1

编辑解决方案 这是解决方案，感谢@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来记录数据，并使用 shingles 来查找重复项。它仍然停留在图表中——所以我假设这意味着它甚至还没有完成查看记录！

我们希望能够比较“相似”匹配，因此字段（如“St.”和“Street”）的差异不会成为唯一性的理由。我们可能不会处理简单的同义词，因此仅替换同义词不是一种选择。所以我想我们正在寻找模糊匹配。

我尝试了一些简单的解决方案，但速度不够快。

尽管在这种情况下哈希构建速度很快（当前的带状疱疹示例没有......它构建了大约 8 个小时并且没有完成），但它的比较速度是可怕的（但这是算法效率低下，而不是解释器速度）

我也一直在研究尽可能多的选择。一段时间以来，我一直坚持使用最近邻搜索，并承诺 DNlog(n) 搜索。

最近邻搜索有两个问题，你可能很清楚如何克服，但我一直没能做到：

  1. 并非所有键都是数字的
  2. 我们当前系统的限制是我们只需要一组 [K-Nearest Neighbor] 中的两个匹配项，但前提是它们是非常明确的匹配项（固定半径最近邻）

我也很幸运地使用了某种集群解决方案。我还没有找到一个可用的 python 库，其中包含可变数量的集群。我发现并且无法实施的每个解决方案都需要预先了解最终要拥有的集群数量。

  1. 我们应该只在它们实际上相似时才匹配
  2. 我们不知道会有多少，如果有的话。

对于#2，一旦我们有答案，我们当然可以过滤，但哪个更好？但这只有在＃1可以被克服的情况下。

由于我们正在比较的数据受到限制，我还没有能够实现 NN 或聚类解决方案，并且不得不转向普通的旧比较。这样做时，为了删除比较域的数量，我连接了所有记录的值，并对字符串与所有其他字符串进行了 Levenshtein 比较。这个解决方案也不够快。它不会在大约 20 分钟内完成一条记录（我当时停止计时）。

我想出了一个简单的例子：

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

再一次，这是一个微不足道的例子，如果实际实施，将确保没有两条记录被检查两次，等等。

有什么解决办法吗？有没有一种方法可以实现 NN 或 Clustering 来解决我的问题？有没有其他我不考虑的模式可以提供帮助？我是索尔吗？

4

3 回答 3

4

我实际上并没有尝试过，您可能会发现它不起作用，但无论如何我都会分享，因为如果我遇到同样的问题，我会尝试这样做。

我会在表中添加一个新列。然后，我将浏览所有记录并执行以下操作：

  1. 将名字、姓氏、地址等连接成一个字符串，我将为其计算类似 Soundex 的字符串（或根据您的需要稍作修改，例如，如果有数字，则保留数字，删除非字母数字字符，添加支持长字符串等...）

  2. 然后我会计算 soundex 代码并将其存储在我的新列中

然后，假设 soundex 完成了它的工作，您可以查询记录，按 soundex 排序，然后应用您已有的比较逻辑。这个想法是只比较排序结果集中彼此附近的记录。

我所说的 soundex-like 是指与普通的 soundex 不同，后者是一个字母和三个数字。但这不适用于长字符串。可能使用三个以上的数字。

无论如何，只是想给你另一个探索的途径......

于 2012-08-08T14:59:00.953 回答
0

据我所知，最快的方法很可能只在 MySQL 中完成。

我也必须在我的一张大表中找到所有重复项，我做了这样的事情：

DELETE FROM t1 
where t1.id in (SELECT clonet1.id from t1 origine, t1 clone 
    WHERE clone.id != origine.id AND clone.id > origine.id AND ...

然后将 ... 替换为您的比较标准。

如果您在表中添加正确的索引，它应该足够快。

当我这样做时，我有数百万个字段要检查，但我只寻找直接的“=”。

不过，我从未见过比循环搜索更慢的简单 Where...

就像 mprivat 所说，它更多的是给你一种搜索方式，而不是一个实际的解决方案......我希望它会有所帮助。

于 2012-08-08T15:06:46.307 回答
0

我意识到您说这可能不切实际，但我认为您最好以某种方式标准化您的数据，以便 St. vs street 不成问题。当然，你选择哪一个取决于你，但同时拥有这两者只会让事情变得过于复杂。

然后你可以使用布隆过滤器，假设你有很多独特的和相对较少的重复。布隆过滤器是一种概率集合数据结构，可以添加元素并测试成员资格。在测试成员资格时，它可以给出两个答案之一：“这个元素肯定不在集合中”或“这个元素几乎肯定在集合中”。这使您可以扔掉大量唯一性并将输入减少到可以在合理的内存量中使用传统算法的位置。该过程的后一阶段使事情恢复到精确性——布隆过滤器只是减少了精确算法需要考虑的输入数量。

我在http://stromberg.dnsalias.org/~strombrg/drs-bloom-filter/有一个 Python 的布隆过滤器实现。当然，还有其他人。

于 2012-08-08T15:56:45.057 回答