Match two strings but allow for a degree of error

Question

How can I match two strings, but at the same time allow for X number of characters to be incorrect in the match. The number of errors should be a controllable variable.

While X number of characters can not match in the string there should be a limit as to how many run in a sequence. Given two strings I might allow 5 characters to be different, but not more than 2 in a row.

I'm looking for a recommended algorithm for comparing these two strings, or maybe there is already a known solution for this.

Answer 1

An approximate string search starting point is that of the Levenshtein distance. This algorithim counts the number of single character edits (insert, delete, and substitution) to change one word into another.

An example of this is kitten --> sitting which has an edit distance of three

1. kitten -> sitten (substitute 's' for 'k')
2. sitten -> sittin (substitute 'i' for 'e')
3. sittin -> sitting (add 'g' at the end)

There are variations on this algorithm, notably the Damerau–Levenshtein distance which allows for the transposition of two adjacent characters ('hte' to 'the' has a DL Distance of 1 and a Levenshtein distance of 2) and thus is often more appropriate for spell checking. Other variations exist for applications where gaps are important (DNA strings).

The Levenshtein distance is well known and not too difficult to find (I once had cause to hunt up an implementation of it as a function in oracle - it was much faster than pulling down all the data and then running the query code side). Rosettacode has a multitude (54) of implemntations of the Levenshtein distance (note that some languages have this as part of the string library somewhere - if you are doing Java, look at the apache commons lang). Wikibooks has 31 implementations and a cursory glance at the two do not show the same code for the same language.

The way this works is it builds up a matrix that corresponds to the relationship between the two strings:

 .kitten
.0123456
s1123456
i2212345
t3321234
t4432123
i5543223
n6654332
g7765443

The . row and column represent that you can get to the target string by 'just' inserting each letter from a empty string. This isn't the ideal case, but it is there to seed the algorithm.

If the value is the same that spot ('i' == 'i'), the value is the same as value diagonally up to the left. If the two spots are dissimilar ('s' != 'k') the value is the the minimum of:

• diagonal up and to the left + 1 (a substitution)
• directly above + 1 (an insertion)
• directly to the left + 1 (a deletion)

The edit distance return value is the value in the lower right of the matrix.

If you follow from the lower right to the upper left with the minimum, you can see the edits done:

 .kitten
.0.   .
s.1   .
i  1  .
t   1 .
t    1.
i.....2
n      2
g......3

Do note that this is the rather memory intensive approach. It can be reduced in memory scope by not building the full matrix - all the algorithm cares about is a subset of the data and it can be reduced from N*M space to 2*max(N,M) space by just storing the the previous row (and what has been calculated on the current row). Code Project shows how this can be done (with C# code to download).