Approximate String Matching
-- An Introduction
Finding close matches to words in text,
searching a database for entries, and homology (similarity) searches on DNA
sequences are but a few of the applications of string matching, which extends
to many instances of Pattern Recognition problems. The problem of
approximate string matching can be formalized as the problem of finding in
a given text of length n all text positions which match a pattern
p of length m with up to k errors, where allowed errors
are character deletions, insertions and substitution. Less formally, this
can be viewed as the problem of transforming a part of the input text to obtain
p using k insertion, deletion and substitution operations.
The error level
is defined to be a = k/m, for
which typical values range from 0.1 to 0.3.
The fastest classical algorithm for low error levels is a
filtration algorithm
, and as such its performance degrades quickly as error levels are increased.
The algorithm shown here improves upon previous techniques for finding potential
matches, and improves the filter for biased texts such as natural languages
. These new features allow the algorithm to continues to perform well even
on moderate error levels, making it the fastest algorithm in the field for
string matching in all "interesting" cases.