私は最近、データベース内の顧客レコードの重複をチェックするアルゴリズムの開発を任されています。DB レイアウトは非常に単純です。FullName、Street、City、ZIP、Phone などのフィールドを含む数万行...
最初に少し背景を説明します。
私はアルゴリズムについて大規模な調査を行い、すべての分野がすべての状況で同じようにうまく機能するとは限らないため、さまざまなアルゴリズムを使用して特定の量ですべてのフィールドを重み付けする必要があると判断しました。たとえば、LastName の加重係数は 0.50 です。評価するときは、使用するアルゴリズムと、それらが最終決定にどの程度影響するかを選択します。
係数 0.25: JaroWinkler
係数 0.60: コサイン 2 グラム類似度
係数 0.15: DamerauLevenshtein
すべてがうまく機能し、少し調整するだけで、ほとんどエラーなく陽性を検出できます。ここまでは順調ですね。ただし、ご想像のとおり、O(n^2) の実行時間 (実際には E フォーム i=0 から i=n) は、何万ものレコードを処理する場合にはあまり効果的ではありません。言うまでもなく、積極的な最適化、コンパイラーの最適化によるスピード、マルチスレッド化などは単なる応急処置にすぎません。本当の問題は複雑さだからです。
本質的に、私は潜在的な一致を事前にフィルタリングする方法を探しており、現在これについて3日間の調査を行っています. R ツリー、R* ツリー、KD ツリー、ユークリッド ベクトル、ミンハッシングなどに関する貴重な情報を見つけました。ただし、これらすべてに関するほとんどの情報は、かなり学術的なものです。私が見つけた最も価値のあるリソースは、「大規模なデータ セットのマイニング」の第 3 章でした。
今、私の本当の質問に：
この情報をすべて読みましたが、すべてをまとめる方法がわかりません。
文字列を入れて、「一致する確率が> 0.20のすべてを見つけてください」と言うことができる、ツリーまたはグラフのデータ構造でのある種のインデックス付けについて考えていました。このアルゴリズムは非常に高速です。次に、潜在的な (>0.20) 一致のリストを取得したら、いくつかのアイテムを「高価な」が選択的なアルゴリズムと比較することができます。これにより、実行時間が非常に妥当な値になるはずです。
上記のことを行うための何らかの参照コードを見つけようとしていますが、学術論文以外には何も思いつかないようです。実際にコンパイルされた「simstring」を見つけましたが、7つのテストレコードとうまく一致していないようでした..誰かが私を正しい方向に向けることができますか? 確かに、誰かが以前にこれに遭遇し、解決策を見つけたに違いありません...
事前にどうもありがとうございました！
PS 私はこれを C++ で行っていますが、C#/C/Java/PHP のサンプルは問題ありません。