ABSTRACT

Approximate string matching is used when a query string is similar to but not identical with desired matches many patterns can be symbolically encoded as strings. Approximate string matching is the process of searching for optimal alignment of two finite-length strings in which comparable patterns may not be obvious; long strings subject to natural variations or random noise, for example, may share subtle, characteristic, underlying patterns of symbols. Use of the term approximate merely emphasizes the fact that a perfect match may not be achievable and that imperfections such as missing and extraneous symbols have to be considered. In many applications, one of the two strings is a prototype string that represents a pattern class and the other is a test string that we wish to analyze and/or classify.