{"id":304,"date":"2009-04-16T10:53:36","date_gmt":"2009-04-16T02:53:36","guid":{"rendered":"http:\/\/blog.lolyco.com\/sean\/?page_id=304"},"modified":"2016-05-11T05:14:38","modified_gmt":"2016-05-10T21:14:38","slug":"damerau-levenshtein","status":"publish","type":"page","link":"https:\/\/blog.lolyco.com\/sean\/damerau-levenshtein\/","title":{"rendered":"Damerau Levenshtein"},"content":{"rendered":"<p>Damerau-Levenshtein is an edit-distance \/ optimal alignment function. See the <a title=\"Damerau Levensthein at Wikipedia\" href=\"http:\/\/en.wikipedia.org\/wiki\/Damerau\u2013Levenshtein_distance\">wikipedia page on Damerau-Levenshtein<\/a> for background. It is similar to the <a title=\"Levenshtein \/ optimal string alignment\" href=\"http:\/\/en.wikipedia.org\/wiki\/Optimal_string_alignment\">Levenshtein function<\/a> but treats transpositions (swapped letters) as one mistake instead of two:<\/p>\n<p><code>levenshtein('hello', 'hlelo') = 2<br \/>\ndamlev('hello', 'hlelo') = 1<\/code><\/p>\n<p>Latest version 2009Nov30 is almost a <a href=\"http:\/\/blog.lolyco.com\/sean\/2009\/11\/30\/damerau-levenshtein-java-methods-updated\/\">complete rewrite of the Java code<\/a>.<\/p>\n<p><a href=\"http:\/\/blog.lolyco.com\/sean\/wp-content\/uploads\/2009\/04\/damlev.zip\">Damerau Levenshtein (damlev) for MySQL<\/a><\/p>\n<p><a href=\"http:\/\/blog.lolyco.com\/sean\/wp-content\/uploads\/2009\/04\/Levenshtein.java_.zip\">Damerau Levenshtein &#8211; Levenshtein.java<\/a><\/p>\n<p>The Java Levenshtein class (offering also Damerau-Levenshtein methods, perhaps the class name could be better?) is now <a href=\"http:\/\/www.firtl.com\/sandpit\/api\/string-diff.json?s1=hlelo&amp;s2=jello&amp;method=damlev&amp;limit=3\">accessible from the Firtl.com sandpit API as JSON<\/a> <a href=\"http:\/\/www.firtl.com\/sandpit\/api\/string-diff.xml?s1=hlelo&amp;s2=jello&amp;method=damlev&amp;limit=3\">and as XML<\/a>. The HTML controls below use the API method to compute the difference between two strings:<\/p>\n<p><script src=\"http:\/\/www.firtl.com\/sandpit\/js\/stringdiffwidget.js\" type=\"text\/javascript\"><\/script><\/p>\n<table style=\"border-style: none;\">\n<tbody>\n<tr>\n<td><label for=\"sqNetString1\">String 1:<\/label><\/td>\n<td><input id=\"sqNetString1\" size=\"10\" type=\"text\" value=\"hello\" \/><\/td>\n<\/tr>\n<tr>\n<td><label for=\"sqNetString2\">String 2:<\/label><\/td>\n<td><input id=\"sqNetString2\" size=\"10\" type=\"text\" value=\"hlelo\" \/><\/td>\n<\/tr>\n<tr>\n<td><label for=\"sqNetMethod\">Method:<\/label><\/td>\n<td><select id=\"sqNetMethod\"><option selected=\"selected\" value=\"lev\">Levenshtein<\/option><option value=\"damlev\">Damerau-Levenshtein<\/option><\/select><\/td>\n<\/tr>\n<tr>\n<td><label for=\"sqNetLimit\">Limit:<\/label><\/td>\n<td><select id=\"sqNetLimit\"><option selected=\"selected\" value=\"999\">No limit<\/option><option value=\"1\">1<\/option><option value=\"2\">2<\/option><option value=\"3\">3<\/option><\/select><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div id=\"sqStringDiffResult\" style=\"clear: left;\"><\/div>\n<p>You can see the Damerau Levenshtein API method more easily if your browser can display XML. Here&#8217;s an example: <a title=\"See XML string diff for 'hello' and 'hlelo' using Damerau Levenshtein\" href=\"http:\/\/www.firtl.com\/sandpit\/api\/string-diff.xml?s1=hello&amp;s2=hlelo&amp;method=damlev\">http:\/\/www.firtl.com\/sandpit\/api\/string-diff.xml?s1=hello&amp;s2=hlelo&amp;method=damlev<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>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(&#8216;hello&#8217;, &#8216;hlelo&#8217;) = 2 damlev(&#8216;hello&#8217;, &#8216;hlelo&#8217;) = 1 Latest version 2009Nov30 is almost a complete rewrite of the Java code. Damerau [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"footnotes":""},"class_list":["post-304","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/pages\/304","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/comments?post=304"}],"version-history":[{"count":40,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/pages\/304\/revisions"}],"predecessor-version":[{"id":1667,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/pages\/304\/revisions\/1667"}],"wp:attachment":[{"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/media?parent=304"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}