4

特定の文字列と比較したい文字列の大きなリスト（200,000以上）があります。指定された文字列はユーザ​​ーによって挿入されたため、少し間違っている可能性があります。

私が望んでいたのは、リストに追加するときに、各文字列にある種の事前計算されたハッシュを作成することでした。このハッシュには、文字列の長さ、すべての文字の追加などの情報が含まれます。

私の質問は、このようなものはすでに存在するのでしょうか？確かに、リスト内のすべての文字列でレーベンシュタイン距離を実行しないようにする何かがありますか？

それとも、私がまだ考えていない3番目のオプションがありますか？

4

1 に答える 1

3

ある種のファジーハッシュを使用したいようです。このようなことを実行できるハッシュ関数はたくさんあります。古典的な古い「SOUNDEX」アルゴリズムも機能する可能性があります。

別の考え-誤ったエントリの可能性が低いと推定した場合、99.9％の確率で直接ヒットし、残りのケースの90％をキャッチする可能性のあるSOUNDEXにフォールバックして、全体を検索することで、実際に問題がない可能性があります。残りの0.01％の時間のリスト。

また、この議論をチェックする価値があります： 大規模な文字列データベースで文字列に最適なあいまい一致を見つける方法

于 2010-08-12T23:41:40.447 に答える