119

単語の候補を伴うスペル チェッカーを実装する場合、通常どのアルゴリズムが使用されますか?

最初は、入力された新しい単語 (辞書にない場合) を、辞書内の他のすべての単語からのレーベンシュタイン距離と照合し、上位の結果を返すことが理にかなっているかもしれないと考えました。ただし、これは辞書全体を繰り返し評価する必要があり、非常に非効率的です。

これは通常どのように行われますか?

4

5 に答える 5

212

スペル修正プログラムの実装方法について、Peter Norvig による優れたエッセイがあります。これは基本的に、指定された編集距離で候補文字列を試す力ずくのアプローチです。(ブルーム フィルターと高速な候補ハッシュを使用して、スペル修正プログラムのパフォーマンスを向上させるためのヒントをいくつか紹介します。 )

スペルチェッカーの要件はより緩いです。単語が辞書にないことを確認するだけで済みます。ブルーム フィルターを使用して、メモリ消費量の少ないスペル チェッカーを構築できます。古いバージョンは、Jon Bentley によるProgramming Pearlsで、64kb の英語辞書を使用して記述されています。

BK ツリーは別のアプローチです。素敵な記事はこちら.

レーベンシュタイン距離は、スペル チェッカーにとって正確な編集距離ではありません。挿入、削除、および置換のみを認識します。転置が欠落しており、1 文字の転置に対して 2 を生成します (1 削除と 1 挿入です)。ダメラウ - レーベンシュタイン距離は正しい編集距離です。

于 2010-02-19T08:34:43.227 に答える
19

私が正常に使用したものの、どこにも記載されていない提案を生成するアプローチは、「悪い」ハッシュ関数を使用して (辞書を作成するときに) 提案を事前に計算することです。

アイデアは、人々が犯すスペルミスの種類を調べ、間違ったスペルを正しいスペルと同じバケットに割り当てるハッシュ関数を設計することです。

たとえば、よくある間違いは、 defined の代わりに definate のように、間違った母音を使用することです。したがって、すべての母音を同じ文字として扱うハッシュ関数を設計します。これを行う簡単な方法は、最初に入力単語を「正規化」してから、正規化された結果を通常のハッシュ関数に通すことです。この例では、正規化関数はすべての母音を削除する可能性があるため、 になります。次に、「正規化された」単語は、一般的なハッシュ関数でハッシュされます。definitedfnt

この特別なハッシュ関数を使用して、すべての辞書の単語を補助インデックス (ハッシュ テーブル) に挿入します。ハッシュ関数が「悪い」ため、このテーブルのバケットには長い衝突リストがありますが、これらの衝突リストは基本的に事前に計算された提案です。

ここで、スペルミスのある単語を見つけたら、補助インデックスでスペルミスがマップされているバケットの衝突リストを調べます。Ta da: 提案リ​​ストがありますね。あなたがしなければならないのは、その上で単語をランク付けすることだけです。

実際には、他のタイプのエラーを処理するために、他のハッシュ関数を使用したいくつかの補助インデックスが必要になります。たとえば、転置された文字、1 文字/2 文字、さらには音声のスペルミスを検出するための単純な Soundex のようなものです。実際には、単純化された発音が長い道のりであり、些細なタイプミスを見つけるように設計されたもののいくつかは本質的に時代遅れであることがわかりました.

そのため、各補助インデックスでスペルミスを検索し、競合リストを連結してからランク付けします。

衝突リストには、辞書にある単語のみが含まれていることに注意してください。別のスペルを生成しようとするアプローチ (Peter Norvig の記事のように) を使用すると、最初に辞書に対してフィルター処理する必要がある (数万) の候補を取得できます。事前に計算されたアプローチでは、おそらく数百の候補が得られ、それらはすべて正しいスペルであることがわかっているため、ランキングに直接スキップできます.

更新: FAROO Distributed Searchという、これに似たアルゴリズムの記述を見つけました。これはまだ編集距離制限検索ですが、事前計算ステップが私の「悪いハッシュ関数」のアイデアのように機能するため、非常に高速です。FAROO は、不適切なハッシュ関数という限定された概念を使用しているだけです。

于 2013-12-18T18:52:24.313 に答える
7

アルゴリズム

  1. スペルが間違っている単語を入力として受け取ります。
  2. 英単語のリストを頻度とともにテキスト ファイルに保存します。
  3. 使用可能なすべての英単語 (テキスト ファイルに格納されている) とその頻度 (単語が英語で使用される頻度の尺度) を三分探索ツリーに挿入します。
  4. 次に、三分探索木に沿ってトラバースします -
    • Ternary Search Tree で検出された単語ごとに、スペルが間違っている単語からのレーベンシュタイン距離を計算します。
    • レーベンシュタイン距離 <= 3 の場合、単語を優先キューに格納します。
    • 2 つの単語の編集距離が同じ場合、頻度の高い単語の方が価値があります。Priority Queue の上位 10 項目を印刷します。

最適化

  1. 現在の単語からの入力単語の部分文字列の編集距離が 3 より大きい場合、現在のノードのサブツリー内の単語を削除できます。
    より詳細な説明とソース コードはgithub プロジェクトにあります。
于 2017-02-11T08:17:24.197 に答える
3

辞書内の各単語の正確な編集距離を知る必要はありません。制限値に達したらアルゴリズムを停止し、単語を除外できます。これにより、計算時間を大幅に節約できます。

于 2010-02-19T08:44:52.307 に答える
2

スペル チェッカーは、Unix のスペル プログラムと同様に非常に簡単に実装できます。ソースコードは公開されています。修正が含まれる可能性があります。1 つの手法は、編集を行い、この新しい単語が辞書にあるかどうかを再度確認することです。このような新しい編集は、グループ化してユーザーに表示できます。

Unix システムは、Mc IllRoy によって書かれたプログラムを使用します。別の方法は、巨大なファイルの場合に役立つ Trie を使用することです。

Unix アプローチは、スキャッター ハッシュ アルゴリズムを使用するため、巨大な辞書に必要なスペースが非常に少なくなります。

于 2011-10-25T18:51:46.180 に答える