{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T19:02:40Z","timestamp":1771614160000,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,8,7]],"date-time":"2010-08-07T00:00:00Z","timestamp":1281139200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,9]]},"DOI":"10.1007\/s00453-010-9437-6","type":"journal-article","created":{"date-parts":[[2010,8,6]],"date-time":"2010-08-06T14:58:17Z","timestamp":1281106697000},"page":"51-74","source":"Crossref","is-referenced-by-count":18,"title":["On Optimally Partitioning a Text to Improve Its Compression"],"prefix":"10.1007","volume":"61","author":[{"given":"Paolo","family":"Ferragina","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Nitto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rossano","family":"Venturini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,8,7]]},"reference":[{"issue":"1\u20132","key":"9437_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0020-0255(01)00097-4","volume":"135","author":"J.L. Bentley","year":"2001","unstructured":"Bentley, J.L., McIlroy, M.D.: Data compression with long repeated strings. Inf. Sci. 135(1\u20132), 1\u201311 (2001)","journal-title":"Inf. Sci."},{"issue":"4","key":"9437_CR2","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1145\/5684.5688","volume":"29","author":"J.L. Bentley","year":"1986","unstructured":"Bentley, J.L., Sleator, D.D., Tarjan, R.E., Wei, V.K.: A locally adaptive data compression scheme. Commun. ACM 29(4), 320\u2013330 (1986)","journal-title":"Commun. ACM"},{"key":"9437_CR3","doi-asserted-by":"crossref","first-page":"939","DOI":"10.1007\/978-0-387-30162-4_418","volume-title":"Encyclopedia of Algorithms","author":"A.L. Buchsbaum","year":"2008","unstructured":"Buchsbaum, A.L., Giancarlo, R.: Table compression. In: Kao, M.Y. (ed.) Encyclopedia of Algorithms, pp. 939\u2013942. Springer, Berlin (2008)"},{"key":"9437_CR4","unstructured":"Buchsbaum, A.L., Caldwell, D.F., Church, K.W., Fowler, G.S., Muthukrishnan, S.: Engineering the compression of massive tables: an experimental approach. In: Proc. of 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 175\u2013184 (2000)"},{"issue":"6","key":"9437_CR5","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1145\/950620.950622","volume":"50","author":"A.L. Buchsbaum","year":"2003","unstructured":"Buchsbaum, A.L., Fowler, G.S., Giancarlo, R.: Improving table compression with combinatorial optimization. J. ACM 50(6), 825\u2013851 (2003)","journal-title":"J. ACM"},{"key":"9437_CR6","unstructured":"Burrows, M., Wheeler, D.: A block-sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation (1994)"},{"key":"9437_CR7","doi-asserted-by":"crossref","unstructured":"Chang, F., Dean, J., Ghemawat, S., Hsieh, W.C., Wallach, D.A., Burrows, M., Chandra, T., Fikes, A., Gruber, R.E.: Bigtable: a distributed storage system for structured data. ACM Trans. Comput. Syst. 26(2) (2008)","DOI":"10.1145\/1365815.1365816"},{"key":"9437_CR8","volume-title":"Algorithms","author":"S. Dasgupta","year":"2006","unstructured":"Dasgupta, S., Papadimitriou, C., Vazirani, U.: Algorithms. McGraw-Hill Science\/Engineering\/Math, New York (2006)"},{"issue":"9","key":"9437_CR9","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1093\/comjnl\/39.9.731","volume":"39","author":"P.M. Fenwick","year":"1996","unstructured":"Fenwick, P.M.: The burrows-wheeler transform for block sorting text compression: principles and improvements. Comput. J. 39(9), 731\u2013740 (1996)","journal-title":"Comput. J."},{"key":"9437_CR10","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G.: On compressing the textual web. In: Proc. of Third ACM Conference on Web Search and Data Mining (WSDM) (2010)","DOI":"10.1145\/1718487.1718536"},{"key":"9437_CR11","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Venturini, R.: The compressed permuterm index. ACM Trans. Algorithms (2010, to appear)","DOI":"10.1145\/1868237.1868248"},{"key":"9437_CR12","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1145\/1082036.1082043","volume":"52","author":"P. Ferragina","year":"2005","unstructured":"Ferragina, P., Giancarlo, R., Manzini, G., Sciortino, M.: Boosting textual compression in optimal linear time. J. ACM 52, 688\u2013713 (2005)","journal-title":"J. ACM"},{"key":"9437_CR13","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Structuring labeled trees for optimal succinctness, and beyond. In: Proc. of 46th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 184\u2013193 (2005)","DOI":"10.1109\/SFCS.2005.69"},{"key":"9437_CR14","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Compressing and searching XML data via two zips. In: Proc. of 15th International World Wide Web Conference (WWW), pp. 751\u2013760 (2006)","DOI":"10.1145\/1135777.1135891"},{"key":"9437_CR15","series-title":"LNCS","first-page":"756","volume-title":"Proc. of 14th European Symposium on Algorithms (ESA\u201906)","author":"P. Ferragina","year":"2006","unstructured":"Ferragina, P., Giancarlo, R., Manzini, G.: The engineering of a compression boosting library: theory vs practice in BWT compression. In: Proc. of 14th European Symposium on Algorithms (ESA\u201906). LNCS, vol.\u00a04168, pp.\u00a0756\u2013767. Springer, Berlin (2006)"},{"key":"9437_CR16","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1016\/j.ic.2008.12.010","volume":"207","author":"P. Ferragina","year":"2009","unstructured":"Ferragina, P., Giancarlo, R., Manzini, G.: The myriad virtues of wavelet trees. Inf. Comput. 207, 849\u2013866 (2009)","journal-title":"Inf. Comput."},{"key":"9437_CR17","first-page":"201","volume-title":"Pattern Matching Algorithms","author":"R. Giancarlo","year":"1997","unstructured":"Giancarlo, R.: Dynamic programming: special cases. In: Apostolico, A., Galil, Z. (eds.) Pattern Matching Algorithms, 2nd edn., pp.\u00a0201\u2013236. Oxford University Press, London (1997)","edition":"2"},{"key":"9437_CR18","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/3-540-44888-8_10","volume-title":"Proc. of 14th Symposium on Combinatorial Pattern Matching (CPM)","author":"R. Giancarlo","year":"2003","unstructured":"Giancarlo, R., Sciortino, M.: Optimal partitions of strings: a new class of Burrows-Wheeler compression algorithms. In: Proc. of 14th Symposium on Combinatorial Pattern Matching (CPM). LNCS, vol.\u00a02676, pp.129\u2013143. Springer, Berlin (2003)"},{"issue":"3","key":"9437_CR19","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/j.tcs.2007.07.019","volume":"387","author":"R. Giancarlo","year":"2007","unstructured":"Giancarlo, R., Restivo, A., Sciortino, M.: From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization. Theor. Comput. Sci. 387(3), 236\u2013248 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9437_CR20","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proc. of 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 841\u2013850 (2003)"},{"issue":"6","key":"9437_CR21","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1016\/0306-4573(92)90066-9","volume":"28","author":"P.G. Howard","year":"1992","unstructured":"Howard, P.G., Vitter, J.S.: Analysis of arithmetic coding for data compression. Inf. Process. Manag. 28(6), 749\u2013764 (1992)","journal-title":"Inf. Process. Manag."},{"issue":"3","key":"9437_CR22","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/j.tcs.2007.07.020","volume":"387","author":"H. Kaplan","year":"2007","unstructured":"Kaplan, H., Landau, S., Verbin, E.: A simpler analysis of Burrows-Wheeler-based compression. Theor. Comput. Sci. 387(3), 220\u2013235 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9437_CR23","doi-asserted-by":"crossref","first-page":"893","DOI":"10.1137\/S0097539797331105","volume":"29","author":"R. Kosaraju","year":"1999","unstructured":"Kosaraju, R., Manzini, G.: Compression of low entropy strings with Lempel\u2013Ziv algorithms. SIAM J. Comput. 29(3), 893\u2013911 (1999)","journal-title":"SIAM J. Comput."},{"key":"9437_CR24","unstructured":"Kulkarni, P., Douglis, F., LaVoie, J.D., Tracey, J.M.: Redundancy elimination within large collections of files. In: USENIX Annual Technical Conference, pp. 59\u201372 (2004)"},{"key":"9437_CR25","series-title":"LNCS","first-page":"703","volume-title":"Proc. of 7th Latin American Symposium on Theoretical Informatics (LATIN)","author":"V. M\u00e4kinen","year":"2006","unstructured":"M\u00e4kinen, V., Navarro, G.: Position-restricted substring searching. In: Proc. of 7th Latin American Symposium on Theoretical Informatics (LATIN). LNCS, vol.\u00a03887, pp.\u00a0703\u2013714. Springer, Berlin (2006)"},{"key":"9437_CR26","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/978-3-540-75530-2_21","volume-title":"Proc. of 14th Symp. on String Processing and Information Retrieval (SPIRE)","author":"V. M\u00e4kinen","year":"2007","unstructured":"M\u00e4kinen, V., Navarro, G.: Implicit compression boosting with applications to self-indexing. In: Proc. of 14th Symp. on String Processing and Information Retrieval (SPIRE). LNCS, vol.\u00a04726, pp.\u00a0229\u2013241. Springer, Berlin (2007)"},{"issue":"3","key":"9437_CR27","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1145\/382780.382782","volume":"48","author":"G. Manzini","year":"2001","unstructured":"Manzini, G.: An analysis of the Burrows-Wheeler transform. J. ACM 48(3), 407\u2013430 (2001)","journal-title":"J. ACM"},{"issue":"5","key":"9437_CR28","doi-asserted-by":"crossref","first-page":"1175","DOI":"10.1016\/j.ipm.2004.08.009","volume":"41","author":"A. Moffat","year":"2005","unstructured":"Moffat, A., Isal, R.Y.: Word-based text compression using the Burrows-Wheeler transform. Inf. Process. Manag. 41(5), 1175\u20131192 (2005)","journal-title":"Inf. Process. Manag."},{"key":"9437_CR29","first-page":"257","volume-title":"Proc. of 3rd Conference on Web Information Systems Engineering (WISE)","author":"Z. Ouyang","year":"2002","unstructured":"Ouyang, Z., Memon, N.D., Suel, T., Trendafilov, D.: Cluster-based delta compression of a collection of files. In: Proc. of 3rd Conference on Web Information Systems Engineering (WISE), pp.\u00a0257\u2013268. IEEE Comput. Soc., Los Alamitos (2002)"},{"key":"9437_CR30","volume-title":"Lossless Compression Handbook","author":"T. Suel","year":"2002","unstructured":"Suel, T., Memon, N.: Algorithms for delta compression and remote file synchronization. In: Sayood,\u00a0K. (ed.) Lossless Compression Handbook. Academic Press, New York (2002)"},{"key":"9437_CR31","unstructured":"Trendafilov, D., Memon, N., Suel, T.: Compressing file collections with a TSP-based approach. Technical Report TR-CIS-2004-02, Polytechnic University (2004)"},{"issue":"3","key":"9437_CR32","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/j.tcs.2007.07.016","volume":"387","author":"B.D. Vo","year":"2007","unstructured":"Vo, B.D., Vo, K.-P.: Compressing table data with column dependency. Theor. Comput. Sci. 387(3), 273\u2013283 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9437_CR33","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images","author":"I.H. Witten","year":"1999","unstructured":"Witten, I.H., Moffat, A., Bell, T.C.: Managing Gigabytes: Compressing and Indexing Documents and Images, 2nd edn. Morgan Kaufmann, Los Altos (1999)","edition":"2"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9437-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9437-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9437-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:06Z","timestamp":1559123106000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9437-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8,7]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["9437"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9437-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,8,7]]}}}