MySQLでレーベンシュタイン距離を使ったあいまい検索

ある文字列に近い文字列をデータベースから探してくるというような処理をしたいときに どうしようかなと思って調べていたときに見つけたのがこの記事。


第11回 Kansai.pm / スペルミス修正プログラムを作ろう

これは、スペルミスの例ですが、やりたいことは同じで「文字列間の類似性を調べて 類似度が高いものを抽出する」という処理です。

その方法の一つに「レーベンシュタイン距離」を使うというのがあったので調べてみました。

実装については、いろんな言語で関数がすでに作られていてライブラリ化されてたりするようです。 PHPに関して言えばそのまんまの levenshtein という関数がありました。

PHP: levenshtein - Manual

試してみたところ、UTF-8で使用した範囲ではきちんと動いているようです。

ただ、編集距離は求められるのですが、最終的にやりたいのは類似度の高いもの順にならべて 候補を示すという処理なので、PHPでデータベース内の文字列をなめて類似度を計算してソートする という処理をするのはしんどい感じです。

で、データベース側でなんとか処理できないかなと思って見つけたのがこれ。

Levenshtein Distance as a MySQL Stored Function

MySQLのストアド関数を作った人がいました。
これなら、

SELECT name, LEVENSHTEIN(name) AS distance FROM hoge 
  ORDER BY distance LIMIT 10;

みたいに書けますね。

これだと、文字列全部をなめて類似度を計算する部分は変わらないので、距離の計算に入る前にある程度ふるいにかけて候補を絞り込んだりした上で距離を計算するのがよいかと思いますが、とりあえずソートの部分をDBに任せられるので、ちょっと楽になりそうです。

上記のnaoyaさんのページには、絞り込みにN-Gramインデックスを使う方法や、編集距離にJaro-Winkler距離を使う方法などが書いてあるので、参考にしてみたいと思います。