- 更新日: 2014年10月27日
- 開発記録
SimString を用いたスペルミス訂正機能
Imagict で、英単語検索時のスペルミス訂正機能を実装しました。例として、famiry とスペルミスして検索すると、family, famine, familiar, familial の4つが訂正候補として提案されます。
内部的にどうやってるかちょっと技術的なことを少々。スペルミス訂正は、類似文字列検索のライブラリを利用して実現しています。
類似文字列検索のライブラリは SimString
まず類似文字列検索で使っているライブラリは SimString というライブラリです。詳細は、以下。
SimString – 高速かつシンプルな類似文字列検索ライブラリ
類似文字列検索ライブラリSimStringをRubyから使う | EasyRamble
SimString は文字列同士の類似度を計算する際に、コサイン係数/ジャッカード係数/ダイス係数/オーバーラップ係数の4種類のいずれかの係数を指定できます。
色々試したところ、ジャッカード係数かダイス係数が、類似度計算の精度が高そうだったので、とりあえずジャッカード係数を採用。
そして、その係数を db.threshold にて指定するのですが、これを大きくすると類似度判定が厳しくなり、類似する文字列の候補数が少なくなります。なので、あまり係数を大きくすると、スペルミス訂正の予測で、出てきて欲しい候補が出てこなくなります。
そこで、最初の段階として、この係数は小さめに設定しました。
1文字目はスペルミスしないだろうと仮定(笑)
ジャッカード係数を小さめに設定すると、出てきて欲しい候補は含まれるようになるのですが、別の問題が発生します。そう、類似文字列の候補数がたくさん出過ぎちゃうのですね。
なので、とりあえず検索文字列のうち1文字目はスペルミスしないだろうと仮定して、1文字目が検索文字列と違う類似文字列は、候補から弾くようにしました。
以上の簡単なアルゴリズムで、それなりの精度の英単語のスペルミス訂正機能を実装できたので、SimString が素晴らしすぎです。
Google のスペルミス訂正機能(もしかして: ○○)はおそろしく精度が高いので、類似文字列検索的なライブラリに加えて、機械学習的なアルゴリズムも加えているのかな〜と予測してます。候補のうちよくクリックされるのが正解!と段々学習していくようなアルゴリズムかなーと。
- 開発記録 の関連記事
- Mastodon(マストドン)をブログ風に保存するサービスを作った
- Wunderlistからリマインダー(iPhone/iCloud)への移行ツールを作りました!
- 指定の曜日から日付を取得するツール(JavaScript)
- 書評や商品レビューのブログ記事のみにGoogle検索を絞り込むブックマークレット
- サクサクひける!ポップアップ辞書Chrome拡張(英和/英英辞典)を公開しました
- JavaScriptで英単語の原形を取得できるライブラリを公開しました
- ImagictでBingoされた英単語をつぶやくTwitter botを作成しました
- jQuery(JavaScript)でマウス座標やウィンドウサイズを取得して確認するツール
- JavaScriptでcollapsed rangeオブジェクトを可視化するツールを作った
- Imagict 開発日誌のブログを始めました
Leave Your Message!