まず、レーベンシュタイン距離は、文字列Aを文字列Bに変換するために必要な編集の最小数として定義されます。ここで、編集とは、単一の文字の挿入または削除、あるいは文字の別の文字への置き換えです。つまり、距離の特定の定義にとって、それはまさに「2つの弦の違い」です。 =）
文字列AとBの間の距離と、距離がN未満の文字列がタイプミスの候補であるしきい値Nを与える距離関数F（A、B）を探しているようです。レーベンシュタイン距離に加えて、 Needleman–Wunsch も検討してください。 。基本的には同じですが、特定のキャラクターが別のキャラクターにどれだけ近いかを示す関数を提供できます。 QWERTYキーボードのキーの位置を反映する一連の重みを使用してそのアルゴリズムを使用すると、タイプミスを見つけるのにかなり良い仕事をすることができます。ただし、これには国際キーボードで問題が発生します。
k個の文字列があり、潜在的なタイプミスを見つけたい場合、行う必要のある比較の数はO（k ^ 2）です。さらに、各比較はO（len（A）* len（B））です。したがって、100万本の弦がある場合、素朴に物事を行うと問題が発生します。物事をスピードアップする方法に関するいくつかの提案があります：
- これが明らかな場合はお詫びしますが、レーベンシュタイン距離は対称であるため、F（A、B）とF（B、A）を計算していないことを確認してください。
- abs（len（A）--len（B））は、文字列AとBの間の距離の下限です。したがって、長さが大きすぎる文字列のチェックをスキップできます。
遭遇する可能性のある問題の1つは、「1stSt。」です。 「ファーストストリート」からはかなり離れていますが、おそらく同じものと見なしたいと思うでしょう。これを処理する最も簡単な方法は、比較を行う前に文字列を標準形に変換することです。したがって、すべての文字列を小文字にしたり、「1st」を「first」にマップする辞書を使用したりできます。その辞書はかなり大きくなる可能性がありますが、この問題に対処するためのより良い方法はわかりません。
この質問にphpのタグを付けたので、これにはphpを使用したいと思います。 PHPには組み込みのlevenshtein（）関数がありますが、両方の文字列は255文字以下である必要があります。それが十分に長くない場合は、自分で作成する必要があります。または、Pythonのdifflibを使用して調査します。