{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T14:26:20Z","timestamp":1773325580720,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2005,7,1]],"date-time":"2005-07-01T00:00:00Z","timestamp":1120176000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2005,7]]},"abstract":"<jats:p>\n            We provide a general boosting technique for Textual Data Compression. Qualitatively, it takes a good compression algorithm and turns it into an algorithm with a better compression performance guarantee. It displays the following remarkable properties: (a) it can turn\n            <jats:italic>any memoryless<\/jats:italic>\n            compressor into a compression algorithm that uses the \u201cbest possible\u201d contexts; (b) it is very simple and\n            <jats:italic>optimal<\/jats:italic>\n            in terms of time; and (c) it admits a decompression algorithm again optimal in time. To the best of our knowledge, this is the first boosting technique displaying these properties.Technically, our boosting technique builds upon three main ingredients: the Burrows--Wheeler Transform, the Suffix Tree data structure, and a greedy algorithm to process them. Specifically, we show that there exists a proper partition of the Burrows--Wheeler Transform of a string\n            <jats:italic>s<\/jats:italic>\n            that shows a deep combinatorial relation with the\n            <jats:italic>k<\/jats:italic>\n            th order entropy of\n            <jats:italic>s<\/jats:italic>\n            . That partition can be identified via a greedy processing of the suffix tree of\n            <jats:italic>s<\/jats:italic>\n            with the aim of minimizing a proper objective function over its nodes. The final compressed string is then obtained by compressing individually each substring of the partition by means of the base compressor we wish to boost.Our boosting technique is inherently combinatorial because it does not need to assume any prior probabilistic model about the source emitting\n            <jats:italic>s<\/jats:italic>\n            , and it does not deploy any training, parameter estimation and learning. Various corollaries are derived from this main achievement. Among the others, we show analytically that using our booster, we get better compression algorithms than some of the best existing ones, that is, LZ77, LZ78, PPMC and the ones derived from the Burrows--Wheeler Transform. Further, we settle analytically some long-standing open problems about the algorithmic structure and the performance of BWT-based compressors. Namely, we provide the first family of BWT algorithms that do not use Move-To-Front or Symbol Ranking as a part of the compression process.\n          <\/jats:p>","DOI":"10.1145\/1082036.1082043","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T16:00:45Z","timestamp":1131379245000},"page":"688-713","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":93,"title":["Boosting textual compression in optimal linear time"],"prefix":"10.1145","volume":"52","author":[{"given":"Paolo","family":"Ferragina","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raffaele","family":"Giancarlo","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Palermo, Palermo, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giovanni","family":"Manzini","sequence":"additional","affiliation":[{"name":"Universit\u00e0 del Piemonte Orientale, Alessandria, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marinella","family":"Sciortino","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Palermo, Palermo, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/882455.874961"},{"key":"e_1_2_1_2_1","first-page":"188","volume-title":"Proceedings of the IEEE Data Compression Conference, IEEE Computer Society Press, Los Alamitos, Calif.","author":"Balkenhol B.","unstructured":"Balkenhol , B. , Kurtz , S. , and Shtarkov , Y. M . 1999. Modification of the Burrows and Wheeler data compression algorithm . In Proceedings of the IEEE Data Compression Conference, IEEE Computer Society Press, Los Alamitos, Calif. , page 188 . Balkenhol, B., Kurtz, S., and Shtarkov, Y. M. 1999. Modification of the Burrows and Wheeler data compression algorithm. In Proceedings of the IEEE Data Compression Conference, IEEE Computer Society Press, Los Alamitos, Calif., page 188."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/5684.5688"},{"key":"e_1_2_1_4_1","volume-title":"Tech. Rep. 124","author":"Burrows M.","year":"1994","unstructured":"Burrows , M. , and Wheeler , D . 1994 . A block sorting lossless data compression algorithm. Tech. Rep. 124 , Digital Equipment Corporation. Burrows, M., and Wheeler, D. 1994. A block sorting lossless data compression algorithm. Tech. Rep. 124, Digital Equipment Corporation."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1986.1057239"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/40.2_and_3.67"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/30.6.541"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Cover T. M. and Thomas J. A. 1990. Elements of Information Theory. Wiley Interscience New York.   Cover T. M. and Thomas J. A. 1990. Elements of Information Theory. Wiley Interscience New York.","DOI":"10.1002\/0471200611"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.11.014"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.426"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.995542"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055349"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/39.9.731"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(93)90095-P"},{"key":"e_1_2_1_15_1","first-page":"251","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif.","author":"Hon W.","unstructured":"Hon , W. , Sadakane , K. , and Sung , W . 2003. Breaking a time-and-space barrier in constructing full-text indices . In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. , pp. 251 -- 260 . Hon, W., Sadakane, K., and Sung, W. 2003. Breaking a time-and-space barrier in constructing full-text indices. In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 251--260."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the Conference on Probabilistic Computational Complexity. AMS, 150--159","author":"Karp R.","unstructured":"Karp , R. , Pippenger , N. , and Sipser , M . 1985. A Time-Randomness tradeoff . In Proceedings of the Conference on Probabilistic Computational Complexity. AMS, 150--159 . Karp, R., Pippenger, N., and Sipser, M. 1985. A Time-Randomness tradeoff. In Proceedings of the Conference on Probabilistic Computational Complexity. AMS, 150--159."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797331105"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/874052.874870"},{"key":"e_1_2_1_19_1","volume-title":"Moscow)","author":"Levenshtein V. I.","unstructured":"Levenshtein , V. I. 1968. On the redundancy and delay of decodable coding of natural numbers. In (Translation from) Problems in Cybernetics (Nauka , Moscow) vol. 20 , 173--179. Levenshtein, V. I. 1968. On the redundancy and delay of decodable coding of natural numbers. In (Translation from) Problems in Cybernetics (Nauka, Moscow) vol. 20, 173--179."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382782"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.61469"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1546"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1984.1056936"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/874052.874907"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022648800760"},{"key":"e_1_2_1_27_1","volume-title":"MSRI Workshop on Nonlinear Estimation and Classification, D. D. Denison, M. H. Hansen, C. C. Holmes, B. Mallick, and B. Yu, Eds","author":"Schapire R. E.","unstructured":"Schapire , R. E. 2002. The boosting approach to Machine Learning: An overview . In MSRI Workshop on Nonlinear Estimation and Classification, D. D. Denison, M. H. Hansen, C. C. Holmes, B. Mallick, and B. Yu, Eds . Springer-Verlag Lecture Notes in Statistics n. 171, 149--172. Schapire, R. E. 2002. The boosting approach to Machine Learning: An overview. In MSRI Workshop on Nonlinear Estimation and Classification, D. D. Denison, M. H. Hansen, C. C. Holmes, B. Mallick, and B. Yu, Eds. Springer-Verlag Lecture Notes in Statistics n. 171, 149--172."},{"key":"e_1_2_1_28_1","unstructured":"Seward J. 1997. The bzip2 home page. http:\/\/sources.redhat.com\/bzip2.  Seward J. 1997. The bzip2 home page. http:\/\/sources.redhat.com\/bzip2."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/789085.789545"},{"key":"e_1_2_1_30_1","volume-title":"Image and Text Compression","author":"Storer J.","unstructured":"Storer , J. 1992. Image and Text Compression . Kluwer Academic Press , Norwell, Mass . Storer, J. 1992. Image and Text Compression. Kluwer Academic Press, Norwell, Mass."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502099"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_2_1_33_1","first-page":"419","volume-title":"Proceedings of the IEEE Data Compression Conference. IEEE Computer Society Press, Los Alamitos, Calif.","author":"Wirth A.","unstructured":"Wirth , A. , and Moffat , A . 2001. Can we do without ranks in Burrows--Wheeler transform compression? In Proceedings of the IEEE Data Compression Conference. IEEE Computer Society Press, Los Alamitos, Calif. , pp. 419 -- 428 . Wirth, A., and Moffat, A. 2001. Can we do without ranks in Burrows--Wheeler transform compression? In Proceedings of the IEEE Data Compression Conference. IEEE Computer Society Press, Los Alamitos, Calif., pp. 419--428."},{"key":"e_1_2_1_34_1","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images","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 , Second ed. Morgan Kaufmann Publishers , Los Altos , Calif. Witten, I. H., Moffat, A., and Bell, T. C. 1999. Managing Gigabytes: Compressing and Indexing Documents and Images, Second ed. Morgan Kaufmann Publishers, Los Altos, Calif."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1977.1055714"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055934"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1082036.1082043","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1082036.1082043","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:18:46Z","timestamp":1750263526000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1082036.1082043"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,7]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2005,7]]}},"alternative-id":["10.1145\/1082036.1082043"],"URL":"https:\/\/doi.org\/10.1145\/1082036.1082043","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,7]]},"assertion":[{"value":"2005-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}