{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:03:30Z","timestamp":1725455010386},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642341083"},{"type":"electronic","value":"9783642341090"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34109-0_42","type":"book-chapter","created":{"date-parts":[[2012,9,13]],"date-time":"2012-09-13T11:14:53Z","timestamp":1347534893000},"page":"398-410","source":"Crossref","is-referenced-by-count":3,"title":["Variable-Length Codes for Space-Efficient Grammar-Based 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","reference":[{"key":"42_CR1","unstructured":"Barbay, J., Navarro, G.: Compressed Representations of Permutations, and Applications. In: STACS, pp. 111\u2013122 (2009)"},{"key":"42_CR2","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":"42_CR3","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\u00a051, 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"42_CR4","unstructured":"Clark, D.: Compact Pat Trees. PhD thesis, University of Waterloo (1996)"},{"issue":"3","key":"42_CR5","doi-asserted-by":"crossref","first-page":"313","DOI":"10.3233\/FI-2011-565","volume":"111","author":"F. Claude","year":"2011","unstructured":"Claude, F., Navarro, G.: Self-indexed grammar-based compression. Fundam. Inform.\u00a0111(3), 313\u2013337 (2011)","journal-title":"Fundam. Inform."},{"key":"42_CR6","first-page":"463","volume":"2","author":"P. Erd\u0151s","year":"1935","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry. Compositio Mathematica\u00a02, 463\u2013470 (1935)","journal-title":"Compositio Mathematica"},{"key":"42_CR7","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Venturini, R.: A simple storage scheme for strings achieving entropy bounds. In: SODA, pp. 690\u2013696 (2007)","DOI":"10.1016\/j.tcs.2006.12.012"},{"key":"42_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/978-3-642-24583-1_27","volume-title":"String Processing and Information Retrieval","author":"K. Goto","year":"2011","unstructured":"Goto, K., Bannai, H., Inenaga, S., Takeda, M.: Fast q-gram Mining on SLP\u00a0Compressed\u00a0Strings. In: Grossi, R., Sebastiani, F., Silvestri, F. (eds.) SPIRE 2011. LNCS, vol.\u00a07024, pp. 278\u2013289. Springer, Heidelberg (2011)"},{"key":"42_CR9","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: SODA, pp. 636\u2013645 (2003)"},{"key":"42_CR10","unstructured":"Hermelin, D., Landau, G.M., Landau, S., Weimann, O.: A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression. In: STACS, pp. 26\u201328 (2009)"},{"key":"42_CR11","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: FOCS, pp. 549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"issue":"2","key":"42_CR12","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":"11","key":"42_CR13","doi-asserted-by":"publisher","first-page":"1722","DOI":"10.1109\/5.892708","volume":"88","author":"N.J. Larsson","year":"2000","unstructured":"Larsson, N.J., Moffat, A.: Off-line dictionary-based compression. Proceedings of the IEEE\u00a088(11), 1722\u20131732 (2000)","journal-title":"Proceedings of the IEEE"},{"key":"42_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1007\/978-3-642-24583-1_39","volume-title":"String Processing and Information Retrieval","author":"S. Maruyama","year":"2011","unstructured":"Maruyama, S., Nakahara, M., Kishiue, N., Sakamoto, H.: ESP-Index: A Compressed Index Based on Edit-Sensitive Parsing. In: Grossi, R., Sebastiani, F., Silvestri, F. (eds.) SPIRE 2011. LNCS, vol.\u00a07024, pp. 398\u2013409. Springer, Heidelberg (2011)"},{"issue":"2","key":"42_CR15","doi-asserted-by":"publisher","first-page":"213","DOI":"10.3390\/a5020214","volume":"5","author":"S. Maruyama","year":"2012","unstructured":"Maruyama, S., Sakamoto, H., Takeda, M.: An online algorithm for lightweight grammar-based compression. Algorithms\u00a05(2), 213\u2013235 (2012)","journal-title":"Algorithms"},{"key":"42_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/3-540-62034-6_35","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"J.I. Munro","year":"1996","unstructured":"Munro, J.I.: Tables. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol.\u00a01180, pp. 37\u201342. Springer, Heidelberg (1996)"},{"key":"42_CR17","unstructured":"Okanohara, D.: dag_vector, https:\/\/github.com\/pfi\/dag_vector"},{"key":"42_CR18","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: SODA, pp. 233\u2013242 (2002)"},{"key":"42_CR19","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.\u00a0302, 211\u2013222 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"42_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/978-3-540-30213-1_33","volume-title":"String Processing and Information Retrieval","author":"H. Sakamoto","year":"2004","unstructured":"Sakamoto, H., Kida, T., Shimozono, S.: A Space-Saving Linear-Time Algorithm for Grammar-Based Compression. In: Apostolico, A., Melucci, M. (eds.) SPIRE 2004. LNCS, vol.\u00a03246, pp. 218\u2013229. Springer, Heidelberg (2004)"},{"issue":"2","key":"42_CR21","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1587\/transinf.E92.D.158","volume":"92","author":"H. Sakamoto","year":"2009","unstructured":"Sakamoto, H., Maruyama, S., Kida, T., Shimozono, S.: A space-saving approximation algorithm for grammar-based compression. IEICE Trans. Inf. Syst.\u00a092(2), 158\u2013165 (2009)","journal-title":"IEICE Trans. Inf. Syst."},{"key":"42_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/978-3-642-20712-9_32","volume-title":"Computer Science \u2013 Theory and Applications","author":"A. Tiskin","year":"2011","unstructured":"Tiskin, A.: Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol.\u00a06651, pp. 401\u2013414. Springer, Heidelberg (2011)"},{"key":"42_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/978-3-642-21458-5_27","volume-title":"Combinatorial Pattern Matching","author":"T. Yamamoto","year":"2011","unstructured":"Yamamoto, T., Bannai, H., Inenaga, S., Takeda, M.: Faster Subsequence and Don\u2019t-Care Pattern Matching on Compressed Texts. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.\u00a06661, pp. 309\u2013322. Springer, Heidelberg (2011)"},{"issue":"5","key":"42_CR24","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. Inform. Theory\u00a024(5), 530\u2013536 (1978)","journal-title":"IEEE Trans. Inform. Theory"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-34109-0_42.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:45:19Z","timestamp":1620132319000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34109-0_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642341083","9783642341090"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34109-0_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}