Archive for the ‘Damerau-Levenshtein Edit Distance’ Category

Damerau-Levenshtein Edit Distance

Saturday, September 22nd, 2012

Damerau-Levenshtein Edit Distance by Kevin Stern.

From the post:

The Damerau-Levenshtein distance admits all of the operations from the Levenshtein distance and further allows for swapping of adjacent characters, with the caveat that cost of two adjacent character swaps be at least the cost of a character deletion plus the cost of a character insertion (this caveat enables a fast dynamic programming solution to the problem). There is a sub-variant of the Damerau-Levenshtein distance known as the restricted edit distance which further specifies that no substring be modified more than once, which is primarily what I found when searching for algorithms for computing Damerau-Levenshtein distance, since, I presume, this sub-variant is a bit more straight forward to compute. In addition, I’ve had a difficult time finding a good explanation of the algorithm for computing the full Damerau-Levenshtein distance – hence, the motivation behind this blog post.

A variation on the Levenshtein edit distance algorithm that you may find useful.

I first saw this at DZone.