{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T11:55:14Z","timestamp":1778586914133,"version":"3.51.4"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2006,10]]},"abstract":"<jats:p>We report on a new experimental analysis of high-order entropy-compressed suffix arrays, which retains the theoretical performance of previous work and represents an improvement in practice. Our experiments indicate that the resulting text index offers state-of-the-art compression. In particular, we require roughly 20% of the original text size---without requiring a separate instance of the text. We can additionally use a simple notion to encode and decode block-sorting transforms (such as the Burrows--Wheeler transform), achieving a compression ratio comparable to that of bzip2. We also provide a compressed representation of suffix trees (and their associated text) in a total space that is comparable to that of the text alone compressed with gzip.<\/jats:p>","DOI":"10.1145\/1198513.1198521","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"611-639","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":65,"title":["When indexing equals compression"],"prefix":"10.1145","volume":"2","author":[{"given":"Luca","family":"Foschini","sequence":"first","affiliation":[{"name":"Scuola Superiore Sant'Anna, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ankur","family":"Gupta","sequence":"additional","affiliation":[{"name":"Duke University, Durham, North Carolina, NC"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, Indiana, IN"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00065-0"},{"key":"e_1_2_1_2_1","volume-title":"CPM: 12th Symposium on Combinatorial Pattern Matching.","author":"Arimura H.","unstructured":"Arimura , H. , Asaka , H. , Sakamoto , H. , and Arikawa , S . 2001. Efficient discovery of proximity patterns with suffix arrays (extended abstract) . In CPM: 12th Symposium on Combinatorial Pattern Matching. Arimura, H., Asaka, H., Sakamoto, H., and Arikawa, S. 2001. Efficient discovery of proximity patterns with suffix arrays (extended abstract). In CPM: 12th Symposium on Combinatorial Pattern Matching."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.05.002"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/5684.5688"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795294165"},{"key":"e_1_2_1_6_1","unstructured":"The Canterbury Corpus. 2001. http:\/\/corpus.canterbury.ac.nz. The Canterbury Corpus. 2001. http:\/\/corpus.canterbury.ac.nz."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840440"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.426"},{"key":"e_1_2_1_9_1","volume-title":"Punctured elias codes for variable-length coding of the integers","author":"Fenwick P.","unstructured":"Fenwick , P. 1996. Punctured elias codes for variable-length coding of the integers . The University of Auckland , NZ. TR 137. ISSN 1173--3500. Fenwick, P. 1996. Punctured elias codes for variable-length coding of the integers. The University of Auckland, NZ. TR 137. ISSN 1173--3500."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.484"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082043"},{"key":"e_1_2_1_12_1","first-page":"269","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Ferragina P.","unstructured":"Ferragina , P. , and Manzini , G . 2001. An experimental study of an opportunistic index . In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York , pp. 269 -- 278 . Ferragina, P., and Manzini, G. 2001. An experimental study of an opportunistic index. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 269--278."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the IEEE Data Compression Conference","author":"Foschini L.","unstructured":"Foschini , L. , Grossi , R. , Gupta , A. , and Vitter , J. S . 2004. Fast compression with a static model in high-order entropy . In Proceedings of the IEEE Data Compression Conference ( Snowbird, UT, Mar.) Foschini, L., Grossi, R., Gupta, A., and Vitter, J. S. 2004. Fast compression with a static model in high-order entropy. In Proceedings of the IEEE Data Compression Conference (Snowbird, UT, Mar.)"},{"key":"e_1_2_1_15_1","first-page":"66","volume-title":"Prentice-Hall","author":"Gonnet G. H.","unstructured":"Gonnet , G. H. , Baeza-Yates , R. A. , and Snider , T . 1992. New indices for text: PAT trees and PAT arrays. In Information Retrieval: Data Structures and Algorithms. chap. 5 . Prentice-Hall , Englewood Cliffs, NJ , pp. 66 -- 82 . Gonnet, G. H., Baeza-Yates, R. A., and Snider, T. 1992. New indices for text: PAT trees and PAT arrays. In Information Retrieval: Data Structures and Algorithms. chap. 5. Prentice-Hall, Englewood Cliffs, NJ, pp. 66--82."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (Jan.), ACM","author":"Grossi R.","unstructured":"Grossi , R. , Gupta , A. , and Vitter , J. S . 2003. High-order entropy-compressed text indexes . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (Jan.), ACM , New York. Grossi, R., Gupta, A., and Vitter, J. S. 2003. High-order entropy-compressed text indexes. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (Jan.), ACM, New York."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM","author":"Grossi R.","unstructured":"Grossi , R. , Gupta , A. , and Vitter , J. S . 2004. When indexing equals compression: Experiments with compressing suffix arrays and applications . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM , New York. Grossi, R., Gupta, A., and Vitter, J. S. 2004. When indexing equals compression: Experiments with compressing suffix arrays and applications. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402354"},{"key":"e_1_2_1_19_1","volume-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"Gusfield D.","unstructured":"Gusfield , D. 1997. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology . Cambridge University Press , Cambridge, MA . Gusfield, D. 1997. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge, MA."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX).","author":"Hon W.","unstructured":"Hon , W. , Lam , T. , Tse , W. , Wong , C. , and Yiu , S . 2004. Practical aspects of compressed suffix arrays and fm-index in searching dna sequences . In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX). Hon, W., Lam, T., Tse, W., Wong, C., and Yiu, S. 2004. Practical aspects of compressed suffix arrays and fm-index in searching dna sequences. In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX)."},{"key":"e_1_2_1_21_1","first-page":"251","volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundation of Computer Science. IEEE Computer Society Press, Los Alamitos, CA","author":"Hon W.-K.","unstructured":"Hon , W.-K. , Sadakane , K. , and Sung , W . -K. 2003. Breaking a time-and-space barrier in constructing full-text indices . In Proceedings of the 44th Annual IEEE Symposium on Foundation of Computer Science. IEEE Computer Society Press, Los Alamitos, CA pp. 251 -- 260 . Hon, W.-K., Sadakane, K., and Sung, W.-K. 2003. Breaking a time-and-space barrier in constructing full-text indices. In Proceedings of the 44th Annual IEEE Symposium on Foundation of Computer Science. IEEE Computer Society Press, Los Alamitos, CA pp. 251--260."},{"key":"e_1_2_1_22_1","unstructured":"Howard P. G. 1997. Interleaving entropy codes. In Sequences. Howard P. G. 1997. Interleaving entropy codes. In Sequences."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63533"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Kasai T. Lee G. Arimura H. Arikawa S. and Park K. 2001. Linear-time longest-common-prefix computation in suffix arrays and its applications. In Combinatorial Pattern Matching (CPM). 181--192. Kasai T. Lee G. Arimura H. Arikawa S. and Park K. 2001. Linear-time longest-common-prefix computation in suffix arrays and its applications. In Combinatorial Pattern Matching (CPM). 181--192.","DOI":"10.1007\/3-540-48194-X_17"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199911)29:13%3C1149::AID-SPE274%3E3.0.CO;2-O"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Li M. and Vitanyi P. 1997. An Introduction to Kolmogorov Complexity and Its Applications. Springer-Verlag New York. Li M. and Vitanyi P. 1997. An Introduction to Kolmogorov Complexity and Its Applications. Springer-Verlag New York.","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/290159.290162"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364092"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1151"},{"key":"e_1_2_1_32_1","volume-title":"Tech. Rep. TR\/DCC-2006-6","author":"Navarro G.","year":"2006","unstructured":"Navarro , G. , and M\u00e4kinen , V . 2006 . Compressed full-text indexes. Tech. Rep. TR\/DCC-2006-6 , University of Chile . Navarro, G., and M\u00e4kinen, V. 2006. Compressed full-text indexes. Tech. Rep. TR\/DCC-2006-6, University of Chile."},{"key":"e_1_2_1_33_1","unstructured":"Nelson M. 2003. Run length encoding\/RLE. http:\/\/www.datacompression.info\/RLE.shtml. Nelson M. 2003. Run length encoding\/RLE. http:\/\/www.datacompression.info\/RLE.shtml."},{"key":"e_1_2_1_34_1","unstructured":"Oki M. 2003. http:\/\/www.infor.kanazawa-it.ac.jp\/~ishii\/lhaunix\/. Oki M. 2003. http:\/\/www.infor.kanazawa-it.ac.jp\/~ishii\/lhaunix\/."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369909"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 233--242","author":"Raman R.","unstructured":"Raman , R. , Raman , V. , and Rao , S. S . 2002. Succinct indexable dictionaries with applications to encoding k-ary trees and multisets . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 233--242 . Raman, R., Raman, V., and Rao, S. S. 2002. Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 233--242."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00298-8"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.232.0149"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Sadakane K.","year":"2002","unstructured":"Sadakane , K. 2002 . Succinct representations of lcp information and improvements in the compressed suffix arrays . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York. Sadakane, K. 2002. Succinct representations of lcp information and improvements in the compressed suffix arrays. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00087-7"},{"key":"e_1_2_1_41_1","unstructured":"Schindler M. 1999. http:\/\/www.compressconsult.com\/rangecoder. Schindler M. 1999. http:\/\/www.compressconsult.com\/rangecoder."},{"key":"e_1_2_1_42_1","unstructured":"Smith J. O. III. 2003. http:\/\/ccrma-www.stanford.edu\/~jos\/mdft\/Autocorrelation.html. Smith J. O. III. 2003. http:\/\/ccrma-www.stanford.edu\/~jos\/mdft\/Autocorrelation.html."},{"key":"e_1_2_1_43_1","unstructured":"TREC. Tipster 3. 2000. http:\/\/trec.nist.gov\/data\/docs_eng.html. TREC. Tipster 3. 2000. http:\/\/trec.nist.gov\/data\/docs_eng.html."},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Wirth A. I. and Moffat A. 2001. Can we do without ranks in burrows wheeler transform compression&quest; In Data Compression Conference. pp. 419--428. Wirth A. I. and Moffat A. 2001. Can we do without ranks in burrows wheeler transform compression&quest; In Data Compression Conference. pp. 419--428.","DOI":"10.1109\/DCC.2001.917173"},{"key":"e_1_2_1_45_1","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan-Kaufmann","author":"Witten I. H.","year":"1999","unstructured":"Witten , I. H. , Moffat , A. , and Bell , T. C . 1999 . Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan-Kaufmann , Los Altos, CA . Witten, I. H., Moffat, A., and Bell, T. C. 1999. Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan-Kaufmann, Los Altos, CA."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1198513.1198521","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T16:08:32Z","timestamp":1736957312000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1198513.1198521"}},"subtitle":["Experiments with compressing suffix arrays and applications"],"short-title":[],"issued":{"date-parts":[[2006,10]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,10]]}},"alternative-id":["10.1145\/1198513.1198521"],"URL":"https:\/\/doi.org\/10.1145\/1198513.1198521","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,10]]},"assertion":[{"value":"2006-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}