[解決済み] スペルチェッカーで候補を出すアルゴリズムとは？

質問

単語候補を含むスペルチェッカーを実装する場合、一般的にどのようなアルゴリズムが使用されますか？

最初は、入力されたそれぞれの新しい単語を (辞書にない場合) その単語の レーベンシュタイン距離 に対してチェックし、上位の結果を返すという方法がいいのではないかと考えました。 しかし、これは、辞書全体を繰り返し評価する必要があり、非常に非効率的であるように思われます。

これは一般的にどのように行われるのでしょうか。

どのように解決するのですか？

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

スペルチェッカーの要件はより弱いものです。ある単語が辞書に載っていないことがわかればよいのです。このため ブルームフィルタ を使って、より少ないメモリ消費でスペルチェッカーを構築することができます。古代のバージョンは プログラミングの真珠 Jon Bentley による、英語辞書に 64kb を使用したものです。

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

Levenshstein 距離はスペルチェッカーに適した編集距離ではありません。それは、挿入、削除、および置換のみを知っています。転置は欠落しており、1 文字の転置に対して 2 を生成します (これは 1 削除と 1 挿入です)。 Damerau-Levenshtein 距離 が正しい編集距離です。