{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T21:51:31Z","timestamp":1743112291410,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319238258"},{"type":"electronic","value":"9783319238265"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-23826-5_25","type":"book-chapter","created":{"date-parts":[[2015,9,4]],"date-time":"2015-09-04T08:20:20Z","timestamp":1441354820000},"page":"258-269","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Online Self-Indexed Grammar Compression"],"prefix":"10.1007","author":[{"given":"Yoshimasa","family":"Takabatake","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yasuo","family":"Tabei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroshi","family":"Sakamoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,9,5]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","first-page":"313","DOI":"10.3233\/FI-2011-565","volume":"111","author":"F Claude","year":"2010","unstructured":"Claude, F., Navarro, G.: Self-indexed grammar-based compression. Fundam. Inform. 111, 313\u2013337 (2010)","journal-title":"Fundam. Inform."},{"key":"25_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-642-34109-0_19","volume-title":"String Processing and Information Retrieval","author":"F Claude","year":"2012","unstructured":"Claude, F., Navarro, G.: Improved grammar-based compressed indexes. In: Calder\u00f3n-Benavides, L., Gonz\u00e1lez-Caro, C., Ch\u00e1vez, E., Ziviani, N. (eds.) SPIRE 2012. LNCS, vol. 7608, pp. 180\u2013192. Springer, Heidelberg (2012)"},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"Genomes Project Consortium: A map of human genome variation from population-scale sequencing. Nature 467, 1061\u20131073 (2010)","DOI":"10.1038\/nature09534"},{"key":"25_CR4","doi-asserted-by":"publisher","first-page":"2:1","DOI":"10.1145\/1186810.1186812","volume":"3","author":"G Cormode","year":"2007","unstructured":"Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. TALG 3, 2:1\u20132:19 (2007)","journal-title":"TALG"},{"key":"25_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-642-28332-1_21","volume-title":"Language and Automata Theory and Applications","author":"T Gagie","year":"2012","unstructured":"Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Nekrich, Y., Puglisi, S.J.: A faster grammar-based self-index. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 240\u2013251. Springer, Heidelberg (2012)"},{"key":"25_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/978-3-642-54423-1_63","volume-title":"LATIN 2014: Theoretical Informatics","author":"T Gagie","year":"2014","unstructured":"Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Nekrich, Y., Puglisi, S.J.: LZ77-based self-indexing with faster pattern matching. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 731\u2013742. Springer, Heidelberg (2014)"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Golynski, A., Munro, J.I., Rao, S.S.: Rank\/select operations on large alphabets: a tool for text indexing. In: SODA, pp. 368\u2013373 (2006)","DOI":"10.1145\/1109557.1109599"},{"key":"25_CR8","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: SODA, pp. 636\u2013645 (2003)"},{"key":"25_CR9","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: FOCS, pp. 549\u2013554 (1989)","DOI":"10.1007\/978-1-4612-3694-8_36"},{"key":"25_CR10","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. Nord. J. of Comp. 4, 172\u2013186 (1997)","journal-title":"Nord. J. of Comp."},{"key":"25_CR11","first-page":"100","volume":"18","author":"S Maruyama","year":"2013","unstructured":"Maruyama, S., Nakahara, M., Kishiue, N., Sakamoto, H.: ESP-Index: A compressed index based on edit-sensitive parsing. JDA 18, 100\u2013112 (2013)","journal-title":"JDA"},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"Maruyama, S., Tabei, Y.: Fully-online grammar compression in constant space. In: DCC, pp. 218\u2013229 (2014)","DOI":"10.1007\/978-3-319-02432-5_25"},{"key":"25_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/978-3-319-02432-5_25","volume-title":"String Processing and Information Retrieval","author":"S Maruyama","year":"2013","unstructured":"Maruyama, S., Tabei, Y., Sakamoto, H., Sadakane, K.: Fully-online grammar compression. In: Kurland, O., Lewenstein, M., Porat, E. (eds.) SPIRE 2013. LNCS, vol. 8214, pp. 218\u2013229. Springer, Heidelberg (2013)"},{"issue":"1","key":"25_CR14","first-page":"87","volume":"2","author":"G Navarro","year":"2004","unstructured":"Navarro, G.: Indexing text using the Ziv-Lempel tire. JDA 2(1), 87\u2013114 (2004)","journal-title":"JDA"},{"key":"25_CR15","doi-asserted-by":"crossref","unstructured":"Navarro, G.: Implementing the LZ-index: Theory versus practice. ACM Journal of Experimental Algorithmics 13 Article No. 1.2 (2008)","DOI":"10.1145\/1412228.1412230"},{"key":"25_CR16","unstructured":"Navarro, G., Sadakane, K.: Fully-functional static and dynamic succinct trees. ACM Transactions on Algorithms (2012). Accepted. A preliminary version appeared in SODA 2010"},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. TALG 3 (2007)","DOI":"10.1145\/1290672.1290680"},{"issue":"1\u20133","key":"25_CR18","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. Theoretical Computer Science 302(1\u20133), 211\u2013222 (2003)","journal-title":"Theoretical Computer Science"},{"key":"25_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1007\/978-3-319-07959-2_29","volume-title":"Experimental Algorithms","author":"Y Takabatake","year":"2014","unstructured":"Takabatake, Y., Tabei, Y., Sakamoto, H.: Improved ESP-index: a practical self-index for highly repetitive texts. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 338\u2013350. Springer, Heidelberg (2014)"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-23826-5_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,21]],"date-time":"2023-01-21T00:02:27Z","timestamp":1674259347000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-23826-5_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319238258","9783319238265"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-23826-5_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"5 September 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}