質問: 誤字を検出して正解の単語をサジェストする、いわゆる「もしかして」検索を実装しようとしています。 使用する正解の単語コーパス(以下『辞書』)を検索対象の項目ごとに切り替えて精度を上げる運用を考えています。 (例えば氏名の項目には『氏名データベース』から、注文の項目には『自社の取扱い商品名リスト』から生成した辞書をそれぞれ割り当てます) オンプレミス環境で任意の辞書からレーベンシュタイン距離が1の誤字(挿入、置換、削除を1文字行って正解に合致する誤字)と正解を表示することが目的です。 日本語に対してこの校正用途で使用可能なライブラリまたはアルゴリズムは公開されているのでしょうか。 言語やOSは問いません。 自作のコードではgrepとループを繰り返す総当たり処理しか思いついていないため、項目数や辞書の単語数が増えてくると低速になることを懸念しております。 高速なライブラリがあれば試用したいのですがうまく見つけられないため質問させていただきました。
回答: いただいた回答をヒントに、`Levenshtein & DB名`で検索したところ、様々なライブラリを探すことができました。 * Python: python-Levenshtein `$ sudo pip install python-Levenshtein` * Java: Apache Luceneライブラリ Luceneから*.jarファイルを取得してインポート * PHP: levenshtein_utf8 下記エントリのコードを参照 上記以外にもインデックスを作成しておくことで、BK木より100倍速いというベンチマークを表示しているSymSpellが興味深いです。 2バイト文字に対応しているかどうかは分かりませんが、検索するとMySQLやSQLiteでレーベンシュタイン距離を計算するライブラリもヒットするようです。