Premium
New and faster filters for multiple approximate string matching
Author(s) -
BaezaYates Ricardo,
Navarro Gonzalo
Publication year - 2002
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10014
Subject(s) - string searching algorithm , algorithm , string (physics) , pattern matching , matching (statistics) , computer science , struct , mathematics , statistics , artificial intelligence , mathematical physics , programming language
We present three new algorithms for on‐line multiple string matching allowing errors. These are extensions of previous algorithms that search for a single pattern. The average running time achieved is in all cases linear in the text size for moderate error level, pattern length, and number of patterns. They adapt (with higher costs) to the other cases. However, the algorithms differ in speed and thresholds of usefulness. We theoretically analyze when each algorithm should be used, and show their performance experimentally. The only previous solution for this problem allows only one error. Our algorithms are the first to allow more errors, and are faster than previous work for a moderate number of patterns (e.g. less than 50–100 on English text, depending on the pattern length). © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 23–49, 2002