Fast text searching with errors

Searching for a pattern in a text file is a very common operation in many applications ranging from text editors and databases to applications in molecular biology. In many instances the pat-tern does not appear in the text exactly. Errors in the text or in the query can result from misspel-ling or from experimental errors (e.g., when the text is a DNA sequence). The use of such approximate pattern matching has been limited until now to specific applications. Most text edi-tors and searching programs do not support searching with errors because of the complexity involved in implementing it. In this paper we present a new algorithm for approximate text searching which is very fast and very flexible. We believe that the new algorithm will find its way to many searching applications and will enable searching with errors to be just as common as searching exactly. 1