{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,30]],"date-time":"2025-03-30T23:10:14Z","timestamp":1743376214937,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642312649"},{"type":"electronic","value":"9783642312656"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31265-6_18","type":"book-chapter","created":{"date-parts":[[2012,6,12]],"date-time":"2012-06-12T03:28:23Z","timestamp":1339471703000},"page":"220-231","source":"Crossref","is-referenced-by-count":6,"title":["Speeding Up q-Gram Mining on Grammar-Based Compressed Texts"],"prefix":"10.1007","author":[{"given":"Keisuke","family":"Goto","sequence":"first","affiliation":[]},{"given":"Hideo","family":"Bannai","sequence":"additional","affiliation":[]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[]},{"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"18_CR1","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.tcs.2003.05.002","volume":"321","author":"M.A. Bender","year":"2004","unstructured":"Bender, M.A., Farach-Colton, M.: The level ancestor problem simplified. Theor. Comput. Sci.\u00a0321(1), 5\u201312 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"18_CR2","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/S0022-0000(05)80002-9","volume":"48","author":"O. Berkman","year":"1994","unstructured":"Berkman, O., Vishkin, U.: Finding level-ancestors in trees. J. Comput. System Sci.\u00a048(2), 214\u2013230 (1994)","journal-title":"J. Comput. System Sci."},{"issue":"3","key":"18_CR3","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. Fundamenta Informaticae\u00a0111(3), 313\u2013337 (2011)","journal-title":"Fundamenta Informaticae"},{"issue":"6","key":"18_CR4","doi-asserted-by":"publisher","first-page":"1654","DOI":"10.1137\/S0097539702402007","volume":"32","author":"M. Crochemore","year":"2003","unstructured":"Crochemore, M., Landau, G.M., Ziv-Ukelson, M.: A subquadratic sequence alignment algorithm for unrestricted scoring matrices. SIAM J. Comput.\u00a032(6), 1654\u20131673 (2003)","journal-title":"SIAM J. Comput."},{"key":"18_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/BFb0028247","volume-title":"Algorithms and Data Structures","author":"P. Dietz","year":"1991","unstructured":"Dietz, P.: Finding Level-Ancestors in Dynamic Trees. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1991. LNCS, vol.\u00a0519, pp. 32\u201340. Springer, Heidelberg (1991)"},{"doi-asserted-by":"crossref","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Compressing and indexing labeled trees, with applications. J. ACM\u00a057(1) (2009)","key":"18_CR6","DOI":"10.1145\/1613676.1613680"},{"key":"18_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/978-3-642-23719-5_36","volume-title":"Algorithms \u2013 ESA 2011","author":"P. Gawrychowski","year":"2011","unstructured":"Gawrychowski, P.: Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 421\u2013432. Springer, Heidelberg (2011)"},{"unstructured":"G\u0105sieniec, L., Kolpakov, R., Potapov, I., Sant, P.: Real-time traversal in grammar-based compressed files. In: Proc. DCC 2005, p. 458 (2005)","key":"18_CR8"},{"key":"18_CR9","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)"},{"unstructured":"Hermelin, D., Landau, G.M., Landau, S., Weimann, O.: A unified algorithm for accelerating edit-distance computation via text-compression. In: Proc. STACS 2009, pp. 529\u2013540 (2009)","key":"18_CR10"},{"issue":"2","key":"18_CR11","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1142\/S0129054112400126","volume":"23","author":"S. Inenaga","year":"2012","unstructured":"Inenaga, S., Bannai, H.: Finding characteristic substrings from compressed texts. International Journal of Foundations of Computer Science\u00a023(2), 261\u2013280 (2012); a preliminary version appeared in PSC 2009","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"6","key":"18_CR12","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J. K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. Journal of the ACM\u00a053(6), 918\u2013936 (2006)","journal-title":"Journal of the ACM"},{"key":"18_CR13","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 Journal of Computing\u00a04, 172\u2013186 (1997)","journal-title":"Nordic Journal of Computing"},{"key":"18_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-48194-X_17","volume-title":"Combinatorial Pattern Matching","author":"T. Kasai","year":"2001","unstructured":"Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. In: Amir, A., Landau, G.M. (eds.) CPM 2001. LNCS, vol.\u00a02089, pp. 181\u2013192. Springer, Heidelberg (2001)"},{"unstructured":"Kimura, D., Kashima, H.: A linear time subpath kernel for trees. IEICE Technical Report, IBISML2011-85, pp. 291\u2013298 (2011)","key":"18_CR15"},{"doi-asserted-by":"crossref","unstructured":"Larsson, N.J., Moffat, A.: Offline dictionary-based compression. In: Proc. DCC 1999, pp. 296\u2013305. IEEE Computer Society (1999)","key":"18_CR16","DOI":"10.1109\/DCC.1999.755679"},{"doi-asserted-by":"crossref","unstructured":"Nevill-Manning, C.G., Witten, I.H., Maulsby, D.L.: Compression by induction of hierarchical grammars. In: Proc. DCC 1994, pp. 244\u2013253 (1994)","key":"18_CR17","DOI":"10.1109\/DCC.1994.305932"},{"issue":"1-3","key":"18_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. Theor. Comput. Sci.\u00a0302(1-3), 211\u2013222 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"18_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/3-540-46521-9_25","volume-title":"Algorithms and Complexity","author":"Y. Shibata","year":"2000","unstructured":"Shibata, Y., Kida, T., Fukamachi, S., Takeda, M., Shinohara, A., Shinohara, T., Arikawa, S.: Speeding Up Pattern Matching by Text Compression. In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol.\u00a01767, pp. 306\u2013315. Springer, Heidelberg (2000)"},{"issue":"5","key":"18_CR20","first-page":"1061","volume":"E86-A","author":"T. Shibuya","year":"2003","unstructured":"Shibuya, T.: Constructing the suffix tree of a tree with a large alphabet. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences\u00a0E86-A(5), 1061\u20131066 (2003)","journal-title":"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"},{"issue":"4","key":"18_CR21","doi-asserted-by":"publisher","first-page":"928","DOI":"10.1145\/322344.322346","volume":"29","author":"J. Storer","year":"1982","unstructured":"Storer, J., Szymanski, T.: Data compression via textual substitution. Journal of the ACM\u00a029(4), 928\u2013951 (1982)","journal-title":"Journal of the ACM"},{"key":"18_CR22","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1109\/MC.1984.1659158","volume":"17","author":"T.A. Welch","year":"1984","unstructured":"Welch, T.A.: A technique for high performance data compression. IEEE Computer\u00a017, 8\u201319 (1984)","journal-title":"IEEE Computer"},{"issue":"3","key":"18_CR23","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"IT-23","author":"J. Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Transactions on Information Theory\u00a0IT-23(3), 337\u2013349 (1977)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"5","key":"18_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-length coding. IEEE Transactions on Information Theory\u00a024(5), 530\u2013536 (1978)","journal-title":"IEEE Transactions on Information Theory"}],"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-31265-6_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,30]],"date-time":"2025-03-30T22:42:58Z","timestamp":1743374578000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31265-6_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642312649","9783642312656"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31265-6_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}