Damerau Levenshtein
Damerau-Levenshtein is an edit-distance / optimal alignment function. See the wikipedia page on Damerau-Levenshtein for background. It is similar to the Levenshtein function but treats transpositions (swapped letters) as one mistake instead of two:
levenshtein('hello', 'hlelo') = 2
damlev('hello', 'hlelo') = 1
Latest version 2009Nov30 is almost a complete rewrite of the Java code.
Damerau Levenshtein (damlev) for MySQL
Damerau Levenshtein – Levenshtein.java
The Java Levenshtein class (offering also Damerau-Levenshtein methods, perhaps the class name could be better?) is now accessible from the Shipping-Quote.net API. The HTML controls below use the API method to compute the difference between two strings:
String 1:
String 2:
Method:
Limit:
You can see the Damerau Levenshtein API method more easily if your browser can display XML. Here’s an example: http://www.shipping-quote.net/api/string-diff.xml?s1=hello&s2=hlelo&method=damlev
6 Responses to “Damerau Levenshtein”
By tom on Oct 25, 2011 | Reply
wrong algorithm. the damerau levenshtein distance of CA ABC is 2 (swap CA -> AC and insert B after A). your algorithm gives 3.
By Sean on Oct 27, 2011 | Reply
This was pointed out on an older post here – see Alexander’s comments at the bottom:
http://blog.lolyco.com/sean/2008/08/27/damerau-levenshtein-algorithm-levenshtein-with-transpositions/
I still haven’t found the time to read the original article to reassure myself *exactly* what the Damerau-Levenshtein string distance is, so I haven’t changed the code to match the changing Wikipedia article. Thanks for reminding me though! I will try to find the time to do that reading and post an update of some kind.