{"id":147,"date":"2008-10-03T17:01:07","date_gmt":"2008-10-03T09:01:07","guid":{"rendered":"http:\/\/blog.lolyco.com\/sean\/?p=147"},"modified":"2009-04-16T11:13:34","modified_gmt":"2009-04-16T03:13:34","slug":"damerau-levenshtein-in-java","status":"publish","type":"post","link":"https:\/\/blog.lolyco.com\/sean\/2008\/10\/03\/damerau-levenshtein-in-java\/","title":{"rendered":"Damerau-Levenshtein in Java"},"content":{"rendered":"<p>When I wrote about the <a title=\"Damerau Levenshtein MySQL UDF article\" href=\"http:\/\/blog.lolyco.com\/sean\/2008\/08\/27\/damerau-levenshtein-algorithm-levenshtein-with-transpositions\/\">Damerau Levenshtein MySQL UDF (User Defined Function)<\/a> I explained that I prototyped the functions in Java first. I had a request for the Java code, but when I looked at it, realised that I only used it half way, and then made finishing touches to the C code directly.<\/p>\n<p>Here is my Levenshtein.java, a class containing 3 static methods: lev(String, String) &#8211; the standard Levenshtein function, levlim(String, String, int) &#8211; an optimised Levenshtein that returns as soon as the distance between the two words grows beyond a limit, and damlev(String, String) &#8211; Damerau-Levenshtein distance between the two words.<\/p>\n<p>The class has a main function, so you can run it directly. Besides the limit optimisation on levlim(), there&#8217;s no real optimisation done anywhere, so there should be plenty to go at. In particular, a new rectangular array is created on each invocation of any of the methods.<\/p>\n<p>Possibly the most important thing to warn is this: I&#8217;ve only used this code for testing ideas, and <span style=\"color: #ff0000;\"><strong>it has never been used in any application!<\/strong><\/span><\/p>\n<p><span style=\"text-decoration: line-through;\">So, fill your boots, <a href=\"http:\/\/blog.lolyco.com\/sean\/wp-content\/uploads\/2008\/10\/Levenshtein.java\">here is Levenshtein.java<\/a>.<\/span><\/p>\n<p><span style=\"text-decoration: line-through;\"><a href=\"http:\/\/blog.lolyco.com\/sean\/2009\/03\/30\/java-damerau-levenshtein-update\/\">Updated with a bugfix March 2009<\/a><\/span><\/p>\n<p>2009 Apr 16 update &#8211; see <a title=\"Damerau Levenshtein page\" href=\"http:\/\/blog.lolyco.com\/sean\/damerau-levenshtein\/\">the Damerau Levenshtein page<\/a> for latest version<\/p>\n","protected":false},"excerpt":{"rendered":"<p>When I wrote about the Damerau Levenshtein MySQL UDF (User Defined Function) I explained that I prototyped the functions in Java first. I had a request for the Java code, but when I looked at it, realised that I only used it half way, and then made finishing touches to the C code directly. Here [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-147","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/posts\/147","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/types\/post"}],"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=147"}],"version-history":[{"count":6,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/posts\/147\/revisions"}],"predecessor-version":[{"id":266,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/posts\/147\/revisions\/266"}],"wp:attachment":[{"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/media?parent=147"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/categories?post=147"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/tags?post=147"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}