A Guided Tour to Approximate String Matching
We survey the current techniques to cope with the problem of string matching
allowing errors. This is becoming a more and more relevant issue for many
fast growing areas such as information retrieval and computational biology.
We focus on online searching, explaining the problem and its relevance, its
statistical behavior, its history and current developments, and the central
ideas of the algorithms and their complexities. We present a number of
experiments to compare the performance of the different algorithms and show
which are the best choices according to each case. We conclude with some
future work directions and open problems.