47480


誤字を検出して正解の単語をサジェストする、いわゆる「もしかして」検索を実装しようとしています。  
使用する正解の単語コーパス(以下『辞書』)を検索対象の項目ごとに切り替えて精度を上げる運用を考えています。  
(例えば氏名の項目には『氏名データベース』から、注文の項目には『自社の取扱い商品名リスト』から生成した辞書をそれぞれ割り当てます)

オンプレミス環境で任意の辞書からレーベンシュタイン距離が1の誤字(挿入、置換、削除を1文字行って正解に合致する誤字)と正解を表示することが目的です。  
日本語に対してこの校正用途で使用可能なライブラリまたはアルゴリズムは公開されているのでしょうか。  
言語やOSは問いません。

自作のコードではgrepとループを繰り返す総当たり処理しか思いついていないため、項目数や辞書の単語数が増えてくると低速になることを懸念しております。  
高速なライブラリがあれば試用したいのですがうまく見つけられないため質問させていただきました。


CC BY-SA 4.0
2018-08-09T10:41:54.267
47380
2018-08-14T01:41:41.927
9820
question
アルゴリズム
任意の辞書で「もしかして」検索機能を提供するライブラリまたはアルゴリズム


`PostgreSQL`では、拡張機能`fuzzystrmatch`で`Levenshtein`が提供されています。  
<https://www.postgresql.org/docs/10/static/fuzzystrmatch.html>

また、`Elasticsearch`でも、可能と思われます。  
<https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-
fuzzy-query.html>


CC BY-SA 4.0
2018-08-13T06:03:20.223
47480
2018-08-13T06:03:20.223
15171
47380
answer


いただいた回答をヒントに、`Levenshtein & DB名`で検索したところ、様々なライブラリを探すことができました。

  * Python: python-Levenshtein  
`$ sudo pip install python-Levenshtein`  
<https://qiita.com/inouet/items/709eca4d8172fec85c31>

  * Java: Apache Luceneライブラリ   
[Lucene](http://lucene.apache.org/core/)から*.jarファイルを取得してインポート  
<https://blogs.yahoo.co.jp/dk521123/36655532.html>

  * PHP: levenshtein_utf8  
下記エントリのコードを参照  
<https://qiita.com/mpyw/items/2b636827730e06c71e3d>

上記以外にもインデックスを作成しておくことで、BK木より100倍速いというベンチマークを表示している[SymSpell](https://github.com/wolfgarbe/SymSpell)が興味深いです。  
<https://qiita.com/daimonji-bucket/items/1f40bc3242a3d26133d0>

2バイト文字に対応しているかどうかは分かりませんが、検索するとMySQLやSQLiteでレーベンシュタイン距離を計算するライブラリもヒットするようです。


CC BY-SA 4.0
2018-08-14T01:41:41.927
47497
2018-08-14T01:41:41.927
9820
47380
answer