String Matching
In particular, string edit distance can be used to measure the similarity of objects which are presented in terms of strings. Sting edit distance is based on a set of edit operations, for example, the insertion, deletion, and substitution of individual symbols in a string. Often a cost is assigned to each edit operation to model its likelihood of occurrence. Given a set of edit operations together with their costs, the edit distance d(x; y) of two strings, x and y, is defined as the minimum cost token over all sequences of edit operations that transform x into y.
The standard algorithm for computing d(x; y), where x = x1...xn and y = y1...ym, is based on dynamic programming [74]. It computes the elements of a two-dimensional edit matrix D(i; j) of dimension (n + 1) * (m + 1) using the following simple algorithm: