{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:54Z","timestamp":1760202654882,"version":"3.41.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2015,1,7]],"date-time":"2015-01-07T00:00:00Z","timestamp":1420588800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002850","name":"Fondo Nacional de Desarrollo Cient\u00edfico y Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["1-110066"],"award-info":[{"award-number":["1-110066"]}],"id":[{"id":"10.13039\/501100002850","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2015,2,3]]},"abstract":"<jats:p>\n            We introduce a compression technique for suffix arrays. It is sensitive to the compressibility of the text and\n            <jats:italic>local<\/jats:italic>\n            , meaning that random portions of the suffix array can be decompressed by accessing mostly contiguous memory areas. This makes decompression very fast, especially when various contiguous cells must be accessed.\n          <\/jats:p>\n          <jats:p>\n            Our main technical contributions are the following. First, we show that runs of consecutive values that are known to appear in function \u03a8(\n            <jats:italic>i<\/jats:italic>\n            ) =\n            <jats:italic>A<\/jats:italic>\n            <jats:sup>\u22121<\/jats:sup>\n            [\n            <jats:italic>A<\/jats:italic>\n            [\n            <jats:italic>i<\/jats:italic>\n            ] + 1] of suffix arrays\n            <jats:italic>A<\/jats:italic>\n            of compressible texts also show up as repetitions in the differential suffix array\n            <jats:italic>A<\/jats:italic>\n            '[\n            <jats:italic>i<\/jats:italic>\n            ] =\n            <jats:italic>A<\/jats:italic>\n            [\n            <jats:italic>i<\/jats:italic>\n            ] \u2212\n            <jats:italic>A<\/jats:italic>\n            [\n            <jats:italic>i<\/jats:italic>\n            \u22121]. Second, we use Re-Pair, a grammar-based compressor, to compress the differential suffix array, and upper bound its compression ratio in terms of the number of runs. Third, we show how to compact the space used by the grammar rules by up to 50%, while still permitting direct access to the rules. Fourth, we develop specific variants of Re-Pair that work using knowledge of \u03a8, and use much less space than the general Re-Pair compressor, while achieving almost the same compression ratios. Fifth, we implement the scheme and compare it exhaustively with previous work, including the first implementations of previous theoretical proposals.\n          <\/jats:p>","DOI":"10.1145\/2594408","type":"journal-article","created":{"date-parts":[[2014,5,20]],"date-time":"2014-05-20T13:47:43Z","timestamp":1400593663000},"source":"Crossref","is-referenced-by-count":10,"title":["Locally Compressed Suffix Arrays"],"prefix":"10.1145","volume":"19","author":[{"given":"Rodrigo","family":"Gonz\u00e1lez","sequence":"first","affiliation":[{"name":"University of Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"University of Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H\u00e9ctor","family":"Ferrada","sequence":"additional","affiliation":[{"name":"University of Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,1,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.3390\/a6020319"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00065-0"},{"key":"e_1_2_1_3_1","series-title":"NATO ISI Series","volume-title":"Combinatorial Algorithms on Words","author":"Apostolico A.","unstructured":"A. Apostolico . 1985. The myriad virtues of subword trees . In Combinatorial Algorithms on Words , NATO ISI Series , Springer-Verlag , 85--96. A. Apostolico. 1985. The myriad virtues of subword trees. In Combinatorial Algorithms on Words, NATO ISI Series, Springer-Verlag, 85--96."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/235809.235810"},{"volume-title":"Procedings of the 19th Annual European Symposium on Algorithms (ESA). 748--759","author":"Belazzougui D.","key":"e_1_2_1_5_1","unstructured":"D. Belazzougui and G. Navarro . 2011. Alphabet-independent compressed text indexing . In Procedings of the 19th Annual European Symposium on Algorithms (ESA). 748--759 . D. Belazzougui and G. Navarro. 2011. Alphabet-independent compressed text indexing. In Procedings of the 19th Annual European Symposium on Algorithms (ESA). 748--759."},{"volume-title":"Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 383--391","author":"Clark D.","key":"e_1_2_1_7_1","unstructured":"D. Clark and I. Munro . 1996. Efficient suffix trees on secondary storage . In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 383--391 . D. Clark and I. Munro. 1996. Efficient suffix trees on secondary storage. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 383--391."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/BIBE.2010.22"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063646"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"F.\n      Claude\n     and \n      G.\n      Navarro\n  . \n  2010\n  a. Extended compact web graph representations. In Algorithms and Applications (Ukkonen Festschrift) T. Elomaa H. Mannila and P. Orponen Eds. Lecture Notes in Computer Science vol. \n  6060\n  . \n  Springer 77--91.   F. Claude and G. Navarro. 2010a. Extended compact web graph representations. In Algorithms and Applications (Ukkonen Festschrift) T. Elomaa H. Mannila and P. Orponen Eds. Lecture Notes in Computer Science vol. 6060. Springer 77--91.","DOI":"10.1007\/978-3-642-12476-1_5"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1841909.1841913"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2010.09.004"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"M. Crochemore and W. Rytter. 2002. Jewels of Stringology. World Scientific.  M. Crochemore and W. Rytter. 2002. Jewels of Stringology. World Scientific.","DOI":"10.1142\/4838"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321820"},{"volume-title":"On the number of bits required to implement an associative memory. Memo 61","author":"Fano R.","key":"e_1_2_1_15_1","unstructured":"R. Fano . 1971. On the number of bits required to implement an associative memory. Memo 61 , Computer Structures Group , Project MAC, Massachusetts. R. Fano. 1971. On the number of bits required to implement an associative memory. Memo 61, Computer Structures Group, Project MAC, Massachusetts."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1455268"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796543"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240243"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.02.010"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.09.012"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.08.004"},{"key":"e_1_2_1_23_1","first-page":"66","article-title":"New indices for text: Pat trees and Pat arrays. In Information Retrieval: Data Structures and Algorithms, Prentice-Hall","volume":"3","author":"Gonnet G.","year":"1992","unstructured":"G. Gonnet , R. Baeza-Yates , and T. Snider . 1992 . New indices for text: Pat trees and Pat arrays. In Information Retrieval: Data Structures and Algorithms, Prentice-Hall , Chapter 3 : 66 -- 82 . G. Gonnet, R. Baeza-Yates, and T. Snider. 1992. New indices for text: Pat trees and Pat arrays. In Information Retrieval: Data Structures and Algorithms, Prentice-Hall, Chapter 3: 66--82.","journal-title":"Chapter"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73437-6_23"},{"volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 841--850","author":"Grossi R.","key":"e_1_2_1_25_1","unstructured":"R. Grossi , A. Gupta , and J. Vitter . 2003. High-order entropy-compressed text indexes . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 841--850 . R. Grossi, A. Gupta, and J. Vitter. 2003. High-order entropy-compressed text indexes. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 841--850."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335351"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402354"},{"volume-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"Gusfield D.","key":"e_1_2_1_28_1","unstructured":"D. Gusfield . 1997. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology . Cambridge University Press . D. Gusfield. 1997. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60044-2_43"},{"volume-title":"Proceedings of the 18th International Symposium on String Processing and Information Retrieval (SPIRE). 174--184","author":"K\u00e4rkk\u00e4inen J.","key":"e_1_2_1_30_1","unstructured":"J. K\u00e4rkk\u00e4inen and S. J. Puglisi . 2011. Fixed block compression boosting in FM-indexes . In Proceedings of the 18th International Symposium on String Processing and Information Retrieval (SPIRE). 174--184 . J. K\u00e4rkk\u00e4inen and S. J. Puglisi. 2011. Fixed block compression boosting in FM-indexes. In Proceedings of the 18th International Symposium on String Processing and Information Retrieval (SPIRE). 174--184."},{"volume-title":"Proceedings of the 3rd South American Workshop on String Processing (WSP). 141--155","author":"K\u00e4rkk\u00e4inen J.","key":"e_1_2_1_31_1","unstructured":"J. K\u00e4rkk\u00e4inen and E. Ukkonen . 1996a. Lempel-Ziv parsing and sublinear-size index structures for string matching . In Proceedings of the 3rd South American Workshop on String Processing (WSP). 141--155 . J. K\u00e4rkk\u00e4inen and E. Ukkonen. 1996a. Lempel-Ziv parsing and sublinear-size index structures for string matching. In Proceedings of the 3rd South American Workshop on String Processing (WSP). 141--155."},{"volume-title":"Proceedings of the 2nd Annual International Conference on Computing and Combinatorics (COCOON). 219--230","author":"K\u00e4rkk\u00e4inen J.","key":"e_1_2_1_32_1","unstructured":"J. K\u00e4rkk\u00e4inen and E. Ukkonen . 1996b. Sparse suffix trees . In Proceedings of the 2nd Annual International Conference on Computing and Combinatorics (COCOON). 219--230 . J. K\u00e4rkk\u00e4inen and E. Ukkonen. 1996b. Sparse suffix trees. In Proceedings of the 2nd Annual International Conference on Computing and Combinatorics (COCOON). 219--230."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.892708"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/647819.736207"},{"key":"e_1_2_1_36_1","first-page":"1","article-title":"Compact suffix array\u2014A space-efficient full-text index","volume":"56","author":"M\u00e4kinen V.","year":"2003","unstructured":"V. M\u00e4kinen . 2003 . Compact suffix array\u2014A space-efficient full-text index . Fundamenta Informaticae 56 , 1 -- 2 , 191--210. V. M\u00e4kinen. 2003. Compact suffix array\u2014A space-efficient full-text index. Fundamenta Informaticae 56, 1--2, 191--210.","journal-title":"Fundamenta Informaticae"},{"key":"e_1_2_1_37_1","first-page":"40","article-title":"Succinct suffix arrays based on run-length encoding","volume":"12","author":"M\u00e4kinen V.","year":"2005","unstructured":"V. M\u00e4kinen and G. Navarro . 2005 . Succinct suffix arrays based on run-length encoding . Nordic J. Comput. 12 , 1, 40 -- 66 . V. M\u00e4kinen and G. Navarro. 2005. Succinct suffix arrays based on run-length encoding. Nordic J. Comput. 12, 1, 40--66.","journal-title":"Nordic J. Comput."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2009.0169"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382782"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"e_1_2_1_42_1","volume-title":"Tables. In Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 37--42","author":"Munro I.","year":"1996","unstructured":"I. Munro . 1996 . Tables. In Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 37--42 . I. Munro. 1996. Tables. In Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 37--42."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1216370.1216372"},{"volume-title":"Proceedings of the 10th International Symposium on Experimental Algorithms (SEA). 193--205","author":"Navarro G.","key":"e_1_2_1_44_1","unstructured":"G. Navarro , S. Puglisi , and D. Valenzuela . 2011. Practical compressed document retrieval . In Proceedings of the 10th International Symposium on Experimental Algorithms (SEA). 193--205 . G. Navarro, S. Puglisi, and D. Valenzuela. 2011. Practical compressed document retrieval. In Proceedings of the 10th International Symposium on Experimental Algorithms (SEA). 193--205."},{"volume-title":"Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX). 60--70","author":"Okanohara D.","key":"e_1_2_1_45_1","unstructured":"D. Okanohara and K. Sadakane . 2007. Practical entropy-compressed rank\/select dictionary . In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX). 60--70 . D. Okanohara and K. Sadakane. 2007. Practical entropy-compressed rank\/select dictionary. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX). 60--70."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290680"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00298-8"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000807.2000821"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/646343.689570"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00087-7"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1198-x"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/647813.738278"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2594408","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2594408","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:00:52Z","timestamp":1750230052000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2594408"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,7]]},"references-count":51,"alternative-id":["10.1145\/2594408"],"URL":"https:\/\/doi.org\/10.1145\/2594408","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2015,1,7]]}}}