A guided tour to approximate string matching

We survey the current techniques to cope with the problem of string matchin g that allows errors. This is becoming a more and more relevant issue for m any fast growing areas such as information retrieval and computational biol ogy. We focus on online searching and mostly on edit distance, explaining t he problem and its relevance, its statistical behavior, its history and cur rent developments, and the central ideas of the algorithms and their comple xities. We present a number of experiments to compare the performance of th e different algorithms and show which are the best choices. We conclude wit h some directions for future work and open problems.