最近、職場で興味深い問題が発生しました。データベースでユーザーが送信したデータが重複していることがわかりました。このデータのほとんどの間のレーベンシュタイン距離は、問題の2つの文字列の違いにすぎないことがわかりました。これは、ある文字列から別の文字列に文字を追加するだけでは、同じ文字列になることを示しています。ほとんどの場合、これは重複するアイテムを説明するための最良の方法のようです。
タイプミスも考慮したいと思います。そこで私たちは、平均して単語ごとにオンラインでタイプミスをする頻度について考え始め、この距離内でそのデータを使用しようとしました。そのような統計は見つかりませんでした。
データの一致に対してこの種のしきい値を作成するときにタイプミスを説明する方法はありますか？
明確にできるかどうか教えてください！
まず、レーベンシュタイン距離は、文字列Aを文字列Bに変換するために必要な編集の最小数として定義されます。ここで、編集とは、単一の文字の挿入または削除、あるいは文字の別の文字への置き換えです。つまり、距離の特定の定義にとって、それはまさに「2つの弦の違い」です。=）
文字列AとBの間の距離と、距離がN未満の文字列がタイプミスの候補であるしきい値Nを与える距離関数F（A、B）を探しているようです。レーベンシュタイン距離に加えて、ニードルマン-ブンシュを検討することもできます。基本的には同じですが、特定のキャラクターが別のキャラクターにどれだけ近いかを示す関数を提供できます。QWERTYキーボードのキーの位置を反映する一連の重みを使用してそのアルゴリズムを使用すると、タイプミスを見つけるのにかなり良い仕事をすることができます。ただし、これには国際キーボードの問題があります。
k個の文字列があり、潜在的なタイプミスを見つけたい場合、行う必要のある比較の数はO（k ^ 2）です。さらに、各比較はO（len（A）* len（B））です。したがって、100万本の弦がある場合、素朴に物事を行うと問題が発生します。物事をスピードアップする方法に関するいくつかの提案があります：
遭遇する可能性のある問題の1つは、「1stSt。」です。「ファーストストリート」からはかなり離れていますが、おそらく同じものと見なしたいと思うでしょう。これを処理する最も簡単な方法は、比較を行う前に文字列を標準形に変換することです。したがって、すべての文字列を小文字にしたり、「1st」を「first」にマップする辞書を使用したりできます。その辞書はかなり大きくなる可能性がありますが、この問題に対処するためのより良い方法はわかりません。
この質問にphpのタグを付けたので、これにはphpを使用したいと思います。PHPには組み込みのlevenshtein（）関数がありますが、両方の文字列は255文字以下である必要があります。それが十分に長くない場合は、自分で作成する必要があります。または、Pythonのdifflibを使用して調査します。
あなたはこの本をチェックするべきです：
http://nlp.stanford.edu/IR-book/pdf/irbookonlinereading.pdf
スペルチェックに関する良い章（3.3）があります
この章の最後にある参考文献には、確率モデルについて説明しているいくつかの論文がリストされています。
幸運を