{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T12:25:05Z","timestamp":1765974305104},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642389047"},{"type":"electronic","value":"9783642389054"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38905-4_6","type":"book-chapter","created":{"date-parts":[[2013,5,16]],"date-time":"2013-05-16T03:28:54Z","timestamp":1368674934000},"page":"38-49","source":"Crossref","is-referenced-by-count":7,"title":["Converting SLP to LZ78 in almost Linear Time"],"prefix":"10.1007","author":[{"given":"Hideo","family":"Bannai","sequence":"first","affiliation":[]},{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"additional","affiliation":[]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[]},{"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"6_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/3-540-45022-X_8","volume-title":"Automata, Languages and Programming","author":"S. Alstrup","year":"2000","unstructured":"Alstrup, S., Holm, J.: Improved algorithms for finding level ancestors in dynamic trees. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 73\u201384. Springer, Heidelberg (2000)"},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/978-3-642-34109-0_10","volume-title":"String Processing and Information Retrieval","author":"H. Bannai","year":"2012","unstructured":"Bannai, H., Inenaga, S., Takeda, M.: Efficient LZ78 factorization of grammar compressed text. In: Calder\u00f3n-Benavides, L., Gonz\u00e1lez-Caro, C., Ch\u00e1vez, E., Ziviani, N. (eds.) SPIRE 2012. LNCS, vol.\u00a07608, pp. 86\u201398. Springer, Heidelberg (2012)"},{"key":"6_CR3","unstructured":"Cole, R., Hariharan, R.: Dynamic LCA queries on trees. In: Proc. SODA 1999, pp. 235\u2013244 (1999)"},{"issue":"6","key":"6_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":"6_CR5","first-page":"316","volume-title":"DCC 1999: Proceedings of the Conference on Data Compression","author":"L. Gasieniec","year":"1999","unstructured":"Gasieniec, L., Rytter, W.: Almost optimal fully LZW-compressed pattern matching. In: DCC 1999: Proceedings of the Conference on Data Compression, p. 316. IEEE Computer Society, Washington, DC (1999)"},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/978-3-642-34109-0_24","volume-title":"String Processing and Information Retrieval","author":"P. Gawrychowski","year":"2012","unstructured":"Gawrychowski, P.: Faster algorithm for computing the edit distance between SLP-compressed strings. In: Calder\u00f3n-Benavides, L., Gonz\u00e1lez-Caro, C., Ch\u00e1vez, E., Ziviani, N. (eds.) SPIRE 2012. LNCS, vol.\u00a07608, pp. 229\u2013236. Springer, Heidelberg (2012)"},{"key":"6_CR7","unstructured":"Gawrychowski, P.: Tying up the loose ends in fully LZW-compressed pattern matching. In: Proc. STACS 2012, pp. 624\u2013635 (2012)"},{"key":"6_CR8","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.jda.2012.07.006","volume":"18","author":"K. Goto","year":"2013","unstructured":"Goto, K., Bannai, H., Inenaga, S., Takeda, M.: Fast q-gram mining on SLP compressed strings. Journal of Discrete Algorithms\u00a018, 89\u201399 (2013)","journal-title":"Journal of Discrete Algorithms"},{"key":"6_CR9","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":"6_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/978-3-642-31594-7_45","volume-title":"Automata, Languages, and Programming","author":"A. Je\u017c","year":"2012","unstructured":"Je\u017c, A.: Faster fully compressed pattern matching by recompression. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 533\u2013544. Springer, Heidelberg (2012)"},{"key":"6_CR11","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"},{"issue":"11","key":"6_CR12","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"},{"issue":"12","key":"6_CR13","doi-asserted-by":"publisher","first-page":"3250","DOI":"10.1109\/TIT.2004.838101","volume":"50","author":"M. Li","year":"2004","unstructured":"Li, M., Chen, X., Li, X., Ma, B., Vit\u00e1nyi, P.M.B.: The similarity metric. IEEE Transactions on Information Theory\u00a050(12), 3250\u20133264 (2004)","journal-title":"IEEE Transactions on Information Theory"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Li, M., Sleep, R.: Genre classification via an LZ78-based string kernel. In: Proc. ISMIR 2005, pp. 252\u2013259 (2005)","DOI":"10.1007\/11527503_80"},{"key":"6_CR15","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1007\/11527503_80","volume-title":"Advanced Data Mining and Applications","author":"M. Li","year":"2005","unstructured":"Li, M., Sleep, R.: An LZ78 based string kernel. In: Li, X., Wang, S., Dong, Z.Y. (eds.) ADMA 2005. LNCS (LNAI), vol.\u00a03584, pp. 678\u2013689. Springer, Heidelberg (2005)"},{"key":"6_CR16","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1007\/11731139_81","volume-title":"Advances in Knowledge Discovery and Data Mining","author":"M. Li","year":"2006","unstructured":"Li, M., Zhu, Y.: Image classification via LZ78 based string kernel: A comparative study. In: Ng, W.-K., Kitsuregawa, M., Li, J., Chang, K. (eds.) PAKDD 2006. LNCS (LNAI), vol.\u00a03918, pp. 704\u2013712. Springer, Heidelberg (2006)"},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-540-73437-6_24","volume-title":"Combinatorial Pattern Matching","author":"Y. Lifshits","year":"2007","unstructured":"Lifshits, Y.: Processing compressed texts: A tractability border. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 228\u2013240. Springer, Heidelberg (2007)"},{"issue":"1","key":"6_CR18","first-page":"187","volume":"1","author":"M. Miyazaki","year":"2000","unstructured":"Miyazaki, M., Shinohara, A., Takeda, M.: An improved pattern matching algorithm for strings in terms of straight-line programs. Journal of Discrete Algorithms\u00a01(1), 187\u2013204 (2000)","journal-title":"Journal of Discrete Algorithms"},{"key":"6_CR19","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)","DOI":"10.1109\/DCC.1994.305932"},{"issue":"1-3","key":"6_CR20","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\u00a0302(1-3), 211\u2013222 (2003)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"6_CR21","first-page":"370","volume":"42","author":"M. Takeda","year":"2001","unstructured":"Takeda, M., Shibata, Y., Matsumoto, T., Kida, T., Shinohara, A., Fukamachi, S., Shinohara, T., Arikawa, S.: Speeding up string pattern matching by text compression: The dawn of a new era. Transactions of Information Processing Society of Japan\u00a042(3), 370\u2013384 (2001)","journal-title":"Transactions of Information Processing Society of Japan"},{"key":"6_CR22","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":"3","key":"6_CR23","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 Transactions on Information Theory IT-23(3), 337\u2013349 (1977)","journal-title":"IEEE Transactions on Information Theory IT"},{"issue":"5","key":"6_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-38905-4_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,13]],"date-time":"2019-07-13T21:36:15Z","timestamp":1563053775000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38905-4_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642389047","9783642389054"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38905-4_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}