19

比較的短いテキスト文字列 (住所、名前などの順序) を持つ大規模なデータベース (潜在的に数百万のレコード) があります。

不正確な重複を削除する戦略を探していますが、あいまい一致が最適な方法のようです。私の問題: 多くの記事と SO の質問は、データベース内のすべてのレコードに対して単一の文字列を照合することを扱っています。データベース全体を一度に重複排除しようとしています。

前者は、線形時間の問題になります (ある値を他の 100 万の値と比較し、毎回何らかの類似度を計算します)。後者は指数時間の問題です (すべてのレコードの値を他のすべてのレコードの値と比較します。100 万レコードの場合、前者のオプションの 1,000,000 回の計算に対して、約 5 x 10^11 回の計算になります)。

私が言及した「ブルートフォース」方法以外のアプローチがあるかどうか疑問に思っています。各レコードの値を比較するための文字列を生成し、類似度がほぼ等しい文字列をグループ化し、これらのグループに対して総当り法を実行することを考えていました。線形時間は達成できませんが、役立つかもしれません。また、これを適切に考えていれば、文字列 A と B の間の潜在的なあいまい一致を見逃す可能性があります。文字列 C (生成されたチェック文字列) との類似性は、互いに非常に類似しているにもかかわらず、非常に異なるためです。

何か案は？

PS私は、時間の複雑さに対して間違った用語を使用した可能性があることを認識しています-それは私が基本的に理解している概念ですが、その場でアルゴリズムを適切なカテゴリにドロップできるほど十分ではありません. 用語を間違って使用した場合は、修正を歓迎しますが、少なくとも私の主張を理解していただければ幸いです.

編集

一部のコメンターは、レコード間のあいまい一致を考慮して、どのレコードを削除するかを選択するための私の戦略は何であるかを尋ねました (つまり、「foo」、「boo」、および「coo」が与えられた場合、重複としてマークされ、削除されます)。ここで自動削除を探しているわけではないことに注意してください。アイデアは、人間によるレビューと評価の目的で、6,000 万以上のレコード データベースで潜在的な重複にフラグを立てることです。おおまかに予測可能/一貫した量である限り、誤検知があっても問題ありません。重複がどの程度蔓延しているかを把握する必要があるだけです。しかし、ファジー マッチング パススルーの実行に 1 か月かかる場合、そもそもこれはオプションではありません。

4

6 に答える 6

13

http://en.wikipedia.org/wiki/Locality-sensitive_hashingをご覧ください。非常に単純なアプローチの 1 つは、各アドレス (または何でも) を重複する n-gram のセットに分割することです。このＳＴＡＣＫＯＶＥＲＦＬＯＷは集合｛ＳＴＡＣＫＯ，ＴＡＣＫＯ，ＡＣＫＯＶ，ＣＫＯＶＥ・・・，ＲＦＬＯＷ｝となる。次に、大きなハッシュ テーブルまたはソート マージを使用して衝突する n グラムを見つけ、ファジー マッチャーで衝突をチェックします。したがって、STACKOVERFLOW と SXACKOVRVLOX は、衝突する n グラム ACKOV に関連付けられているため、衝突します。

洗練された次のレベルは、ランダム ハッシュ関数を選択することです。たとえば、任意のキーを持つ HMAC と、見つけた n グラムのうち、最小のハッシュ値を持つものだけを保持します。次に、少数の n-gram を追跡する必要がありますが、両方のケースで最小のハッシュ値が ACKOV である場合にのみ一致が表示されます。ここでは明らかに、n-gram の長さと誤ヒットの確率との間にトレードオフがあります。実際、同じレコード内の複数のハッシュ関数からの結果を連結することにより、n を非常に小さくして精度を高めるように思われるため、複数の異なるハッシュ関数で同時に一致を取得する必要があります。確率はこの方法でうまくいくと思います。「重複検出ミンハッシュ」をグーグルで検索してみてください

于 2011-08-25T20:17:41.990 に答える
3

すべての組み合わせの複雑さを誤って計算した可能性があると思います。1つの文字列を他のすべての文字列と比較することが線形である場合、これは長さが短いため、各比較はO（1）であることを意味します。各文字列を他のすべての文字列と比較するプロセスは、指数関数ではなく2次式であり、すべてが悪いわけではありません。簡単に言うと、nC2またはn（n-1）/ 2の文字列のペアを比較しているので、O（n ^ 2）だけです。

