{"id":116,"date":"2008-08-27T23:26:41","date_gmt":"2008-08-27T15:26:41","guid":{"rendered":"http:\/\/blog.lolyco.com\/sean\/?p=116"},"modified":"2009-04-16T11:11:14","modified_gmt":"2009-04-16T03:11:14","slug":"damerau-levenshtein-algorithm-levenshtein-with-transpositions","status":"publish","type":"post","link":"https:\/\/blog.lolyco.com\/sean\/2008\/08\/27\/damerau-levenshtein-algorithm-levenshtein-with-transpositions\/","title":{"rendered":"Damerau-Levenshtein algorithm: Levenshtein with transpositions"},"content":{"rendered":"

I’m still working away slowly at Spider.my<\/a>, and spotted a funny loop in the search suggestions<\/strong>:<\/p>\n

\"Search<\/a>

Search for Teusday - how about Thursday?<\/p><\/div>The helpful hint is “maybe ‘thursday’ would get more results?”. I’m using a simple Levenshtein distance algorithm<\/a> to provide hints<\/strong> when only a few results appear. Because spider.my has very few sites<\/strong> in its database at the moment, nearly every search produces a handy (actually somewhere between funny and annoying!) hint. The basic Levenshtein algorithm doesn’t test for transpositions<\/a> – when 2 keys<\/strong> are pressed<\/strong> in the wrong order<\/strong>. A test like “levenshtein(‘teusday’, ‘tuesday’)” will give an answer of 2, for the two substitutions<\/strong>. Similarly, “levenshtein(‘teusday’, ‘thursday’)” gives a result of 2, for the substitution of ‘e’ with ‘h’ and the insertion<\/strong> of ‘r’. My hint code orders results by levenshtein distance<\/strong> only, so ‘thursday’ appears before ‘tuesday’ in the results due to caprice<\/strong> on the part of MySQL<\/strong>.<\/p>\n

I’m sure there’s a better reason<\/strong> than caprice, but I don’t often use the word, and I don’t know<\/strong> why the order is that way, so … caprice it is. I could also order my results by similarity in length<\/strong> to the original keyword. That’s a sensible<\/strong> idea that only just struck me, but it didn’t at the crucial time<\/strong>, so I wrote a lot of code instead.<\/p>\n

Clicking on the helpful hint above starts the circle:<\/p>\n

\"Not<\/a>

Not many results for Thursday, how about Tuesday?<\/p><\/div>\n

Again, not many results due to an empty database<\/strong>, and the hint code excludes suggesting the same word, so the hint sends us back to Tuesday.\u00a0 Tuesday and Thursday have the same Levenshtein distance from each other, so around<\/strong> we go. This loop isn’t likely to go away with an improved<\/strong> distance function: a ‘closest’ suggestion for some word will itself suggest the original word if distance is the only criterion<\/strong>.<\/p>\n

The problem on spider.my is a consequence of the near-empty database. If more results were returned from a search, the suggestion would only appear for an uncommon<\/strong> (or mis-spelt) keyword. If a more common keyword is suggested, no suggestion will be made.<\/p>\n

I read on Wikipedia<\/strong> that the Levenshtein function doesn’t test for transpositions<\/strong>, and my original faulty keyword ‘teusday’ is a good example: the ‘e’ and the ‘u’ are transposed<\/strong> – they are each in the other’s position. The Wikipedia article links to another Wikipedia article with an algorithm that does include transposition checking – Damerau Levenshtein<\/a>.<\/p>\n

While I was editing<\/strong> Josh Drew’s Levenshtein code, I made a few other changes<\/strong>. Maybe they’re not to everybody’s taste, so here are 3 different versions of my Damerau-Levenshtein function<\/strong> for MySQL based on Josh Drew’s code:<\/p>\n

1. Basic Damerau-Levenshtein distance (damlev(string, string)), minimal changes to original code:<\/p>\n

Damerau-Levenshtein distance source code<\/a><\/p>\n

– slightly more time<\/strong> to execute (about 10%?) than levenshtein().<\/p>\n

2. Damerau-Levenshtein distance, with limit<\/strong> (damlev(string, string, int)) to save computation<\/strong> time on very dissimilar<\/strong> strings:<\/p>\n

Damerau-Levenshtein distance with limit source code<\/a><\/p>\n

– can execute<\/strong> in a fraction<\/strong> of the time (from 50 seconds average down to 13 seconds average in one of my tests) of damlev() with low limits. Worst case<\/strong> (when limit > string length) very similar<\/strong> time to damlev(string, string). Best gains on long strings, low limit.<\/p>\n

3. Damerau-Levenshtein distance, with limit and performance hack<\/strong> (damlevlim256(string, string, int) to pre-load row and column starts:<\/p>\n

Damerau-Levenshtein distance with limit and 256 hack source code<\/a><\/p>\n

– executes in less than 90% of time of damlevlim in tests. Time saving greater for longer strings, but not much<\/strong>. 256 ( – 1) is maximum length of string arguments (currently DOES NOT TEST for argument length!<\/strong>). The pre-loaded table is 64K in size, because that should be enough for anybody<\/strong> \ud83d\ude00<\/p>\n

For installation<\/strong> instructions, see my search suggestions with MYSQL Levenshtein distance<\/a> article. Let me know<\/strong> how you get on with any or all of those, I hope you find them useful. I wrote the Damerau add-ons in Java<\/strong> first, so I can post those up too if anybody is interested<\/del> here they are<\/a><\/span><\/span>. Now on the Damerau Levenshtein page<\/a><\/p>\n

Just for comparison:<\/p>\n

levenshtein('teusday', 'tuesday') = 2
\nlevenshtein('teusday', 'thursday') = 2
\ndamlev('teusday', 'tuesday') = 1
\ndamlev('teusday', 'thursday') = 2
\ndamlev('tuesday', 'something') = 8
\ndamlevlim('tuesday', 'something', 3) = 3 (returns early)
\n<\/code><\/p>\n","protected":false},"excerpt":{"rendered":"

I’m still working away slowly at Spider.my, and spotted a funny loop in the search suggestions: The helpful hint is “maybe ‘thursday’ would get more results?”. I’m using a simple Levenshtein distance algorithm to provide hints when only a few results appear. Because spider.my has very few sites in its database at the moment, nearly […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[36,3,35],"tags":[39,9,18,105],"class_list":["post-116","post","type-post","status-publish","format-standard","hentry","category-search","category-software","category-spidermy","tag-mysql","tag-open-source","tag-server","tag-software"],"_links":{"self":[{"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/posts\/116","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=116"}],"version-history":[{"count":11,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/posts\/116\/revisions"}],"predecessor-version":[{"id":127,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/posts\/116\/revisions\/127"}],"wp:attachment":[{"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/media?parent=116"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/categories?post=116"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/tags?post=116"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}