Approximate Boyer–Moore String Matching
Jorma Tarhio, Esko Ukkonen · SIAM Journal on Computing · 1993
The Boyer–Moore idea applied in exact string matching is generalized to approximate string matching. Two versions of the problem are considered. The k mismatches problem is to find all approximate occurrences of a pattern string (length m) in a text string (length n) with at most k mismatches. The generalized Boyer–Moore algorithm is shown (under a mild independence assumption) to solve the problem in expected time $O(kn({1 / {(m - k) + ({k / c})}}))$, where c is the size of the alphabet. A related algorithm is developed for the k differences problem, where the task is to find all approximate occurrences of a pattern in a text with $ \leqslant k$ differences (insertions, deletions, changes). Experimental evaluation of the algorithms is reported, showing that the new algorithms are often significantly faster than the old ones. Both algorithms are functionally equivalent with the Horspool version of the Boyer–Moore algorithm when $k = 0$.
Cited by 85 works. doi:10.1137/0222018
Authors
References
- An introduction to probability theory and its applications
- An Introduction to Probability Theory and Its Applications, Vol. 2
- The String-to-String Correction Problem
- Fast Pattern Matching in Strings
- Efficient string matching
- A fast string searching algorithm
- The theory and computation of evolutionary distances: Pattern recognition
- Algorithms for approximate string matching
- Finding approximate patterns in strings
- Fast parallel and serial approximate string matching