ソリューションの編集 @mprivatのおかげで、これがソリューションでした。
from mysql_wrapper2 import Mysql
import Levenshtein
import time
db = Mysql()
fields = [...]
records = db.query('SELECT *, CONCAT(%s) as `string`, SOUNDEX(CONCAT(%s)) as `soundsLike` FROM records ORDER BY `soundsLike`' % (','.join(fields), ','.join(fields)))
print len(records)
matches = []
start = time.clock()
for k,v in enumerate(records):
if k+1 == len(records):
break
if Levenshtein.ratio(records[k]['string'],records[k+1]['string']) >= .98:
matches.append((records[k],records[k+1]))
print time.clock() - start
print len(matches)
エンドソリューション
重複するレコードがある（またはない）Webアプリケーション用のMySQLデータベースがあります。これらのレコードは、人物（名前、住所など）を表します。
現在、すべてのレコードをプルし、それらを帯状疱疹と比較して、管理ユーザーに重複の可能性を提示するPythonスクリプトがあります。このスクリプトは、1000レコード未満でうまく機能しました。現在、実際のデータ（89kレコード）でテストしているため、持続不可能になっています。16GBのメモリ使用量でスクリプトを停止しましたが、まだ終了したかどうかわかりません。[私はメモリを大切にしていますが、約30GBのメモリまでは速度がはるかに重要です-500kレコードを処理する場合]
その方法では、データを文書化するためにpygraphを使用し、重複を見つけるために帯状疱疹を使用しました。それはまだグラフに残っていたので、それはレコードを見終わってさえいないことを意味していると思います！
「類似した」一致を比較できるようにすることを目指しているため、フィールドの違い（「St.」や「Street」など）が一意性の根拠になることはありません。単純な同義語を扱っていない可能性があるため、同義語の置換だけを選択することはできません。ですから、あいまい一致を探していると思います。
私はいくつかの簡単な解決策を試しましたが、それらは十分に速くありません。
この場合、ハッシュは迅速に構築されますが（帯状疱疹を使用した現在の例では構築されません...約8時間構築され、終了しませんでした）、比較時の速度は恐ろしいものです（ただし、これはアルゴリズムの非効率性であり、インタープリターの速度ではありません）
私はまた、可能な限り多くのオプションを研究してきました。DNlog（n）検索のヒットの約束で、私はしばらくの間最近傍検索で立ち往生しています。
最近傍探索には2つの問題があります。それは、克服する方法をよく知っているかもしれませんが、私はできませんでした。
- すべてのキーが数値ではありません
- 現在のシステムの制約は、セット[K-Nearest Neighbor]で2つの一致のみが必要であるということですが、それらがかなり明確な一致である場合に限ります（Fixed radius Nearest Neighbor）
私はまた、ある種のクラスタリングソリューションに幸運をもたらしてきました。クラスターの数が可変である、動作するPythonライブラリをまだ見つけていません。私が見つけた、そして実装できなかったすべてのソリューションは、最終的に持つクラスターの数についての事前の知識を必要とします。
- 実際に類似している場合にのみ一致する必要があります
- いくつあるかはわかりません。
＃2の場合、答えが得られたら確かにフィルタリングできますが、どちらが良いでしょうか？しかし、それは＃1を克服できる場合にのみです。
比較しているデータに制約があるため、NNまたはクラスタリングソリューションのいずれかを暗示することができず、単純な古い比較に移行する必要がありました。そうすることで、比較ドメインの数を削除するために、すべてのレコードの値を連結し、文字列に対して他のすべての文字列に対してレーベンシュタイン比較を実行しました。このソリューションも、単に十分な速度ではありません。約20分で1つのレコードを終了しません（その時点でタイミングを停止しました）。
簡単な例として私が思いついたもの：
from mysql_wrapper2 import Mysql
import Levenshtein
db = Mysql()
# Get 89k records from the database
records = db.query(""""
SELECT *
FROM records
""")
# Build a dictionary where the keys are our records, and their IDs are our data
# Only passing ID, we only use about 3GB of memory, instead of
# > 16GB with the actual dictionaries
records_hash = {}
for i in records:
key = []
for k in i.values():
key.append(str(i))
records_hash['-'.join(key)] = i['id']
# Compare every key to every key with the Levenshtein ratio
for i in records_hash.keys():
print 'once...'
for j in records_hash.keys():
if Levenshtein.ratio(i,j) >= .75:
pass
繰り返しになりますが、これは簡単な例であり、実際に実装された場合、2つのレコードが2回チェックされていないことを確認します。
解決策はありますか？問題に合うようにNNまたはクラスタリングのいずれかを暗示する方法はありますか？私が考えていない他のパターンが役立つ可能性はありますか？私はSOLですか？