Levenstein/edit distance is most often calculated using a dynamic programming (DP) algorithm.

The algorithm goes like this:

1. given 2 strings, s and t
2. instantiate d, an m x n matrix where m = length of s + 1 and n = length of t + 1
3. for each char in s
4. for each char in t
5. set d[i][j] = minimum ( d[i][j-1] + 1, d[i – 1][j] + 1, d[i – 1][j – 1] + cost), where cost = 0 if s.charAt(i) == t.charAt[j] and 1 otherwise

The edit distance is the value of d[length of s][length of t]

http://www.mgilleland.com/ld/ldjavascript.htm has a fantastic visualizer for the algorithm in javascript.

This is the base case for the operations: insert, delete and replace/substitute.

To support adjacent transpositions, we need an additional

int trans	= d[ 0 ][ i - 2 ] + 1;
if ( s.charAt( i - 2 ) != t ) trans++;
if ( s != t.charAt( j - 2 ) ) trans++;
if ( d[i][j] > trans ) d[i][j] = trans;

2 simple optimizations to this algorithm:

1. Instead of storing m x n matrix (which would result in OutOfMemoryErrors for large strings), you can store only the last row of calculations (or the last 2 rows when using transpositions).

2. Apply Ukkonen's cutoff algorithm which reduces table evaluations such that not every row of the matrix need be populated. This algorithm evaluates O(k^2) entries where k = max errors.

Ukkonen's algorithm was published in E. Ukkonen. Finding approximate patterns in strings. Journal of Algo-
rithms, 6:132{7, 1985., but I couldn't find a version of it freely available online. It is, however,described in Tries for Approximate Matching.

The general idea is to start evaluating a row at the previous column's largest value. Read the paper for more details.

No Comments »