{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T15:32:23Z","timestamp":1786635143887,"version":"3.56.0"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642214578","type":"print"},{"value":"9783642214585","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-21458-5_6","type":"book-chapter","created":{"date-parts":[[2011,6,27]],"date-time":"2011-06-27T21:11:27Z","timestamp":1309209087000},"page":"41-54","source":"Crossref","is-referenced-by-count":40,"title":["Self-indexing Based on LZ77"],"prefix":"10.1007","author":[{"given":"Sebastian","family":"Kreft","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"6_CR1","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1137\/1.9781611972900.9","volume-title":"2010 Proceedings of the Twelfth Workshop on Algorithm Engineering and Experiments (ALENEX)","author":"Diego Arroyuelo","year":"2010","unstructured":"Arroyuelo, D., C\u00e1novas, R., Navarro, G., Sadakane, K.: Succinct trees in practice. In: ALENEX, pp. 84\u201397 (2010)"},{"issue":"4","key":"6_CR2","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00453-004-1146-6","volume":"43","author":"D. Benoit","year":"2005","unstructured":"Benoit, D., Demaine, E., Munro, I., Raman, R., Raman, V., Rao, S.: Representing trees of higher degree. Algorithmica\u00a043(4), 275\u2013292 (2005)","journal-title":"Algorithmica"},{"key":"6_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/978-3-642-03784-9_12","volume-title":"String Processing and Information Retrieval","author":"N.R. Brisaboa","year":"2009","unstructured":"Brisaboa, N.R., Ladra, S., Navarro, G.: Directly addressable variable-length codes. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol.\u00a05721, pp. 122\u2013130. Springer, Heidelberg (2009)"},{"key":"6_CR4","unstructured":"Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. TRep. 124, DEC (1994)"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Claude, F., Fari\u00f1a, A., Mart\u00ednez-Prieto, M., Navarro, G.: Compressed q-gram indexing for highly repetitive biological sequences. In: BIBE, pp. 86\u201391 (2010)","DOI":"10.1109\/BIBE.2010.22"},{"issue":"4","key":"6_CR6","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P. Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM\u00a052(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"issue":"2","key":"6_CR7","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1145\/1240233.1240243","volume":"3","author":"Paolo Ferragina","year":"2007","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Trans. Alg.\u00a03(2), article 20 (2007)","journal-title":"ACM Transactions on Algorithms"},{"key":"6_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/978-3-642-12200-2_16","volume-title":"LATIN 2010: Theoretical Informatics","author":"J. Fischer","year":"2010","unstructured":"Fischer, J.: Optimal succinctness for range minimum queries. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol.\u00a06034, pp. 158\u2013169. Springer, Heidelberg (2010)"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Gog, S., Fischer, J.: Advantages of shared data structures for sequences of balanced parentheses. In: DCC, pp. 406\u2013415 (2010)","DOI":"10.1109\/DCC.2010.43"},{"key":"6_CR10","unstructured":"Grossi, R., Gupta, A., Vitter, J.: High-order entropy-compressed text indexes. In: SODA, pp. 841\u2013850 (2003)"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Grossi, R., Vitter, J.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. In: STOC, pp. 397\u2013406 (2000)","DOI":"10.1145\/335305.335351"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"He, J., Zeng, J., Suel, T.: Improved index compression techniques for versioned document collections. In: CIKM, pp. 1239\u20131248 (2010)","DOI":"10.1145\/1871437.1871594"},{"key":"6_CR13","unstructured":"K\u00e4rkk\u00e4inen, J.: Repetition-Based Text Indexes. Ph.D. thesis, Univ. Helsinki, Finland (1999)"},{"key":"6_CR14","unstructured":"K\u00e4rkk\u00e4inen, J., Ukkonen, E.: Lempel-Ziv parsing and sublinear-size index structures for string matching. In: WSP, pp. 141\u2013155 (1996)"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Kreft, S.: Self-Index based on LZ77. MSc thesis, Univ. of Chile (2010), http:\/\/www.dcc.uchile.cl\/gnavarro\/algoritmos\/tesisKreft.pdf","DOI":"10.1007\/978-3-642-21458-5_6"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Kreft, S., Navarro, G.: LZ77-like compression with fast random access. In: DCC, pp. 239\u2013248 (2010)","DOI":"10.1109\/DCC.2010.29"},{"key":"6_CR17","unstructured":"Kuruppu, S., Beresford-Smith, B., Conway, T., Zobel, J.: Repetition-based compression of large DNA datasets. In: RECOMB (2009), poster"},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-642-16321-0_20","volume-title":"String Processing and Information Retrieval","author":"S. Kuruppu","year":"2010","unstructured":"Kuruppu, S., Puglisi, S.J., Zobel, J.: Relative lempel-ziv compression of genomes for large-scale storage and retrieval. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 201\u2013206. Springer, Heidelberg (2010)"},{"issue":"3","key":"6_CR19","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/j.tcs.2007.07.013","volume":"387","author":"V. M\u00e4kinen","year":"2007","unstructured":"M\u00e4kinen, V., Navarro, G.: Rank and select revisited and extended. Theo.Comp.Sci.\u00a0387(3), 332\u2013347 (2007)","journal-title":"Theo.Comp.Sci."},{"issue":"3","key":"6_CR20","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1089\/cmb.2009.0169","volume":"17","author":"V. M\u00e4kinen","year":"2010","unstructured":"M\u00e4kinen, V., Navarro, G., Sir\u00e9n, J., V\u00e4lim\u00e4ki, N.: Storage and retrieval of highly repetitive sequence collections. J. Comp. Biol.\u00a017(3), 281\u2013308 (2010)","journal-title":"J. Comp. Biol."},{"issue":"3","key":"6_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":"4","key":"6_CR22","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/321479.321481","volume":"15","author":"D. Morrison","year":"1968","unstructured":"Morrison, D.: PATRICIA-Practical algorithm to retrieve information coded in alphanumeric. J. ACM\u00a015(4), 514\u2013534 (1968)","journal-title":"J. ACM"},{"key":"6_CR23","doi-asserted-by":"crossref","unstructured":"Munro, I., Raman, R., Raman, V., Rao, S.: Succinct representations of permutations. In: ICALP, pp. 345\u2013356 (2003)","DOI":"10.1007\/3-540-45061-0_29"},{"key":"6_CR24","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: SODA, pp. 657\u2013666 (2002)"},{"issue":"1","key":"6_CR25","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/S1570-8667(03)00066-2","volume":"2","author":"G. Navarro","year":"2004","unstructured":"Navarro, G.: Indexing text using the Ziv-Lempel trie. J. Discr. Alg.\u00a02(1), 87\u2013114 (2004)","journal-title":"J. Discr. Alg."},{"issue":"1","key":"6_CR26","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1216370.1216372","volume":"39","author":"Gonzalo Navarro","year":"2007","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Comp. Surv.\u00a039(1), article 2 (2007)","journal-title":"ACM Computing Surveys"},{"key":"6_CR27","doi-asserted-by":"crossref","unstructured":"Okanohara, D., Sadakane, K.: Practical entropy-compressed rank\/select dictionary. In: ALENEX (2007)","DOI":"10.1137\/1.9781611972870.6"},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Succincter. In: FOCS, pp. 305\u2013313 (2008)","DOI":"10.1109\/FOCS.2008.83"},{"key":"6_CR29","unstructured":"Raman, R., Raman, V., Rao, S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: SODA, pp. 233\u2013242 (2002)"},{"issue":"3","key":"6_CR30","first-page":"501","volume":"5","author":"L. Russo","year":"2008","unstructured":"Russo, L., Oliveira, A.: A compressed self-index using a Ziv-Lempel dictionary. Inf. Retr.\u00a05(3), 501\u2013513 (2008)","journal-title":"Inf. Retr."},{"issue":"2","key":"6_CR31","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1016\/S0196-6774(03)00087-7","volume":"48","author":"K. Sadakane","year":"2003","unstructured":"Sadakane, K.: New text indexing functionalities of the compressed suffix arrays. J. Alg.\u00a048(2), 294\u2013313 (2003)","journal-title":"J. Alg."},{"key":"6_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-540-89097-3_17","volume-title":"String Processing and Information Retrieval","author":"J. Sir\u00e9n","year":"2008","unstructured":"Sir\u00e9n, J., V\u00e4lim\u00e4ki, N., M\u00e4kinen, V., Navarro, G.: Run-length compressed indexes are superior for highly repetitive sequence collections. In: Amir, A., Turpin, A., Moffat, A. (eds.) SPIRE 2008. LNCS, vol.\u00a05280, pp. 164\u2013175. Springer, Heidelberg (2008)"},{"issue":"3","key":"6_CR33","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J. Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Inf. Theo.\u00a023(3), 337\u2013343 (1977)","journal-title":"IEEE Trans. Inf. Theo."},{"issue":"5","key":"6_CR34","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J. Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theo.\u00a024(5), 530\u2013536 (1978)","journal-title":"IEEE Trans. Inf. Theo."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21458-5_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T12:04:35Z","timestamp":1560341075000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21458-5_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642214578","9783642214585"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21458-5_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}