{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:40:15Z","timestamp":1775281215928,"version":"3.50.1"},"reference-count":40,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2003,4,1]],"date-time":"2003-04-01T00:00:00Z","timestamp":1049155200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3760,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2003,4]]},"DOI":"10.1016\/s0304-3975(02)00426-7","type":"journal-article","created":{"date-parts":[[2003,3,26]],"date-time":"2003-03-26T01:16:11Z","timestamp":1048641371000},"page":"253-272","source":"Crossref","is-referenced-by-count":61,"title":["Collage system: a unifying framework for compressed pattern matching"],"prefix":"10.1016","volume":"298","author":[{"given":"Takuya","family":"Kida","sequence":"first","affiliation":[]},{"given":"Tetsuya","family":"Matsumoto","sequence":"additional","affiliation":[]},{"given":"Yusuke","family":"Shibata","sequence":"additional","affiliation":[]},{"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[]},{"given":"Ayumi","family":"Shinohara","sequence":"additional","affiliation":[]},{"given":"Setsuo","family":"Arikawa","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(02)00426-7_BIB1","doi-asserted-by":"crossref","unstructured":"A. Amir, G. Benson, Efficient two-dimensional compressed matching, in: Proc. Data Compression Conference, 1992, p. 279.","DOI":"10.1109\/DCC.1992.227453"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB2","unstructured":"A. Amir, G. Benson, Two-dimensional periodicity and its application, in: Proc. of the 3rd Ann. ACM-SIAM Symp. on Discrete Algorithms, 1992, pp. 440\u2013452."},{"key":"10.1016\/S0304-3975(02)00426-7_BIB3","doi-asserted-by":"crossref","unstructured":"A. Amir, G. Benson, M. Farach, Optimal two-dimensional compressed matching, in: Proc. 21st Internat. Colloq. on Automata, Languages and Programming, 1994, pp. 215\u2013226.","DOI":"10.1007\/3-540-58201-0_70"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB4","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1006\/jcss.1996.0023","article-title":"Let sleeping files lie","volume":"52","author":"Amir","year":"1996","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"10.1016\/S0304-3975(02)00426-7_BIB5","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/0196-6774(92)90003-U","article-title":"Efficient pattern matching with scaling","volume":"13","author":"Amir","year":"1992","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB6","series-title":"Pattern Matching Algorithm","author":"Apostolico","year":"1997"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB7","series-title":"Text Algorithms","author":"Crochemore","year":"1994"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB8","doi-asserted-by":"crossref","unstructured":"E.S. de Moura, G. Navarro, N. Ziviani, R. Baeza-Yates, Direct pattern matching on compressed text, in: Proc. 5th Internat. Symp. on String Processing and Information Retrieval, IEEE Computer Society, Silver Spring, MD, 1998, pp. 90\u201395.","DOI":"10.1109\/SPIRE.1998.712987"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB9","doi-asserted-by":"crossref","unstructured":"E.S. de Moura, G. Navarro, N. Ziviani, R. Baeza-Yates, Fast searching on compressed texts allowing errors, in: Proc. 21st Ann. Internat. ACM SIGIR Conf. on Research and Development in Information Retrieval, ACM Press, New York, 1998, pp. 298\u2013306.","DOI":"10.1145\/290941.291013"},{"issue":"3","key":"10.1016\/S0304-3975(02)00426-7_BIB10","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0304-3975(88)90112-0","article-title":"Matching patterns in strings subject to multi-linear transformations","volume":"60","author":"Eilam-Tzoreff","year":"1988","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(02)00426-7_BIB11","doi-asserted-by":"crossref","unstructured":"M. Farach, M. Thorup, String-matching in Lempel\u2013Ziv compressed strings, in: 27th ACM STOC, 1995, pp. 703\u2013713.","DOI":"10.1145\/225058.225288"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB12","doi-asserted-by":"crossref","unstructured":"L. Ga\u0327sieniec, M. Karpinski, W. Plandowski, W. Rytter, Efficient algorithms for Lempel\u2013Ziv encoding, in: Proc. 4th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, Vol. 1097, Springer, Berlin, 1996, pp. 392\u2013403.","DOI":"10.1007\/3-540-61422-2_148"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB13","doi-asserted-by":"crossref","unstructured":"L. Gasieniec, M. Karpinski, W. Plandowski, W. Rytter, Efficient algorithms for Lempel\u2013Ziv encoding, in: Proc. 5th Scandinavian Workshop on Algorithm Theory, 1996, pp. 392\u2013403.","DOI":"10.1007\/3-540-61422-2_148"},{"issue":"3","key":"10.1016\/S0304-3975(02)00426-7_BIB14","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/PL00009177","article-title":"From Ukkonen to McCreight and Weiner","volume":"19","author":"Giegerich","year":"1997","journal-title":"Algorithmica"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB15","doi-asserted-by":"crossref","unstructured":"L.C.K. Hui, Color set size problem with application to string matching, in: Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 644, Springer, Berlin, 1992, pp. 230\u2013243.","DOI":"10.1007\/3-540-56024-6_19"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB16","doi-asserted-by":"crossref","unstructured":"J. K\u00e4rkk\u00e4inen, G. Navarro, E. Ukkonen, Approximate string matching over Ziv-Lempel compressed text, in: Proc. 11th Ann. Symp. on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 1848, Springer, Berlin, 2000, pp. 195\u2013209.","DOI":"10.1007\/3-540-45123-4_18"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB17","first-page":"172","article-title":"An efficient pattern-matching algorithm for strings with short descriptions","volume":"4","author":"Karpinski","year":"1997","journal-title":"Nordic J. Comput."},{"key":"10.1016\/S0304-3975(02)00426-7_BIB18","doi-asserted-by":"crossref","unstructured":"T. Kida, M. Takeda, A. Shinohara, S. Arikawa, Shift-And approach to pattern matching in LZW compressed text, in: Proc. 10th Ann. Symp. on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 1645, Springer, Berlin, 1999, pp. 1\u201313.","DOI":"10.1007\/3-540-48452-3_1"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB19","series-title":"Proc. Data Compression Conf. \u201998","first-page":"103","article-title":"Multiple pattern matching in LZW compressed text","author":"Kida","year":"1998"},{"issue":"1","key":"10.1016\/S0304-3975(02)00426-7_BIB20","first-page":"133","article-title":"Multiple pattern matching in LZW compressed text","volume":"1","author":"Kida","year":"2000","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"10.1016\/S0304-3975(02)00426-7_BIB21","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1109\/18.841160","article-title":"Grammar-based codes","volume":"46","author":"Kieffer","year":"2000","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"4","key":"10.1016\/S0304-3975(02)00426-7_BIB22","doi-asserted-by":"crossref","first-page":"1227","DOI":"10.1109\/18.850665","article-title":"Universal lossless compression via multilevel pattern matching","volume":"46","author":"Kieffer","year":"2000","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"2","key":"10.1016\/S0304-3975(02)00426-7_BIB23","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","article-title":"Fast pattern matching in strings","volume":"6","author":"Knuth","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(02)00426-7_BIB24","doi-asserted-by":"crossref","unstructured":"S. Kosaraju, Pattern matching in compressed texts, in: Proc. Foundation of Software Technology and Theoretical Computer Science, Springer, Berlin, 1995, pp. 349\u2013362.","DOI":"10.1007\/3-540-60692-0_60"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB25","doi-asserted-by":"crossref","unstructured":"N.J. Larsson, A. Moffat, Offline dictionary-based compression, in: Proc. Data Compression Conf. \u201999, IEEE Computer Society, Silver Spring, MD, 1999, pp. 296\u2013305.","DOI":"10.1109\/DCC.1999.755679"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB26","doi-asserted-by":"crossref","unstructured":"T. Matsumoto, T. Kida, M. Takeda, A. Shinohara, S. Arikawa, Bit-parallel approach to approximate string matching in compressed texts, in: Proc. 7th Internat. Symp. on String Processing and Information Retrieval, IEEE Computer Society, Silver Spring, MD, 2000, pp. 221\u2013228.","DOI":"10.1109\/SPIRE.2000.878198"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB27","doi-asserted-by":"crossref","unstructured":"M. Miyazaki, A. Shinohara, M. Takeda, An improved pattern matching algorithm for strings in terms of straight-line programs, in: Proc. 8th Ann. Symp. on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 1264, Springer, Berlin, 1997, pp. 1\u201311.","DOI":"10.1007\/3-540-63220-4_45"},{"issue":"1","key":"10.1016\/S0304-3975(02)00426-7_BIB28","first-page":"187","article-title":"An improved pattern matching algorithm for strings in terms of straight-line programs","volume":"1","author":"Miyazaki","year":"2000","journal-title":"J. Discrete Algorithms"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB29","doi-asserted-by":"crossref","unstructured":"G. Navarro, M. Raffinot, A general practical approach to pattern matching over Ziv-Lempel compressed text, in: Proc. 10th Ann. Symp. on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 1645, Springer, Berlin, 1999, pp. 14\u201336.","DOI":"10.1007\/3-540-48452-3_2"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB30","series-title":"The Data Compression Book","author":"Nelson","year":"1992"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB31","doi-asserted-by":"crossref","unstructured":"C.G. Nevill-Manning, I.H. Witten, D.L. Maulsby, Compression by induction of hierarchical grammars, in: Proc. Data Compression Conf. \u201994, IEEE Press, New York, 1994, pp. 244\u2013253.","DOI":"10.1109\/DCC.1994.305932"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB32","doi-asserted-by":"crossref","unstructured":"Y. Shibata, T. Kida, S. Fukamachi, M. Takeda, A. Shinohara, T. Shinohara, S. Arikawa, Speeding up pattern matching by text compression, in: Proc. 4th Italian Conf. on Algorithms and Complexity, Lecture Notes in Computer Science, Vol. 1767, Springer, Berlin, 2000, pp. 306\u2013315.","DOI":"10.1007\/3-540-46521-9_25"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB33","doi-asserted-by":"crossref","unstructured":"Y. Shibata, T. Matsumoto, M. Takeda, A. Shinohara, S. Arikawa, A Boyer\u2013Moore type algorithm for compressed pattern matching, in: Proc. 11th Ann. Symp. on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 1848, Springer, Berlin, 2000, pp. 181\u2013194.","DOI":"10.1007\/3-540-45123-4_17"},{"key":"10.1016\/S0304-3975(02)00426-7_BIB34","doi-asserted-by":"crossref","unstructured":"Y. Shibata, M. Takeda, A. Shinohara, S. Arikawa, Pattern matching in text compressed by using antidictionaries, in: Proc. 10th Ann. Symp. on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 1645, Springer, Berlin, 1999, pp. 37\u201349.","DOI":"10.1007\/3-540-48452-3_3"},{"issue":"4","key":"10.1016\/S0304-3975(02)00426-7_BIB35","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1145\/322344.322346","article-title":"Data compression via textual substitution","volume":"29","author":"Storer","year":"1982","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0304-3975(02)00426-7_BIB36","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/MC.1984.1659158","article-title":"A technique for high performance data compression","volume":"17","author":"Welch","year":"1984","journal-title":"IEEE Comput."},{"key":"10.1016\/S0304-3975(02)00426-7_BIB37","unstructured":"S. Wu, U. Manber, Agrep\u2014a fast approximate pattern-matching tool, in: Usenix Winter 1992 Technical Conference, 1992, pp. 153\u2013162."},{"issue":"3","key":"10.1016\/S0304-3975(02)00426-7_BIB38","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1109\/18.841161","article-title":"Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform","volume":"46","author":"Yang","year":"2000","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"5","key":"10.1016\/S0304-3975(02)00426-7_BIB39","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","article-title":"Compression of individual sequences via variable-length coding","volume":"24","author":"Ziv","year":"1978","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"3","key":"10.1016\/S0304-3975(02)00426-7_BIB40","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for sequential data compression","volume":"IT-23","author":"Ziv","year":"1997","journal-title":"IEEE Trans. Inform. Theory"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397502004267?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397502004267?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,12]],"date-time":"2020-03-12T16:57:10Z","timestamp":1584032230000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397502004267"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,4]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,4]]}},"alternative-id":["S0304397502004267"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(02)00426-7","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2003,4]]}}}