{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:57:48Z","timestamp":1725537468414},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642041273"},{"type":"electronic","value":"9783642041280"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_38","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T14:16:36Z","timestamp":1252937796000},"page":"420-431","source":"Crossref","is-referenced-by-count":3,"title":["On Optimally Partitioning a Text to Improve Its Compression"],"prefix":"10.1007","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","reference":[{"issue":"1-2","key":"38_CR1","doi-asserted-by":"publisher","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. Information Sciences\u00a0135(1-2), 1\u201311 (2001)","journal-title":"Information Sciences"},{"key":"38_CR2","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. ACM-SIAM SODA, pp. 175\u2013184 (2000)"},{"issue":"6","key":"38_CR3","doi-asserted-by":"publisher","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\u00a050(6), 825\u2013851 (2003)","journal-title":"J. ACM"},{"key":"38_CR4","doi-asserted-by":"publisher","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, Heidelberg (2008)"},{"key":"38_CR5","unstructured":"Burrows, M., Wheeler, D.: A block-sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation (1994)"},{"key":"38_CR6","doi-asserted-by":"crossref","unstructured":"Chang, F., Dean, J., Ghemawat, S., et al.: Bigtable: A distributed storage system for structured data. ACM Trans. Comput. Syst.\u00a026(2) (2008)","DOI":"10.1145\/1365815.1365816"},{"key":"38_CR7","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press, McGraw-Hill Book Company (2001)"},{"key":"38_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1007\/11841036_67","volume-title":"Algorithms \u2013 ESA 2006","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: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 756\u2013767. Springer, Heidelberg (2006)"},{"key":"38_CR9","doi-asserted-by":"publisher","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. Information and Computation\u00a0207, 849\u2013866 (2009)","journal-title":"Information and Computation"},{"key":"38_CR10","doi-asserted-by":"publisher","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\u00a052, 688\u2013713 (2005)","journal-title":"J. ACM"},{"key":"38_CR11","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Structuring labeled trees for optimal succinctness, and beyond. In: Proc. FOCS, pp. 184\u2013193 (2005)","DOI":"10.1109\/SFCS.2005.69"},{"key":"38_CR12","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Nitto, I., Venturini, R.: On optimally partitioning a text to improve its compression. CoRR, abs\/0906.4692 (2009)","DOI":"10.1007\/978-3-642-04128-0_38"},{"key":"38_CR13","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Venturini, R.: The compressed permuterm index. ACM Transactions on Algorithms (to appear, 2009)","DOI":"10.1145\/1868237.1868248"},{"issue":"3","key":"38_CR14","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0387(3), 236\u2013248 (2007)","journal-title":"Theoretical Computer Science"},{"key":"38_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/3-540-44888-8_10","volume-title":"Combinatorial Pattern Matching","author":"R. Giancarlo","year":"2003","unstructured":"Giancarlo, R., Sciortino, M.: Optimal partitions of strings: A new class of Burrows-Wheeler compression algorithms. In: Baeza-Yates, R., Ch\u00e1vez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol.\u00a02676, pp. 129\u2013143. Springer, Heidelberg (2003)"},{"issue":"6","key":"38_CR16","doi-asserted-by":"publisher","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. Information Processing Management\u00a028(6), 749\u2013764 (1992)","journal-title":"Information Processing Management"},{"issue":"3","key":"38_CR17","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0387(3), 220\u2013235 (2007)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"38_CR18","doi-asserted-by":"publisher","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 Journal on Computing\u00a029(3), 893\u2013911 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"38_CR19","unstructured":"Kulkarni, P., Douglis, F., LaVoie, J.D., Tracey, J.M.: Redundancy elimination within large collections of files. In: USENIX, pp. 59\u201372 (2004)"},{"key":"38_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/978-3-540-75530-2_21","volume-title":"String Processing and Information Retrieval","author":"V. M\u00e4kinen","year":"2007","unstructured":"M\u00e4kinen, V., Navarro, G.: Implicit compression boosting with applications to self-indexing. In: Ziviani, N., Baeza-Yates, R. (eds.) SPIRE 2007. LNCS, vol.\u00a04726, pp. 229\u2013241. Springer, Heidelberg (2007)"},{"issue":"3","key":"38_CR21","doi-asserted-by":"publisher","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\u00a048(3), 407\u2013430 (2001)","journal-title":"J. ACM"},{"issue":"5","key":"38_CR22","doi-asserted-by":"publisher","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. Information Processing Management\u00a041(5), 1175\u20131192 (2005)","journal-title":"Information Processing Management"},{"key":"38_CR23","volume-title":"Lossless Compression Handbook","author":"T. Suel","year":"2002","unstructured":"Suel, T., Memon, N.: Algorithms for delta compression and remote file synchronization. In: Lossless Compression Handbook. Academic Press, London (2002)"},{"key":"38_CR24","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":"38_CR25","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0387(3), 273\u2013283 (2007)","journal-title":"Theoretical Computer Science"},{"key":"38_CR26","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. Morgan Kaufmann, San Francisco (1999)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T11:22:31Z","timestamp":1558524151000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}