客観的なコンパレータを書くことができないので、順番に並べ替えることができる方法を考えることはできませんでしたが、そうしても、並べ替えにはマージソートにO（nlogn）が必要であり、レコードが非常に多いため、おそらく余分なメモリを使用する場合は、クイックソートを使用します。これは、最悪の場合はO（n ^ 2）を取り、ブルートフォースの最悪の場合の時間よりも改善されません。

于 2011-08-25T19:38:29.423 に答える
3

レーベンシュタイン トランスデューサーを使用できます。これは、「クエリ用語を受け入れ、それから離れた n 個のスペル エラー内にある辞書内のすべての用語を返します」。 ここにデモがあります。

于 2016-02-16T01:54:42.287 に答える
1

これは1回限りのクリーンアップだと思います。問題は、それほど多くの比較を行う必要があることではなく、どの比較を行う価値があるかを判断する必要があると思います。あなたは名前と住所に言及しているので、あなたが直面する比較の問題のいくつかについては、このリンクを参照してください.

100 万個のレコードをそれ自体と比較するには、ほぼ 5000 億回のブルート フォース比較を行わなければならないのは事実ですが、それは、以前に一致と宣言されたレコードをスキップしないことを前提としています (つまり、以下の擬似コード）。

私のポーキー E-machines T6532 2.2GHz は、100 バイトのテキスト ファイル レコードの 1 秒あたり 1.4m のシークと読み取りを行うことができるため、5,000 億の比較には約 4 日かかります。手の込んだソリューションの調査とコーディングに 4 日間を費やす代わりに (実際に実行するには、さらに x 日が必要であることがわかりました)、比較ルーチンが比較対象のキーを計算して保存できないと仮定します。他にやるべきことを見つけている間、これらすべての比較をブルートフォースさせます。

for i = 1 to LASTREC-1
  seektorec(i)
  getrec(i) into a
  for j = i+1 to LASTREC
    getrec(j) into b
    if similarrecs(a, b) then [gotahit(); break]

特定の実行で簡単に定義できる一致しか見つからなかったとしても、残りの一致しないレコードをより合理的な小さなセットに減らして、さらに力ずくで実行してもそれほど時間がかからないことを願っています。

しかし、similarrecs() が比較対象の a + b の部分を個別に計算して保存できない可能性は低いと思われます。その場合、はるかに効率的な方法は次のとおりです。

for i = 1 to LASTREC
  getrec(i) in a
  write fuzzykey(a) into scratchfile
sort scratchfile
for i = 1 to LASTREC-1
  if scratchfile(i) = scratchfile(i+1) then gothit()

各レコードの fuzzykey() を計算するために独自のカスタム コードを呼び出すことが許可されている場合、ほとんどのデータベースは 1 つのコマンド ラインで上記を実行できます。

いずれにせよ、難しいのは、上記のリンクに従って、2 つのレコードが重複する原因を突き止めることです。

于 2011-08-27T02:03:02.437 に答える
0

等価関係は、特に優れた種類のマッチングです。それらは次の 3 つの特性を満たします。

  • reflexivity: 任意の値 A、A ~ A
  • 対称性: A ~ B の場合、必然的に B ~ A
  • 推移性: A ~ B および B ~ C の場合、必然的に A ~ C

これらの優れている点は、特定のセットの要素の各ペアが ~ によって関連付けられるように、データを互いに素なセットに分割できることです。したがって、union-find アルゴリズムを適用して最初にすべてのデータを分割し、次に分割内の各セットから 1つの代表的な要素を選択することができます。これにより、データの重複が完全に排除されます (「重複」とは「〜による関連」を意味します)。さらに、このソリューションは、各パーティションからどの代表をたまたま選択しても、同じ数の最終値が得られ、各最終値はペアごとに重複しないという意味で標準的です。

残念ながら、あいまい一致は等価関係ではありません。おそらく推移的ではないからです (おそらく再帰的で対称的ですが)。この結果、データを分割する標準的な方法がなくなります。どのような方法でデータを分割しようとしても、あるセットの一部の値が別のセットの値と同等である、または 1 つのセット内の一部の値が同等でないことがわかる場合があります。

では、これらの状況で、正確にどのような動作が必要ですか?

于 2011-08-25T20:10:57.503 に答える