{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:23:06Z","timestamp":1759638186174},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671596"},{"type":"electronic","value":"9783540465218"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46521-9_25","type":"book-chapter","created":{"date-parts":[[2007,11,3]],"date-time":"2007-11-03T18:47:16Z","timestamp":1194115636000},"page":"306-315","source":"Crossref","is-referenced-by-count":28,"title":["Speeding Up Pattern Matching by Text Compression"],"prefix":"10.1007","author":[{"given":"Yusuke","family":"Shibata","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takuya","family":"Kida","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuichi","family":"Fukamachi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ayumi","family":"Shinohara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takeshi","family":"Shinohara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Setsuo","family":"Arikawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,2,14]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195113679.001.0001","volume-title":"Pattern Matching Algorithm","author":"A. Apostolico","year":"1997","unstructured":"A. Apostolico and Z. Galil. Pattern Matching Algorithm. Oxford University Press, New York, 1997."},{"issue":"1-2","key":"25_CR2","doi-asserted-by":"crossref","first-page":"101","DOI":"10.5109\/13361","volume":"21","author":"S. Arikawa","year":"1984","unstructured":"S. Arikawa and S. Shiraishi. Pattern matching machines for replacing several character strings. Bulletin of Informatics and Cybernetics, 21(1-2):101\u2013111, 1984.","journal-title":"Bulletin of Informatics and Cybernetics"},{"issue":"10","key":"25_CR3","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1145\/135239.135243","volume":"35","author":"R. Baeza-Yates","year":"1992","unstructured":"R. Baeza-Yates and G. H. Gonnet. A new approach to text searching. Comm. ACM, 35(10):74\u201382, 1992.","journal-title":"Comm. ACM"},{"issue":"10","key":"25_CR4","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1145\/359842.359859","volume":"20","author":"R. S. Boyer","year":"1977","unstructured":"R. S. Boyer and J. S. Moore. A fast string searching algorithm. Comm. ACM, 20(10):62\u201372, 1977.","journal-title":"Comm. ACM"},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"D. Breslauer. Saving comparisons in the Crochemore-Perrin string matching algorithm. In Proc. of 1st European Symp. on Algorithms, pages 61\u201372, 1993.","DOI":"10.1007\/3-540-57273-2_44"},{"issue":"4\/5","key":"25_CR6","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF01185427","volume":"12","author":"M. Crochemore","year":"1994","unstructured":"M. Crochemore, A. Czumaj, L. Gasieniec, S. Jarominek, T. Lecroq, W. Plandowski, and W. Rytter. Speeding up two string-matching algorithm. Algorithmica, 12(4\/5):247\u2013267, 1994.","journal-title":"Algorithmica"},{"issue":"3","key":"25_CR7","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1145\/116825.116845","volume":"38","author":"M. Crochemore","year":"1991","unstructured":"M. Crochemore and D. Perrin. Two-way string-matching. J. ACM, 38(3):651\u2013675, 1991.","journal-title":"J. ACM"},{"key":"25_CR8","volume-title":"Text Algorithms","author":"M. Crochemore","year":"1994","unstructured":"M. Crochemore and W. Rytter. Text Algorithms. Oxford University Press, New York, 1994."},{"key":"25_CR9","doi-asserted-by":"crossref","unstructured":"E. S. de Moura, G. Navarro, N. Ziviani, and R. Baeza-Yates. Direct pattern matching on compressed text. In Proc. 5th International Symp. on String Processing and Information Retrieval, pages 90\u201395. IEEE Computer Society, 1998.","DOI":"10.1109\/SPIRE.1998.712987"},{"key":"25_CR10","unstructured":"P. Gage. A new algorithm for data compression. The C Users Journal, 12(2), 1994."},{"issue":"3","key":"25_CR11","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1016\/0022-0000(83)90002-8","volume":"26","author":"Z. Galil","year":"1983","unstructured":"Z. Galil and J. Seiferas. Time-space-optimal string matching. J. Comput. System Sci., 26(3):280\u2013294, 1983.","journal-title":"J. Comput. System Sci."},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"L. Gasieniec, W. Plandowski, and W. Rytter. Constant-space string matching with smaller number of comparisons: Sequential sampling. In Proc. 6th Ann. Symp. on Combinatorial Pattern Matching, pages 78\u201389. Springer-Verlag, 1995.","DOI":"10.1007\/3-540-60044-2_36"},{"issue":"1\/2","key":"25_CR13","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0304-3975(94)00249-I","volume":"147","author":"L. Gasieniec","year":"1995","unstructured":"L. Gasieniec, W. Plandowski, and W. Rytter. The zooming method: a recursive approach to time-space efficient string-matching. Theoret. Comput. Sci, 147(1\/2):19\u201330, 1995.","journal-title":"Theoret. Comput. Sci"},{"key":"25_CR14","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1002\/spe.4380100608","volume":"10","author":"R. N. Horspool","year":"1980","unstructured":"R. N. Horspool. Practical fast searching in strings. Software-Practice and Experience, 10:501\u2013506, 1980.","journal-title":"Software-Practice and Experience"},{"key":"25_CR15","unstructured":"G. C. Jewell. Text compaction for information retrieval. IEEE SMC Newsletter, 5, 1976."},{"key":"25_CR16","doi-asserted-by":"crossref","unstructured":"T. Kida, Y. Shibata, M. Takeda, A. Shinohara, and S. Arikawa. A unifying framework for compressed pattern matching. In Proc. 6th International Symp. on String Processing and Information Retrieval, pages 89\u201396. IEEE Computer Society, 1999.","DOI":"10.1109\/SPIRE.1999.796582"},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"T. Kida, M. Takeda, A. Shinohara, and S. Arikawa. Shift-And approach to pattern matching in LZW compressed text. In Proc. 10th Ann. Symp. on Combinatorial Pattern Matching, pages 1\u201313. Springer-Verlag, 1999.","DOI":"10.1007\/3-540-48452-3_1"},{"key":"25_CR18","doi-asserted-by":"crossref","unstructured":"T. Kida, M. Takeda, A. Shinohara, M. Miyazaki, and S. Arikawa. Multiple pattern matching in LZW compressed text. In J. A. Atorer and M. Cohn, editors, Proc. Data Compression Conference '98, pages 103\u2013112. IEEE Computer Society, 1998.","DOI":"10.1109\/DCC.1998.672136"},{"issue":"2","key":"25_CR19","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D. E. Knuth","year":"1977","unstructured":"D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAM J. Comput, 6(2):323\u2013350, 1977.","journal-title":"SIAM J. Comput"},{"key":"25_CR20","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/3-540-58094-8_10","volume-title":"Proc. Combinatorial Pattern Matching","author":"U. Manber","year":"1994","unstructured":"U. Manber. A text compression scheme that allows fast searching directly in the compressed file. In Proc. Combinatorial Pattern Matching, volume 807 of Lecture Notes in Computer Science, pages 113\u2013124. Springer-Verlag, 1994."},{"key":"25_CR21","doi-asserted-by":"crossref","unstructured":"G. Navarro and M. Raffiot. A general practical approach to pattern matching over Ziv-Lempel compressed text. In Proc. 10th Ann. Symp. on Combinatorial Pattern Matching, pages 14\u201336. Springer-Verlag, 1999.","DOI":"10.1007\/3-540-48452-3_2"},{"issue":"8","key":"25_CR22","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1145\/79173.79184","volume":"33","author":"D. M. Sunday","year":"1990","unstructured":"D. M. Sunday. A very fast substring search algorithm. Comm. ACM, 33(8):132\u2013142, 1990.","journal-title":"Comm. ACM"},{"key":"25_CR23","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/B978-0-12-037102-0.50013-3","volume":"2","author":"M. Takeda","year":"1990","unstructured":"M. Takeda. An efficient multiple string replacing algorithm using patterns with pictures. Advances in Software Science and Technology, 2:131\u2013151, 1990.","journal-title":"Advances in Software Science and Technology"},{"issue":"2","key":"25_CR24","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0167-6423(96)00008-1","volume":"27","author":"B. W. Watson","year":"1996","unstructured":"B. W. Watson and G. Zwaan. A taxonomy of sublinear multiple keyword pattern matching algorithms. Sci. of Comput. Programing., 27(2):85\u2013118, 1996.","journal-title":"Sci. of Comput. Programing."},{"key":"25_CR25","unstructured":"S. Wu and U. Manber. Agrep-a fast approximate pattern-matching tool. In Usenix Winter 1992 Technical Conference, pages 153\u2013162, 1992."},{"issue":"10","key":"25_CR26","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1145\/135239.135244","volume":"35","author":"S. Wu","year":"1992","unstructured":"S. Wu and U. Manber. Fast text searching allowing errors. Comm. ACM, 35(10):83\u201391, October 1992.","journal-title":"Comm. ACM"},{"issue":"3","key":"25_CR27","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1137\/0208029","volume":"8","author":"A. C.-C. Yao","year":"1979","unstructured":"A. C.-C. Yao. The complexity of pattern matching for a random string. SIAM J. Comput., 8(3):368\u2013387, 1979.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46521-9_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,26]],"date-time":"2021-08-26T13:47:26Z","timestamp":1629985646000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46521-9_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671596","9783540465218"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-46521-9_25","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}