{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T20:54:48Z","timestamp":1776113688836,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642389047","type":"print"},{"value":"9783642389054","type":"electronic"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38905-4_23","type":"book-chapter","created":{"date-parts":[[2013,5,16]],"date-time":"2013-05-16T03:28:54Z","timestamp":1368674934000},"page":"235-246","source":"Crossref","is-referenced-by-count":13,"title":["A Succinct Grammar Compression"],"prefix":"10.1007","author":[{"given":"Yasuo","family":"Tabei","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoshimasa","family":"Takabatake","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroshi","family":"Sakamoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Apostolico, A., Lonardi, S.: Off-line Compression by Greedy Textual Substitution. Proceedings of the IEEE\u00a088, 1733\u20131744 (2000)","DOI":"10.1109\/5.892709"},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"Asai, T., Abe, K., Kawasoe, S., Arimura, H., Sakamoto, H., Arikawa, S.: Efficient Substructure Discovery from Large Semi-structured Data. In: SDM, pp. 158\u2013174 (2002)","DOI":"10.1137\/1.9781611972726.10"},{"key":"23_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-642-17514-5_27","volume-title":"Algorithms and Computation","author":"J. Barbay","year":"2010","unstructured":"Barbay, J., Gagie, T., Navarro, G., Nekrich, Y.: Alphabet Partitioning for Compressed Rank\/Select and Applications. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part II. LNCS, vol.\u00a06507, pp. 315\u2013326. Springer, Heidelberg (2010)"},{"key":"23_CR4","unstructured":"Barbay, J., Navarro, G.: Compressed Representations of Permutations, and Applications. In: STACS, pp. 111\u2013122 (2009)"},{"key":"23_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/978-3-540-73951-7_13","volume-title":"Algorithms and Data Structures","author":"F.C. Botelho","year":"2007","unstructured":"Botelho, F.C., Pagh, R., Ziviani, N.: Simple and Space-Efficient Minimal Perfect Hash Functions. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol.\u00a04619, pp. 139\u2013150. Springer, Heidelberg (2007)"},{"key":"23_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. Inform. Theory\u00a051, 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"23_CR7","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, 313\u2013337 (2011)","journal-title":"Fundam. Inform."},{"key":"23_CR8","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2006.12.012","volume":"372","author":"P. Ferragina","year":"2007","unstructured":"Ferragina, P., Venturini, R.: A simple storage scheme for strings achieving entropy bounds. Theor. Comput. Sci.\u00a0372, 115\u2013121 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"23_CR9","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/S0020-0190(02)00288-0","volume":"84","author":"F.V. Fomin","year":"2002","unstructured":"Fomin, F.V., Kratsch, D., Novelli, J.-C.: Approximating minimum cocolorings. Inf. Process. Lett.\u00a084, 285\u2013290 (2002)","journal-title":"Inf. Process. Lett."},{"key":"23_CR10","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":"23_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/11780441_27","volume-title":"Combinatorial Pattern Matching","author":"R. Gonz\u00e1lez","year":"2006","unstructured":"Gonz\u00e1lez, R., Navarro, G.: Statistical Encoding of Succinct Data Structures. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol.\u00a04009, pp. 294\u2013305. Springer, Heidelberg (2006)"},{"key":"23_CR12","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: SODA, pp. 841\u2013850 (2003)"},{"key":"23_CR13","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"},{"key":"23_CR14","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1016\/j.jcss.2011.09.002","volume":"78","author":"J. Jansson","year":"2012","unstructured":"Jansson, J., Sadakane, K., Sung, W.-K.: Ultra-succinct representation of ordered trees with applications. J. Comput. Syst. Sci.\u00a078, 619\u2013631 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1007\/978-3-642-31594-7_43","volume-title":"Automata, Languages, and Programming","author":"J. Jansson","year":"2012","unstructured":"Jansson, J., Sadakane, K., Sung, W.-K.: CRAM: Compressed Random Access Memory. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 510\u2013521. Springer, Heidelberg (2012)"},{"key":"23_CR16","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Miller, R.E., Rosenberg, A.L.: Rapid Identification of Repeated Patterns in Strings, Trees and Arrays. In: STOC, pp. 125\u2013136 (1972)","DOI":"10.1145\/800152.804905"},{"key":"23_CR17","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R.M. Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient Randomized Pattern-Matching Algorithms. IBM Journal of Research and Development\u00a031, 249\u2013260 (1987)","journal-title":"IBM Journal of Research and Development"},{"key":"23_CR18","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, 172\u2013186 (1997)","journal-title":"Nordic J. Comp."},{"key":"23_CR19","doi-asserted-by":"crossref","unstructured":"Larsson, N.J., Moffat, A.: Offline Dictionary-Based Compression. In: DCC, pp. 296\u2013305 (1999)","DOI":"10.1109\/DCC.1999.755679"},{"key":"23_CR20","unstructured":"Lehman, E.: Approximation Algorithms for Grammar-Based Compression. PhD thesis, MIT (2002)"},{"key":"23_CR21","unstructured":"Lehman, E., Shelat, A.: Approximation algorithms for grammar-based compression. In: SODA, pp. 205\u2013212 (2002)"},{"key":"23_CR22","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)"},{"key":"23_CR23","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/j.jda.2012.07.009","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. J. Discrete Algorithms\u00a018, 100\u2013112 (2013)","journal-title":"J. Discrete Algorithms"},{"key":"23_CR24","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, 213\u2013235 (2012)","journal-title":"Algorithms"},{"key":"23_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/978-3-642-31265-6_2","volume-title":"Combinatorial Pattern Matching","author":"G. Navarro","year":"2012","unstructured":"Navarro, G.: Wavelet Trees for All. In: K\u00e4rkk\u00e4inen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol.\u00a07354, pp. 2\u201326. Springer, Heidelberg (2012)"},{"key":"23_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-642-30850-5_26","volume-title":"Experimental Algorithms","author":"G. Navarro","year":"2012","unstructured":"Navarro, G., Providel, E.: Fast, small, simple rank\/Select on bitmaps. In: Klasing, R. (ed.) SEA 2012. LNCS, vol.\u00a07276, pp. 295\u2013306. Springer, Heidelberg (2012)"},{"key":"23_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":"23_CR28","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":"23_CR29","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":"23_CR30","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Grossi, R.: Squeezing succinct data structures into entropy bounds. In: SODA, pp. 1230\u20131239 (2006)","DOI":"10.1145\/1109557.1109693"},{"key":"23_CR31","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\u00a03, 416\u2013430 (2005)","journal-title":"J. Discrete Algorithms"},{"key":"23_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1007\/978-3-642-34109-0_42","volume-title":"String Processing and Information Retrieval","author":"Y. Takabatake","year":"2012","unstructured":"Takabatake, Y., Tabei, Y., Sakamoto, H.: Variable-Length Codes for Space-Efficient Grammar-Based Compression. In: Calder\u00f3n-Benavides, L., Gonz\u00e1lez-Caro, C., Ch\u00e1vez, E., Ziviani, N. (eds.) SPIRE 2012. LNCS, vol.\u00a07608, pp. 398\u2013410. Springer, Heidelberg (2012)"},{"key":"23_CR33","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/s002360050126","volume":"35","author":"R.B. Yehuda","year":"1998","unstructured":"Yehuda, R.B., Fogel, S.: Partitioning a Sequence into Few Monotone Subsequences. Acta. Inf.\u00a035, 421\u2013440 (1998)","journal-title":"Acta. Inf."},{"key":"23_CR34","doi-asserted-by":"crossref","unstructured":"Zaki, M.J.: Efficiently mining frequent trees in a forest. In: KDD, pp. 71\u201380 (2002)","DOI":"10.1145\/775047.775058"},{"key":"23_CR35","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. Inform. Theory\u00a023, 337\u2013343 (1977)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"23_CR36","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, 530\u2013536 (1978)","journal-title":"IEEE Trans. Inform. Theory"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38905-4_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,26]],"date-time":"2020-07-26T20:20:47Z","timestamp":1595794847000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38905-4_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642389047","9783642389054"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38905-4_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}