{"id":73,"date":"2008-08-06T01:44:25","date_gmt":"2008-08-05T17:44:25","guid":{"rendered":"http:\/\/blog.lolyco.com\/sean\/?p=73"},"modified":"2011-01-04T17:18:29","modified_gmt":"2011-01-04T09:18:29","slug":"search-suggestions-with-mysql-levenshtein-distance","status":"publish","type":"post","link":"https:\/\/blog.lolyco.com\/sean\/2008\/08\/06\/search-suggestions-with-mysql-levenshtein-distance\/","title":{"rendered":"Search suggestions with MYSQL Levenshtein distance"},"content":{"rendered":"

Up until a couple of days ago, the Spider.my<\/a> search<\/strong> page applied only minimal formatting to hits, and no extra page decoration. The ‘blank screen of death<\/strong>‘ appeared for a search miss<\/strong>: no results, no page content.<\/p>\n

Just to reassure the user<\/strong> the empty page was ‘normal’, I’d put a lame<\/strong> message up saying “No results, try something like ‘uk sun<\/strong>‘”. As soon as I’d made the recent searches page and saw some Bahasa Malaysia <\/a>searches on there, I realised that must look terrible<\/strong>!<\/p>\n

I recalled the SOUNDEX()<\/strong> function from donkey’s years ago, but quickly gave up on using that. SOUNDEX() produces a code that can be used to match strings phonetically<\/strong>, but a simple spelling mistake can produce a large difference in SOUNDEX() result. In addition, two very different words may share the same SOUNDEX() result, for example: ‘perhaps’ and ‘privacy’.<\/p>\n

A quick search turned up Levenshtein Distance<\/a><\/strong>, also know as ‘edit distance’. This is a measure of the minimum edits that must be made to one word to change it into another. You can think of it as the number of mistakes needed to turn what you intended to type into what you actually typed! Thought of this way, it seems to be a good candidate<\/strong> for search key suggestions<\/strong>.<\/p>\n

Spider.my uses a MySQL<\/a> backend, and there are Levenshtein implementations available online as stored procedures, but I chose to go with source code from Josh Drew’s website<\/a>. Compiling and installing the code on my Slackware server was much easier than Josh’s instructions made me think it would be. I got some extra hints from a page at mysql.com<\/a>.<\/p>\n

All I had to do was to compile:<\/p>\n

g++ -I \/usr\/include\/mysql\/ -o libmysqllevenshtein.so -shared\u00a0 mysqllevenshtein.cc<\/code><\/p><\/blockquote>\n

The source file doesn’t immediately look like C++, so if you compile it with gcc, you’ll get an error about
\n“__gxx_personality_v0 undefined symbol”. I found the tip to use g++ instead on http:\/\/gcc.gnu.org\/ml\/gcc-help\/2002-07\/msg00186.html<\/a> and http:\/\/mail.python.org\/pipermail\/python-list\/2002-June\/149504.html.<\/a><\/p>\n

Copy the shared object to the directory where the other mysql libs are:<\/p>\n

cp libmysqllevenshtein.so \/usr\/lib\/mysql\/<\/code><\/p><\/blockquote>\n

And update the library links and cache:<\/p>\n

cd \/usr\/lib<\/code><\/p>\n

ln -s mysql\/libmysqllevenshtein.so .<\/code><\/p>\n

ldconfig<\/code><\/p><\/blockquote>\n

Then in mysql:<\/p>\n

CREATE FUNCTION levenshtein RETURNS INT SONAME 'libmysqllevenshtein.so';<\/code><\/p><\/blockquote>\n

That’s it! Now a query like:<\/p>\n

select levenshtein('privacy', 'rpivacy');<\/code><\/p><\/blockquote>\n

returns ‘2’ – the minimum number of edits to change ‘rpivacy’ into ‘privacy’. Now the search at spider.my<\/a> is much more friendly when your typing goes bad!<\/span> (2011 Jan 4th – just saw this link turn up as a 404. There’s not currently a spell checker at spider.my<\/a>, but there may be one day soon.<\/p>\n

\"Suggested<\/a>

Suggested word for typo in search box<\/p><\/div>\n

Some updates on this topic are available:
\nDamerau-Levenshtein algorithm: Levenshtein with transpositions<\/a>
\nDamerau-Levenshtein in Java<\/a><\/p>\n

2009 Apr 16 update – see the Damerau Levenshtein page<\/a> for latest version<\/p>\n","protected":false},"excerpt":{"rendered":"

Up until a couple of days ago, the Spider.my search page applied only minimal formatting to hits, and no extra page decoration. The ‘blank screen of death‘ appeared for a search miss: no results, no page content. Just to reassure the user the empty page was ‘normal’, I’d put a lame message up saying “No […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[30,20,11,3,35],"tags":[9,22],"class_list":["post-73","post","type-post","status-publish","format-standard","hentry","category-breaktime","category-fixed","category-google","category-software","category-spidermy","tag-open-source","tag-slackware"],"_links":{"self":[{"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/posts\/73","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=73"}],"version-history":[{"count":13,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/posts\/73\/revisions"}],"predecessor-version":[{"id":1031,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/posts\/73\/revisions\/1031"}],"wp:attachment":[{"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/media?parent=73"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/categories?post=73"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/tags?post=73"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}