プログラマー幸福論

プログラム関係の雑記やcodicの開発日誌

soundexアルゴリズムを使ったスペルチェッカーの実装方法について

f:id:namba0219:20120330221851j:plain

Photo by bejadin.info

codic でも実装されている、検索エンジンや辞書サイトでよく見かけるスペルチェッカー(もしかしてxxx?)の実装方法について解説してみたいと思います。

通常スペルチェッカーの実装には、正しいスペルを辞書などに持っておく必要がありますが、codicでは、codic自身が英語辞書なので キーワードに対して自分自身に登録されている単語から、似ているものを見つけ出せばいいことになります。

似ている単語を見つけるアルゴリズムには、以下のようなものがあります。codic では、この中の Soundex を日本人用に改造して使っています(PHPの soundex 関数)。

  • レーベンシュタイン距離
  • Soundex
  • Metaphone

Soundex アルゴリズムについて

Soundex アルゴリズムは、「似たような発音に対して同じ文字」を返す特性があります。例えば、Sun と Son はどちらも S500 という文字列に変換されます。この特性を利用することで類似した英単語を検索することができます。

この Soundex アルゴリズムの最大のメリットは、類似する単語を完全一致で検索できるところにあります。完全一致だと何がいいのかというのは、検索アルゴリズムやDBのインデックスに詳しい人ならわかると思います。

リーベンシュタイン距離などの類似度を算出するアルゴリズムを使った場合、何らかの条件でフィルタリングされた母集団(最初の1文字で検索するなど)に対してすべての類似度を計算し、類似度が高いものをいくつか選択するという方法がとられます。

しかし Soundex では、あらかじめ Soundex 化したものをデータベースや全文インデックスに登録しておき、必要に応じて検索キーワードを Soundex 化したものを完全一致で検索することができるので、より高速な実装ができます。

日本人用にカスタマイズ

ただし、Soundex は、日本人向けのアルゴリズムではないので、right と light など日本人が間違いやすい単語については、考慮がありません。

そこで、codic では 少し改良したものを使うことでこの問題に対応しています。具体的には、Soundex 化する前に前処理として変換前の文字列に対して以下の置換を行っています。

  • L - R
  • TH - S
     

このような変換を行った場合、スペル候補に出やすくはなりますが、精度が鈍くなり結果が出すぎてしまう問題が発生してしまいます。codic では、検索結果に1件もヒットしなかった場合にキーワードの候補を検索するようすることで、出すぎても違和感なく使えるようにしています(0件の場合は多い方がいいだというという考え方)。 

ちなみに今回は紹介しませんが、Metaphone も同じような特性を持っていますので同じような処理を実装することができます。また Metaphone の方が Soundex よりもより正確らしいのでまた時間があれば試してみたいと思っています。