あいまい一致番号

Question

私はDouble MetaphoneとCaverphone2で文字列の比較を行ってきました。名前、住所などのようなものでうまくいきます（Caverphone2は私にとって最適です）。しかし、電話番号、IPアドレス、クレジットカード番号などの数値になると、あまりにも多くの誤検出が発生します。

したがって、LuhnとVerhoeffのアルゴリズムを見てきました。私はほしいが、それほどではない。彼らは検証には良いようだが、ファジーマッチングのために構築されているようには見えない。ファジィ文字列アルゴリズムに似た符号化と比較目的のために、2桁の数字を含む1桁のエラーと転置エラーを検出できるLuhnとVerhoeffのような動作はありますか？

数字をエンコードして100,000個の他の数字と比較して、非常に一致するものを探したいのですが。 7041234のようなものは7041324と転写エラーの可能性がありますが、4213704のようなものは一致しません。

Answer 1

Levenshteinandfriendsは、特定の文字列または数字の間の距離を見つけるのに適しています。ただし、スペルチェックを作成する場合は、すべてのクエリで単語データベース全体を実行する必要はありません。

Peter Norvigは、Googleのスペルの提案の背後にある技術のいくつかに基づいて、シンプルな「ファジーマッチング」スペル補正ツールにa very nice articleを書きました。

辞書にNのエントリがあり、平均単語の長さがLの場合、 "Brute force Levenshtein"アプローチには時間がかかりますO(N*L^3)。 Peter Norvigのアプローチでは、入力からある編集距離内のすべての単語が生成され、辞書で検索されます。したがって、これは、O(L^k)を達成する。ここで、kは、考慮される最も遠い編集距離である。