Levenshtein Distance

I spent the weekend working on implementing a few string comparison algorithms for mailcheck and decided to share one of the easiest ones to implement, the Levenshtein distance algorithm.

The Levenshtein distance is calculated as the fewest number of deletions, insertions, or substitutions required to transform one string into another (If you add the transposition operation, you get the Damerau–Levenshtein distance, and if you allow only substitution you get the Hammng distance.) Turns out implementation is a simple dynamic programming exercise because the Levenshtein distance can easily be calculated for various length substrings of each of the two strings being compared.

Take a look at the data structure containing the substring edit distance in action with strings of your choosing here.

The javascript implementation I came up with is as follows for your your perusing pleasure: