自動修正アルゴリズム

Question

C++で次のコードを実装します。

1）指定された単語が辞書に存在するかどうかを確認します。辞書ファイルは膨大なファイルです。 100MBまたは3〜400万語を考えてみましょう。

2）誤った単語の訂正を提案してください。

3）オートコンプリート機能。

私のアプローチ

1）私はそう効率的な意志を検索ツリーを構築する予定です。

2）自動補正機能を実装する方法がわかりません。

3）私は、オートコンプリート機能を実装することができます木

を使用して上記のすべての機能を実装するために最適なデータ構造とアルゴリズムは何ですか？

Answer 1

特定のサブツリーのすべての文字列を調べることで自動補完を行うことができます。あなたが選ぶのに役立ついくつかのスコアが役立つかもしれません。これは、あなたがトライでその道を下って行き、すべての可能なエンディングを得るためにそこにサブツリー全体をトラバースする場合のようなものです。

修正のために、http://en.wikipedia.org/wiki/Levenshtein_distanceのようなものをツリーの上に実装する必要があります。トライで与えられたパスを処理した場合は、パスの最後にあるサブツリーのすべての文字列に対して結果を再利用できるという事実を利用できます。

Answer 2

1）別に木から、別の興味深い方法は http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform
BWTの接尾辞配列を容易に所定の接頭辞を持つ単語を追跡するために使用することができるBWT
です。エラー訂正のための

2）は、現代的なアプローチは、LHSです：ランダムなGoogle検索によって提供さ
http://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search

いくつかのリンク：私は、に取り組んでいます
https://cs.stackexchange.com/questions/2093/efficient-map-data-structure-supporting-approximate-lookup
https://code.google.com/p/likelike/
http://aspguy.wordpress.com/2012/02/18/the-magic-behind-the-google-search/

Answer 3

同じ問題。今まで私が遭遇した最良の解決策は、自動補完のために三項探索木を使用することです。三元探索木は、試行よりも空間効率が良い。 もし私の三元検索ツリーで検索した文字列を見つけることができないのであれば、私は最も近いものを見つけるために既にビルドされたBKツリーを使います。 BKツリーはLevenshtein距離を内部的に使用します。 You

メタフォンはあなたが探求したいかもしれないものですが、私はメタフォンの深みにはいきません。

私はあなたが好きな方は、BK TREE + TERNARY SEARCH TREEのためのJavaで解決策を持っています。