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
sitting which has an edit distance of three
- kitten -> sitten (substitute 's' for 'k')
- sitten -> sittin (substitute 'i' for 'e')
- 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:
. 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:
i 1 .
t 1 .
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).