{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T11:02:56Z","timestamp":1746010976992,"version":"3.37.0"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642038150"},{"type":"electronic","value":"9783642038167"}],"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-03816-7_21","type":"book-chapter","created":{"date-parts":[[2009,8,19]],"date-time":"2009-08-19T14:43:03Z","timestamp":1250692983000},"page":"235-246","source":"Crossref","is-referenced-by-count":20,"title":["Self-indexed Text Compression Using Straight-Line Programs"],"prefix":"10.1007","author":[{"given":"Francisco","family":"Claude","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Amir, A., Benson, G.: Efficient two-dimensional compressed matching. In: Proc. 2nd DCC, pp. 279\u2013288 (1992)","DOI":"10.1109\/DCC.1992.227453"},{"key":"21_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/11780441_4","volume-title":"Combinatorial Pattern Matching","author":"J. Barbay","year":"2006","unstructured":"Barbay, J., Golynski, A., Munro, I., Rao, S.S.: Adaptive searching in succinctly encoded binary relations and tree-structured documents. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol.\u00a04009, pp. 24\u201335. Springer, Heidelberg (2006)"},{"issue":"1","key":"21_CR3","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.tcs.2003.05.002","volume":"321","author":"M. Bender","year":"2004","unstructured":"Bender, M., Farach-Colton, M.: The level ancestor problem simplified. Theor. Comp. Sci.\u00a0321(1), 5\u201312 (2004)","journal-title":"Theor. Comp. Sci."},{"issue":"4","key":"21_CR4","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.S.: Representing trees of higher degree. Algorithmica\u00a043(4), 275\u2013292 (2005)","journal-title":"Algorithmica"},{"issue":"7","key":"21_CR5","first-page":"2554","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 TIT\u00a051(7), 2554\u20132576 (2005)","journal-title":"IEEE TIT"},{"key":"21_CR6","unstructured":"Clark, D.: Compact Pat Trees. PhD thesis, University of Waterloo (1996)"},{"issue":"6","key":"21_CR7","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1145\/355541.355547","volume":"47","author":"M. Farach-Colton","year":"2000","unstructured":"Farach-Colton, M., Ferragina, P., Muthukrishnan, S.: On the sorting-complexity of suffix tree construction. J. ACM\u00a047(6), 987\u20131011 (2000)","journal-title":"J. ACM"},{"issue":"4","key":"21_CR8","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 texts. J. ACM\u00a052(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"issue":"2","key":"21_CR9","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/1240233.1240243","volume":"3","author":"P. 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), 20 (2007)","journal-title":"ACM Trans. Alg."},{"key":"21_CR10","unstructured":"Gasieniec, L., Kolpakov, R., Potapov, I., Sant, P.: Real-time traversal in grammar-based compressed files. In: Proc. 15th DCC, p. 458 (2005)"},{"issue":"1-2","key":"21_CR11","first-page":"137","volume":"56","author":"L. Gasieniec","year":"2003","unstructured":"Gasieniec, L., Potapov, I.: Time\/space efficient compressed pattern matching. Fund. Inf.\u00a056(1-2), 137\u2013154 (2003)","journal-title":"Fund. Inf."},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Golynski, A., Munro, I., Rao, S.: Rank\/select operations on large alphabets: a tool for text indexing. In: Proc. 17th SODA, pp. 368\u2013373 (2006)","DOI":"10.1145\/1109557.1109599"},{"key":"21_CR13","unstructured":"Grossi, R., Gupta, A., Vitter, J.: High-order entropy-compressed text indexes. In: Proc. 14th SODA, pp. 841\u2013850 (2003)"},{"key":"21_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1007\/3-540-45061-0_73","volume-title":"Automata, Languages and Programming","author":"J. K\u00e4rkk\u00e4inen","year":"2003","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P.: Simple linear work suffix array construction. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 943\u2013955. Springer, Heidelberg (2003)"},{"key":"21_CR15","unstructured":"K\u00e4rkk\u00e4inen, J., Ukkonen, E.: Lempel-Ziv parsing and sublinear-size index structures for string matching. In: Proc. 3rd WSP, pp. 141\u2013155. Carleton University Press (1996)"},{"issue":"2","key":"21_CR16","first-page":"172","volume":"4","author":"M. Karpinski","year":"1997","unstructured":"Karpinski, M., Rytter, W., Shinohara, A.: An efficient pattern-matching algorithm for strings with short descriptions. Nordic J. Comp.\u00a04(2), 172\u2013186 (1997)","journal-title":"Nordic J. Comp."},{"issue":"1","key":"21_CR17","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/S0304-3975(02)00426-7","volume":"298","author":"T. Kida","year":"2003","unstructured":"Kida, T., Matsumoto, T., Shibata, Y., Takeda, M., Shinohara, A., Arikawa, S.: Collage system: a unifying framework for compressed pattern matching. Theor. Comp. Sci.\u00a0298(1), 253\u2013272 (2003)","journal-title":"Theor. Comp. Sci."},{"issue":"3","key":"21_CR18","first-page":"737","volume":"46","author":"J. Kieffer","year":"2000","unstructured":"Kieffer, J., Yang, E.-H.: Grammar-based codes: A new class of universal lossless source codes. IEEE TIT\u00a046(3), 737\u2013754 (2000)","journal-title":"IEEE TIT"},{"issue":"11","key":"21_CR19","doi-asserted-by":"publisher","first-page":"1722","DOI":"10.1109\/5.892708","volume":"88","author":"J. Larsson","year":"2000","unstructured":"Larsson, J., Moffat, A.: Off-line dictionary-based compression. Proc. IEEE\u00a088(11), 1722\u20131732 (2000)","journal-title":"Proc. IEEE"},{"issue":"3","key":"21_CR20","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. Theor. Comp. Sci.\u00a0387(3), 332\u2013347 (2007)","journal-title":"Theor. Comp. Sci."},{"issue":"4","key":"21_CR21","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/321479.321481","volume":"15","author":"D. Morrison","year":"1968","unstructured":"Morrison, D.: PATRICIA \u2013 practical algorithm to retrieve information coded in alphanumeric. J. ACM\u00a015(4), 514\u2013534 (1968)","journal-title":"J. ACM"},{"key":"21_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/3-540-45061-0_29","volume-title":"Automata, Languages and Programming","author":"J. Munro","year":"2003","unstructured":"Munro, J., Raman, R., Raman, V., Rao, S.S.: Succinct representations of permutations. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 345\u2013356. Springer, Heidelberg (2003)"},{"issue":"1","key":"21_CR23","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":"21_CR24","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1216370.1216372","volume":"39","author":"G. Navarro","year":"2007","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Comp. Surv.\u00a039(1), 2 (2007)","journal-title":"ACM Comp. Surv."},{"key":"21_CR25","doi-asserted-by":"crossref","unstructured":"Nevill-Manning, C., Witten, I., Maulsby, D.: Compression by induction of hierarchical grammars. In: Proc. 4th DCC, pp. 244\u2013253 (1994)","DOI":"10.1109\/DCC.1994.305932"},{"key":"21_CR26","unstructured":"Raman, R., Raman, V., Rao, S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proc. 13th SODA, pp. 233\u2013242 (2002)"},{"issue":"4","key":"21_CR27","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s10791-008-9050-3","volume":"11","author":"L. Russo","year":"2008","unstructured":"Russo, L., Oliveira, A.: A compressed self-index using a Ziv-Lempel dictionary. Inf. Retr.\u00a011(4), 359\u2013388 (2008)","journal-title":"Inf. Retr."},{"issue":"1-3","key":"21_CR28","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. Comp. Sci.\u00a0302(1-3), 211\u2013222 (2003)","journal-title":"Theor. Comp. Sci."},{"key":"21_CR29","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":"21_CR30","first-page":"337","volume":"23","author":"J. Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE TIT\u00a023(3), 337\u2013343 (1977)","journal-title":"IEEE TIT"},{"issue":"5","key":"21_CR31","first-page":"530","volume":"24","author":"J. Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable length coding. IEEE TIT\u00a024(5), 530\u2013536 (1978)","journal-title":"IEEE TIT"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03816-7_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T19:57:27Z","timestamp":1739303847000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03816-7_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642038150","9783642038167"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03816-7_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}