{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:14:18Z","timestamp":1725495258887},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540676331"},{"type":"electronic","value":"9783540451235"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45123-4_29","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T14:59:14Z","timestamp":1194965954000},"page":"350-363","source":"Crossref","is-referenced-by-count":26,"title":["Indexing Text with Approximate q-Grams"],"prefix":"10.1007","author":[{"given":"Gonzalo","family":"Navarro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erkki","family":"Sutinen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jani","family":"Tanninen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jorma","family":"Tarhio","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,11,7]]},"reference":[{"key":"29_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-82456-2","volume-title":"Combinatorial Algorithms on Words","author":"A. Apostolico","year":"1985","unstructured":"A. Apostolico and Z. Galil. Combinatorial Algorithms on Words. Springer-Verlag, New York, 1985."},{"unstructured":"M. Ara\u00fajo, G. Navarro, and N. Ziviani. Large text searching allowing errors. In Proc. WSP\u201997, pages 2\u201320. Carleton University Press, 1997.","key":"29_CR2"},{"unstructured":"R. Baeza-Yates. Text retrieval: Theory and practice. In 12th IFIP World Computer Congress, volume I, pages 465\u2013476. Elsevier Science, September 1992.","key":"29_CR3"},{"issue":"2","key":"29_CR4","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/PL00009253","volume":"23","author":"R. Baeza-Yates","year":"1999","unstructured":"R. Baeza-Yates and G. Navarro. Faster approximate string matching. Algorithmica, 23(2):127\u2013158, 1999.","journal-title":"Algorithmica"},{"issue":"1","key":"29_CR5","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1002\/(SICI)1097-4571(2000)51:1<69::AID-ASI10>3.0.CO;2-C","volume":"51","author":"R. Baeza-Yates","year":"2000","unstructured":"R. Baeza-Yates and G. Navarro. Block-addressing indices for approximate text retrieval. J. of the American Society for Information Science (JASIS), 51(1):69\u201382, January 2000.","journal-title":"J. of the American Society for Information Science (JASIS)"},{"key":"29_CR6","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0304-3975(85)90157-4","volume":"40","author":"A. Blumer","year":"1985","unstructured":"A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. Chen, and J. Seiferas. The samllest automaton recognizing the subwords of a text. Theoretical Computer Science, 40:31\u201355, 1985.","journal-title":"Theoretical Computer Science"},{"key":"29_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/3-540-58094-8_23","volume-title":"Proc. CPM\u201994","author":"W. Chang","year":"1994","unstructured":"W. Chang and T. Marr. Approximate string matching and local similarity. In Proc. CPM\u201994, LNCS 807, pages 259\u2013273, 1994."},{"key":"29_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/3-540-60044-2_33","volume-title":"Proc. CPM\u201995","author":"A. Cobbs","year":"1995","unstructured":"A. Cobbs. Fast approximate matching using suffix trees. In Proc. CPM\u201995, pages 41\u201354, 1995. LNCS 937."},{"key":"29_CR9","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0304-3975(86)90041-1","volume":"45","author":"M. Crochemore","year":"1986","unstructured":"M. Crochemore. Transducers and repetitions. Theoretical Computer Science, 45:63\u201386, 1986.","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"M. Farach, P. Ferragina, and S. Muthukrishnan. Overcoming the memory bottleneck in suffix tree construction. In Proc. SODA\u2019 98, pages 174\u2013183, 1998.","key":"29_CR10","DOI":"10.1109\/SFCS.1998.743441"},{"key":"29_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1007\/3-540-48318-7_5","volume-title":"Proc. WAE\u201999","author":"R. Giegerich","year":"1999","unstructured":"R. Giegerich, S. Kurtz, and J. Stoye. Efficient implementation of lazy suffix trees. In Proc. WAE\u201999, LNCS 1668, pages 30\u201342, 1999."},{"key":"29_CR12","volume-title":"Technical report","author":"G. Gonnet","year":"1992","unstructured":"G. Gonnet. A tutorial introduction to Computational Biochemistry using Darwin. Technical report, Informatik E.T.H., Zuerich, Switzerland, 1992."},{"unstructured":"G. Gonnet, R. Baeza-Yates, and T. Snider. Information Retrieval: Data Structures and Algorithms, chapter 3: New indices for text: Pat trees and Pat arrays, pages 66\u201382. Prentice-Hall, 1992.","key":"29_CR13"},{"unstructured":"N. Holsti and E. Sutinen. Approximate string matching using q-gram places. In Proc. 7th Finnish Symposium on Computer Science, pages 23\u201332. University of Joensuu, 1994.","key":"29_CR14"},{"key":"29_CR15","first-page":"240","volume":"16","author":"P. Jokinen","year":"1991","unstructured":"P. Jokinen and E. Ukkonen. Two algorithms for approximate string matching in static texts. In Proc. of MFCS\u201991, volume 16, pages 240\u2013248, 1991.","journal-title":"Proc. of MFCS\u201991"},{"unstructured":"D. Knuth. The Art of Computer Programming, volume 3: Sorting and Searching. Addison-Wesley, 1973.","key":"29_CR16"},{"doi-asserted-by":"crossref","unstructured":"U. Manber and E. Myers. Suffix arrays: a new method for on-line string searches. SIAM Journal on Computing, pages 935\u2013948, 1993.","key":"29_CR17","DOI":"10.1137\/0222058"},{"unstructured":"U. Manber and S. Wu. glimpse: A tool to search through entire file systems. In Proc. USENIX Technical Conference, pages 23\u201332, Winter 1994.","key":"29_CR18"},{"issue":"4\/5","key":"29_CR19","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF01185432","volume":"12","author":"E. Myers","year":"1994","unstructured":"E. Myers. A sublinear algorithm for approximate keyword searching. Algorithmica, 12(4\/5):345\u2013374, Oct\/Nov 1994.","journal-title":"Algorithmica"},{"unstructured":"G. Navarro. A guided tour to approximate string matching. Technical Report TR\/DCC-99-5, Dept. of Computer Science, Univ. of Chile, 1999. To appear in ACM Computing Surveys. ftp:\/\/ftp.dcc.uchile.cl\/pub\/users\/gnavarro\/survasm.ps.gz .","key":"29_CR20"},{"doi-asserted-by":"crossref","unstructured":"G. Navarro and R. Baeza-Yates. A practical q-gram index for text retrieval allowing errors. CLEI Electronic Journal, 1(2), 1998. http:\/\/www.clei.cl.","key":"29_CR21","DOI":"10.19153\/cleiej.1.2.3"},{"key":"29_CR22","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/3-540-48452-3_13","volume-title":"Proc. CPM\u201999","author":"G. Navarro","year":"1999","unstructured":"G. Navarro and R. Baeza-Yates. A new indexing method for approximate string matching. In Proc. CPM\u201999, LNCS 1645, pages 163\u2013186, 1999."},{"key":"29_CR23","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0196-6774(80)90016-4","volume":"1","author":"P. Sellers","year":"1980","unstructured":"P. Sellers. The theory and computation of evolutionary distances: pattern recognition. J. of Algorithms, 1:359\u2013373, 1980.","journal-title":"J. of Algorithms"},{"unstructured":"F. Shi. Fast approximate string matching with q-blocks sequences. In Proc. WSP\u201996, pages 257\u2013271. Carleton University Press, 1996.","key":"29_CR24"},{"key":"29_CR25","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/3-540-61258-0_4","volume-title":"Proc. CPM\u201996","author":"E. Sutinen","year":"1996","unstructured":"E. Sutinen and J. Tarhio. Filtration with q-samples in approximate string matching. In Proc. CPM\u201996, LNCS 1075, pages 50\u201361, 1996."},{"doi-asserted-by":"crossref","unstructured":"E. Ukkonen. Approximate string matching over suffix trees. In Proc. CPM\u201993, pages 228\u2013242, 1993.","key":"29_CR26","DOI":"10.1007\/BFb0029808"},{"doi-asserted-by":"crossref","unstructured":"S. Wu and U. Manber. Fast text searching allowing errors. Comm. of the ACM, 35(10):83\u201391, October 1992.","key":"29_CR27","DOI":"10.1145\/135239.135244"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45123-4_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T06:38:43Z","timestamp":1556951923000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45123-4_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540676331","9783540451235"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-45123-4_29","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}