SimString を用いたスペルミス訂正機能

Imagict で、英単語検索時のスペルミス訂正機能を実装しました。例として、famiry とスペルミスして検索すると、family, famine, familiar, familial の4つが訂正候補として提案されます。

内部的にどうやってるかちょっと技術的なことを少々。スペルミス訂正は、類似文字列検索のライブラリを利用して実現しています。

【お知らせ】英単語を画像イメージで楽に暗記できる辞書サイトを作りました。英語学習中の方は、ぜひご利用ください！

類似文字列検索のライブラリは SimString

まず類似文字列検索で使っているライブラリは SimString というライブラリです。詳細は、以下。

SimString は文字列同士の類似度を計算する際に、コサイン係数/ジャッカード係数/ダイス係数/オーバーラップ係数の4種類のいずれかの係数を指定できます。

色々試したところ、ジャッカード係数かダイス係数が、類似度計算の精度が高そうだったので、とりあえずジャッカード係数を採用。

そして、その係数を db.threshold にて指定するのですが、これを大きくすると類似度判定が厳しくなり、類似する文字列の候補数が少なくなります。なので、あまり係数を大きくすると、スペルミス訂正の予測で、出てきて欲しい候補が出てこなくなります。

そこで、最初の段階として、この係数は小さめに設定しました。

ジャッカード係数を小さめに設定すると、出てきて欲しい候補は含まれるようになるのですが、別の問題が発生します。そう、類似文字列の候補数がたくさん出過ぎちゃうのですね。

なので、とりあえず検索文字列のうち1文字目はスペルミスしないだろうと仮定して、1文字目が検索文字列と違う類似文字列は、候補から弾くようにしました。

以上の簡単なアルゴリズムで、それなりの精度の英単語のスペルミス訂正機能を実装できたので、SimString が素晴らしすぎです。

Google のスペルミス訂正機能（もしかして: ○○）はおそろしく精度が高いので、類似文字列検索的なライブラリに加えて、機械学習的なアルゴリズムも加えているのかな〜と予測してます。候補のうちよくクリックされるのが正解！と段々学習していくようなアルゴリズムかなーと。

Rails と Swift はぜひ押さえておきたいです。