{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:17:58Z","timestamp":1725491878422},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540755296"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-75530-2_24","type":"book-chapter","created":{"date-parts":[[2007,9,19]],"date-time":"2007-09-19T10:26:50Z","timestamp":1190197610000},"page":"264-275","source":"Crossref","is-referenced-by-count":3,"title":["Approximate String Matching with Lempel-Ziv Compressed Indexes"],"prefix":"10.1007","author":[{"given":"Lu\u00eds M. S.","family":"Russo","sequence":"first","affiliation":[]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[]},{"given":"Arlindo L.","family":"Oliveira","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"24_CR1","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/375360.375365","volume":"33","author":"G. Navarro","year":"2001","unstructured":"Navarro, G.: A guided tour to approximate string matching. ACM Comput. Surv.\u00a033(1), 31\u201388 (2001)","journal-title":"ACM Comput. Surv."},{"key":"24_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/3-540-58094-8_23","volume-title":"Combinatorial Pattern Matching","author":"W.I. Chang","year":"1994","unstructured":"Chang, W.I., Marr, T.G.: Approximate string matching and local similarity. In: Crochemore, M., Gusfield, D. (eds.) CPM 1994. LNCS, vol.\u00a0807, pp. 259\u2013273. Springer, Heidelberg (1994)"},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"Fredriksson, K., Navarro, G.: Average-optimal single and multiple approximate string matching. ACM Journal of Experimental Algorithmics 9(1.4) (2004)","DOI":"10.1145\/1005813.1041513"},{"issue":"4","key":"24_CR4","first-page":"19","volume":"24","author":"G. Navarro","year":"2001","unstructured":"Navarro, G., Baeza-Yates, R., Sutinen, E., Tarhio, J.: Indexing methods for approximate string matching. IEEE Data Engineering Bulletin\u00a024(4), 19\u201327 (2001)","journal-title":"IEEE Data Engineering Bulletin"},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: STOC, pp. 91\u2013100 (2004)","DOI":"10.1145\/1007352.1007374"},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"Maa\u00df, M., Nowak, J.: Text indexing with errors. In: CPM, pp. 21\u201332 (2005)","DOI":"10.1007\/11496656_3"},{"key":"24_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/11780441_6","volume-title":"Combinatorial Pattern Matching","author":"H.L. Chan","year":"2006","unstructured":"Chan, H.L., Lam, T.W., Sung, W.K., Tam, S.L., Wong, S.S.: A linear size index for approximate pattern matching. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol.\u00a04009, pp. 49\u201359. Springer, Heidelberg (2006)"},{"key":"24_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/11880561_27","volume-title":"String Processing and Information Retrieval","author":"L. Coelho","year":"2006","unstructured":"Coelho, L., Oliveira, A.: Dotted suffix trees: a structure for approximate text indexing. In: Crestani, F., Ferragina, P., Sanderson, M. (eds.) SPIRE 2006. LNCS, vol.\u00a04209, pp. 329\u2013336. Springer, Heidelberg (2006)"},{"key":"24_CR9","first-page":"1","volume-title":"IEEE 14th Annual Symposium on Switching and Automata Theory","author":"P. Weiner","year":"1973","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: IEEE 14th Annual Symposium on Switching and Automata Theory, pp. 1\u201311. IEEE Computer Society Press, Los Alamitos (1973)"},{"key":"24_CR10","doi-asserted-by":"crossref","unstructured":"Manber, U., Myers, E.: Suffix arrays: a new method for on-line string searches. SIAM Journal on Computing, 935\u2013948 (1993)","DOI":"10.1137\/0222058"},{"key":"24_CR11","unstructured":"Gonnet, G.: A tutorial introduction to Computational Biochemistry using Darwin. Technical report, Informatik E.T.H., Zuerich, Switzerland (1992)"},{"key":"24_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/BFb0029808","volume-title":"Combinatorial Pattern Matching","author":"E. Ukkonen","year":"1993","unstructured":"Ukkonen, E.: Approximate string matching over suffix trees. In: Apostolico, A., Crochemore, M., Galil, Z., Manber, U. (eds.) Combinatorial Pattern Matching. LNCS, vol.\u00a0684, pp. 228\u2013242. Springer, Heidelberg (1993)"},{"key":"24_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/3-540-60044-2_33","volume-title":"Combinatorial Pattern Matching","author":"A. Cobbs","year":"1995","unstructured":"Cobbs, A.: Fast approximate matching using suffix trees. In: Galil, Z., Ukkonen, E. (eds.) Combinatorial Pattern Matching. LNCS, vol.\u00a0937, pp. 41\u201354. Springer, Heidelberg (1995)"},{"key":"24_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/3-540-61258-0_4","volume-title":"Combinatorial Pattern Matching","author":"E. Sutinen","year":"1996","unstructured":"Sutinen, E., Tarhio, J.: Filtration with q-samples in approximate string matching. In: Hirschberg, D.S., Meyers, G. (eds.) CPM 1996. LNCS, vol.\u00a01075, pp. 50\u201363. Springer, Heidelberg (1996)"},{"key":"24_CR15","doi-asserted-by":"crossref","unstructured":"Navarro, G., Baeza-Yates, R.: A practical q-gram index for text retrieval allowing errors. CLEI Electronic Journal\u00a01(2) (1998)","DOI":"10.19153\/cleiej.1.2.3"},{"issue":"4\/5","key":"24_CR16","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF01185432","volume":"12","author":"E.W. Myers","year":"1994","unstructured":"Myers, E.W.: A sublinear algorithm for approximate keyword searching. Algorithmica\u00a012(4\/5), 345\u2013374 (1994)","journal-title":"Algorithmica"},{"issue":"1","key":"24_CR17","first-page":"205","volume":"1","author":"G. Navarro","year":"2000","unstructured":"Navarro, G., Baeza-Yates, R.: A hybrid indexing method for approximate string matching. Journal of Discrete Algorithms\u00a01(1), 205\u2013239 (2000)","journal-title":"Journal of Discrete Algorithms"},{"issue":"2-4","key":"24_CR18","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/j.jda.2004.08.003","volume":"3","author":"G. Navarro","year":"2005","unstructured":"Navarro, G., Sutinen, E., Tarhio, J.: Indexing text with approximate q-grams. J. Discrete Algorithms\u00a03(2-4), 157\u2013175 (2005)","journal-title":"J. Discrete Algorithms"},{"issue":"13","key":"24_CR19","doi-asserted-by":"publisher","first-page":"1149","DOI":"10.1002\/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O","volume":"29","author":"S. Kurtz","year":"1999","unstructured":"Kurtz, S.: Reducing the space requirement of suffix trees. Pract. Exper.\u00a029(13), 1149\u20131171 (1999)","journal-title":"Pract. Exper."},{"issue":"2","key":"24_CR20","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1016\/S0196-6774(03)00087-7","volume":"48","author":"K. Sadakane","year":"2003","unstructured":"Sadakane, K.: New text indexing functionalities of the compressed suffix arrays. J. Algorithms\u00a048(2), 294\u2013313 (2003)","journal-title":"J. Algorithms"},{"issue":"4","key":"24_CR21","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P. Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. Journal of the ACM\u00a052(4), 552\u2013581 (2005)","journal-title":"Journal of the ACM"},{"issue":"1","key":"24_CR22","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/S1570-8667(03)00066-2","volume":"2","author":"G. Navarro","year":"2004","unstructured":"Navarro, G.: Indexing text using the Ziv-Lempel trie. J. Discrete Algorithms\u00a02(1), 87\u2013114 (2004)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"24_CR23","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R. Grossi","year":"2005","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput.\u00a035(2), 378\u2013407 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"24_CR24","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1216370.1216372","volume":"39","author":"G. Navarro","year":"2007","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Computing Surveys\u00a039(1) article 2 (2007)","journal-title":"ACM Computing Surveys"},{"issue":"3","key":"24_CR25","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1145\/382780.382782","volume":"48","author":"G. Manzini","year":"2001","unstructured":"Manzini, G.: An analysis of the Burrows-Wheeler transform. Journal of the ACM\u00a048(3), 407\u2013430 (2001)","journal-title":"Journal of the ACM"},{"key":"24_CR26","unstructured":"K\u00e4rkk\u00e4inen, J., Ukkonen, E.: Lempel-Ziv parsing and sublinear-size index structures for string matching. In: South American Workshop on String Processing, pp. 141\u2013155. Carleton University Press (1996)"},{"key":"24_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/11780441_29","volume-title":"Combinatorial Pattern Matching","author":"D. Arroyuelo","year":"2006","unstructured":"Arroyuelo, D., Navarro, G., Sadakane, K.: Reducing the space requirement of LZ-Index. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol.\u00a04009, pp. 318\u2013329. Springer, Heidelberg (2006)"},{"key":"24_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/11880561_14","volume-title":"String Processing and Information Retrieval","author":"L.M.S. Russo","year":"2006","unstructured":"Russo, L.M.S., Oliveira, A.L.: A compressed self-index using a Ziv-Lempel dictionary. In: Crestani, F., Ferragina, P., Sanderson, M. (eds.) SPIRE 2006. LNCS, vol.\u00a04209, pp. 163\u2013180. Springer, Heidelberg (2006)"},{"key":"24_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1007\/978-3-540-27801-6_33","volume-title":"Combinatorial Pattern Matching","author":"T. Huynh","year":"2004","unstructured":"Huynh, T., Hon, W., Lam, T., Sung, W.: Approximate string matching using compressed suffix arrays. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, pp. 434\u2013444. Springer, Heidelberg (2004)"},{"key":"24_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/11602613_35","volume-title":"Algorithms and Computation","author":"T. Lam","year":"2005","unstructured":"Lam, T., Sung, W., Wong, S.: Improved approximate string matching using compressed suffix data structures. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 339\u2013348. Springer, Heidelberg (2005)"},{"key":"24_CR31","unstructured":"Morales, P.: Soluci\u00f3n de consultas complejas sobre un indice de texto comprimido (solving complex queries over a compressed text index). Undergraduate thesis, Dept. of Computer Science, University of Chile, G. Navarro, advisor (2005)"},{"issue":"5","key":"24_CR32","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"},{"issue":"3","key":"24_CR33","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1145\/316542.316550","volume":"46","author":"G. Myers","year":"1999","unstructured":"Myers, G.: A fast bit-vector algorithm for approximate string matching based on dynamic programming. Journal of the ACM\u00a046(3), 395\u2013415 (1999)","journal-title":"Journal of the ACM"},{"key":"24_CR34","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0020-0190(99)00121-0","volume":"72","author":"G. Navarro","year":"1999","unstructured":"Navarro, G., Baeza-Yates, R.: Very fast and simple approximate string matching. Information Processing Letters\u00a072, 65\u201370 (1999)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-75530-2_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:23:20Z","timestamp":1619504600000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-75530-2_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540755296"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-75530-2_24","relation":{},"subject":[]}}