{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T20:15:23Z","timestamp":1776802523860,"version":"3.51.2"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319774039","type":"print"},{"value":"9783319774046","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-77404-6_36","type":"book-chapter","created":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T10:03:11Z","timestamp":1520848991000},"page":"490-503","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["On the Approximation Ratio of\u00a0Lempel-Ziv Parsing"],"prefix":"10.1007","author":[{"given":"Travis","family":"Gagie","sequence":"first","affiliation":[]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[]},{"given":"Nicola","family":"Prezza","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"key":"36_CR1","unstructured":"Belazzougui, D., Cunial, F.: Representing the suffix tree with the CDAWG. In: Proceedings of 28th Annual Symposium on Combinatorial Pattern Matching (CPM). LIPIcs, vol. 78, pp. 7:1\u20137:13 (2017)"},{"key":"36_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/978-3-319-19929-0_3","volume-title":"Combinatorial Pattern Matching","author":"D Belazzougui","year":"2015","unstructured":"Belazzougui, D., Cunial, F., Gagie, T., Prezza, N., Raffinot, M.: Composite repetition-aware data structures. In: Cicalese, F., Porat, E., Vaccaro, U. (eds.) CPM 2015. LNCS, vol. 9133, pp. 26\u201339. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-19929-0_3"},{"key":"36_CR3","doi-asserted-by":"crossref","unstructured":"Bille, P., Gagie, T., Li G\u00f8rtz, I., Prezza, N.: A separation between run-length SLPs and LZ77. CoRR, abs\/1711.07270 (2017)","DOI":"10.1016\/j.jda.2018.09.002"},{"issue":"3","key":"36_CR4","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1145\/28869.28873","volume":"34","author":"A Blumer","year":"1987","unstructured":"Blumer, A., Blumer, J., Haussler, D., McConnell, R.M., Ehrenfeucht, A.: Complete inverted files for efficient text retrieval and analysis. J. ACM 34(3), 578\u2013595 (1987)","journal-title":"J. ACM"},{"key":"36_CR5","unstructured":"Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Technical report 124, Digital Equipment Corporation (1994)"},{"issue":"7","key":"36_CR6","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M Charikar","year":"2005","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"36_CR7","volume-title":"Elements of Information Theory","author":"T Cover","year":"2006","unstructured":"Cover, T., Thomas, J.: Elements of Information Theory, 2nd edn. Wiley, Hoboken (2006)","edition":"2"},{"key":"36_CR8","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.jda.2011.02.002","volume":"11","author":"M Crochemore","year":"2012","unstructured":"Crochemore, M., Iliopoulos, C.S., Kubica, M., Rytter, W., Wale\u0144, T.: Efficient algorithms for three variants of the LPF table. J. Discrete Algorithms 11, 51\u201361 (2012)","journal-title":"J. Discrete Algorithms"},{"key":"36_CR9","unstructured":"Dinklage, P., Fischer, J., K\u00f6ppl, D., L\u00f6bel, M., Sadakane, K.: Compression with the tudocomp framework. CoRR, abs\/1702.07577 (2017)"},{"key":"36_CR10","unstructured":"Fici, G.: Factorizations of the Fibonacci infinite word. J. Integer Sequences, 18(9), Article 3 (2015)"},{"key":"36_CR11","doi-asserted-by":"publisher","first-page":"734","DOI":"10.1101\/gr.114819.110","volume":"21","author":"MH-Y Fritz","year":"2011","unstructured":"Fritz, M.H.-Y., Leinonen, R., Cochrane, G., Birney, E.: Efficient storage of high throughput DNA sequencing data using reference-based compression. Genome Res. 21, 734\u2013740 (2011)","journal-title":"Genome Res."},{"issue":"6","key":"36_CR12","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1016\/j.ipl.2006.04.008","volume":"99","author":"T Gagie","year":"2006","unstructured":"Gagie, T.: Large alphabets and incompressibility. Inf. Process. Lett. 99(6), 246\u2013251 (2006)","journal-title":"Inf. Process. Lett."},{"key":"36_CR13","unstructured":"Gallant, J.K.: String Compression Algorithms. Ph.D thesis. Princeton University (1982)"},{"key":"36_CR14","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P.: Pattern matching in Lempel-Ziv compressed strings: fast, simple, and deterministic. CoRR, abs\/1104.4203 (2011)","DOI":"10.1137\/1.9781611973082.29"},{"key":"36_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-319-46049-9_4","volume-title":"String Processing and Information Retrieval","author":"D Hucke","year":"2016","unstructured":"Hucke, D., Lohrey, M., Reh, C.P.: The smallest grammar problem revisited. In: Inenaga, S., Sadakane, K., Sakai, T. (eds.) SPIRE 2016. LNCS, vol. 9954, pp. 35\u201349. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-46049-9_4"},{"key":"36_CR16","unstructured":"I, T.: Longest common extensions with recompression. In: Proceedings of 28th Annual Symposium on Combinatorial Pattern Matching (CPM). LIPIcs, vol. 78, pp. 18:1\u201318:15 (2017)"},{"key":"36_CR17","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2015.05.027","volume":"592","author":"A Jez","year":"2015","unstructured":"Jez, A.: Approximation of grammar-based compression via recompression. Theor. Comput. Sci. 592, 115\u2013134 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"36_CR18","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/j.tcs.2015.12.032","volume":"616","author":"A Jez","year":"2016","unstructured":"Jez, A.: A really simple approximation of smallest grammar. Theor. Comput. Sci. 616, 141\u2013150 (2016)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"36_CR19","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM 53(6), 918\u2013936 (2006)","journal-title":"J. ACM"},{"issue":"3","key":"36_CR20","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1109\/18.841160","volume":"46","author":"JC Kieffer","year":"2000","unstructured":"Kieffer, J.C., Yang, E.-H.: Grammar-based codes: a new class of universal lossless source codes. IEEE Trans. Inf. Theory 46(3), 737\u2013754 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"36_CR21","first-page":"1","volume":"1","author":"AN Kolmogorov","year":"1965","unstructured":"Kolmogorov, A.N.: Three approaches to the quantitative definition of information. Prob. Inf. Transm. 1(1), 1\u20137 (1965)","journal-title":"Prob. Inf. Transm."},{"key":"36_CR22","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2012.02.006","volume":"483","author":"S Kreft","year":"2013","unstructured":"Kreft, S., Navarro, G.: On compressing and indexing repetitive sequences. Theor. Comput. Sci. 483, 115\u2013133 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"36_CR23","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","volume":"22","author":"A Lempel","year":"1976","unstructured":"Lempel, A., Ziv, J.: On the complexity of finite sequences. IEEE Trans. Inf. Theory 22(1), 75\u201381 (1976)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"36_CR24","first-page":"40","volume":"12","author":"V M\u00e4kinen","year":"2005","unstructured":"M\u00e4kinen, V., Navarro, G.: Succinct suffix arrays based on run-length encoding. Nord. J. Comput. 12(1), 40\u201366 (2005)","journal-title":"Nord. J. Comput."},{"issue":"5","key":"36_CR25","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"36_CR26","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/S0020-0190(02)00512-4","volume":"86","author":"S Mantaci","year":"2003","unstructured":"Mantaci, S., Restivo, A., Sciortino, M.: Burrows-Wheeler transform and Sturmian words. Inf. Process. Lett. 86(5), 241\u2013246 (2003)","journal-title":"Inf. Process. Lett."},{"key":"36_CR27","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316588284","volume-title":"Compact Data Structures - A Practical Approach","author":"G Navarro","year":"2016","unstructured":"Navarro, G.: Compact Data Structures - A Practical Approach. Cambridge University Press, Cambridge (2016)"},{"key":"36_CR28","unstructured":"Nishimoto, T., I, T., Inenaga, S., Bannai, H., Takeda, M.: Fully dynamic data structure for LCE queries in compressed space. In: Proceedings of 41st International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 72:1\u201372:15 (2016)"},{"key":"36_CR29","unstructured":"Prezza, N.: Compressed Computation for Text Indexing. Ph.D thesis. University of Udine (2016)"},{"issue":"1","key":"36_CR30","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/322234.322237","volume":"28","author":"M Rodeh","year":"1981","unstructured":"Rodeh, M., Pratt, V.R., Even, S.: Linear algorithm for data compression via string matching. J. ACM 28(1), 16\u201324 (1981)","journal-title":"J. ACM"},{"issue":"1\u20133","key":"36_CR31","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theor. Comput. Sci. 302(1\u20133), 211\u2013222 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"24","key":"36_CR32","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1016\/j.jda.2004.08.016","volume":"3","author":"H Sakamoto","year":"2005","unstructured":"Sakamoto, H.: A fully linear-time approximation algorithm for grammar-based compression. J. Discrete Algorithms 3(24), 416\u2013430 (2005)","journal-title":"J. Discrete Algorithms"},{"key":"36_CR33","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","volume":"27","author":"CE Shannon","year":"1948","unstructured":"Shannon, C.E.: A mathematical theory of communication. Bell Syst. Tech. J. 27, 398\u2013403 (1948)","journal-title":"Bell Syst. Tech. J."},{"issue":"7","key":"36_CR34","doi-asserted-by":"publisher","first-page":"e1002195","DOI":"10.1371\/journal.pbio.1002195","volume":"17","author":"ZD Sthephens","year":"2015","unstructured":"Sthephens, Z.D., Lee, S.Y., Faghri, F., Campbell, R.H., Chenxiang, Z., Efron, M.J., Iyer, R., Sinha, S., Robinson, G.E.: Big data: astronomical or genomical? PLoS Biol. 17(7), e1002195 (2015)","journal-title":"PLoS Biol."},{"issue":"4","key":"36_CR35","doi-asserted-by":"publisher","first-page":"928","DOI":"10.1145\/322344.322346","volume":"29","author":"JA Storer","year":"1982","unstructured":"Storer, J.A., Szymanski, T.G.: Data compression via textual substitution. J. ACM 29(4), 928\u2013951 (1982)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","LATIN 2018: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-77404-6_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T16:03:22Z","timestamp":1709827402000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-77404-6_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319774039","9783319774046"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-77404-6_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"13 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Buenos Aires","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Argentina","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/latin2018.dc.uba.ar\/#","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}