複数のWebサイトから抽出したレストランのタイミングと住所情報のデータベースの構築に取り組んでいます。同じレストランの情報が複数のWebサイトに存在する可能性があるため。したがって、データベースには、ほぼ重複するコピーがいくつかあります。
レストランの数が多いので、たとえば100000です。次に、新しいエントリごとに、100000 ^ 2の順序で比較して、ほぼ同じ名前のレストラン情報がすでに存在するかどうかを確認する必要があります。ですから、それよりも優れた効率的なアプローチがあるかどうかを尋ねています。ありがとうございました。
基本的に、レコード連携ツールを探しています。これらのツールは、レコードを索引付けして、各レコードについて潜在的な候補の小さなセットをすばやく見つけ、それらをより詳細に比較することができます。これにより、O(n^2) 問題が回避されます。また、比較前のデータのクリーニングや、レーベンシュタインや q-gram などのより洗練されたコンパレーターもサポートしています。
ウィキペディアのレコード連携ページにツールの一覧がありましたが、削除されました。探しに行きたい場合は、バージョン履歴にまだ残っています。
これには、インデックス作成に Lucene を使用し、詳細なコンパレーターが組み込まれているDukeという独自のツールを作成しました。これを使用して、220,000 のホテルの重複除去に成功しました。この重複排除は、ラップトップで 4 つのスレッドを使用して数分で実行できます。
1 つのアプローチは、既存のレストランの小さなセットを検索して新しいレストランと比較できるように、類似度関数を構築することです。このルックアップはデータベース内のインデックスを使用するため、高速である必要があります。
類似度関数を定義する方法は難しい部分です:) 通常、各レコードを一連のトークンに変換できます。各レコードはデータベースで検索され、類似している可能性のあるレコードを見つけます。
クロールされたデータの重複に近いものを見つけるために構築したシステムについて説明するために私が書いたこのブログ投稿を参照してください。やりたいことと非常に似ているように聞こえますが、ユースケースが小さいため、実装はよりシンプルにする必要があると思います。