我有一个大型数据库(可能有数百万条记录)，其中包含相对较短的文本字符串(按街道地址、姓名等顺序)。
我正在寻找一种策略来删除不精确的重复，模糊匹配似乎是选择的方法。我的问题:许多文章和问题处理匹配单个字符串对数据库中的所有记录。我希望立即对整个数据库进行重复数据删除。
前者将是一个线性时间问题(将一个值与一百万个其他值进行比较，每次计算一些相似性度量)。后者是一个指数时间问题(将每个记录的值与每个其他记录的值进行比较;对于一百万条记录，这大约是5 x 10^11次计算，而前一个选项是1,000,000次计算)。
我想知道是否有另一种方法，而不是我提到的"暴力"方法。我在考虑是否可能生成一个字符串来比较每个记录的值，然后将具有大致相同相似性度量的字符串分组，然后在这些组中运行暴力方法。我不会得到线性时间，但它可能会有所帮助。此外，如果我正确地思考这个问题，这可能会错过字符串a和B之间潜在的模糊匹配，因为它们与字符串C(生成的检查字符串)的相似性非常不同，尽管它们彼此非常相似。
任何想法?
注:我意识到我可能使用了错误的术语来描述时间复杂度——这是一个我有基本把握的概念，但还不够好，所以我不能当场把一个算法放到适当的类别中。如果我使用了错误的术语，我欢迎更正，但希望我至少表达了我的观点。
编辑
一些评论者问，给定记录之间的模糊匹配，我的策略是选择删除哪些记录(即给定"foo"，"boo"one_answers"coo"，它们将被标记为重复并删除)。我应该注意到，我并不是在寻找自动删除。这个想法是在6000多万条记录数据库中标记潜在的重复，以供人类审查和评估。如果有一些误报是可以接受的，只要它是一个大致可预测/一致的数量。我只是需要弄清楚复制人有多普遍。但如果模糊匹配传递需要一个月的时间来运行，那么这根本就不是一个选择。
看看http://en.wikipedia.org/wiki/Locality-sensitive_hashing。一种非常简单的方法是将每个地址(或其他)划分为一组重叠的n-gram。这个STACKOVERFLOW变成了集合{STACKO, TACKO, ACKOV, ckov…, RFLOW}。然后使用大型哈希表或排序归并来查找冲突的n-gram，并使用模糊匹配器检查冲突。因此，STACKOVERFLOW和SXACKOVRVLOX将发生碰撞，因为它们都与碰撞的n-gram ACKOV相关联。
下一个复杂的层次是选择一个随机的哈希函数-例如具有任意键的HMAC，并且在你找到的n个图中，只保留哈希值最小的那个。然后，您必须跟踪更少的n-gram，但只有在两种情况下最小的哈希值都是ACKOV时才会看到匹配。显然，在n-gram的长度和错误命中的概率之间存在权衡。事实上，人们似乎做的是使n相当小，并通过在同一条记录中连接多个哈希函数的结果来获得更高的精度，因此您需要同时在多个不同的哈希函数中获得匹配-我假设这样做的概率更好。尝试谷歌搜索"重复检测minhash"
我认为你可能错误地计算了所有组合的复杂性。如果一个字符串与所有其他字符串的比较是线性的，这意味着由于长度较小，每次比较是O(1)。将每个字符串与其他字符串进行比较的过程不是指数的，而是二次的，这也不全是坏事。简单来说，你比较的是nC2或n(n-1)/2对字符串，所以它就是O(n^2)
我想不出一种方法，你可以按顺序排序，因为你不能写一个客观的比较器，但即使你这样做，排序将需要O(nlogn)的归并排序，因为你有这么多的记录，可能不喜欢使用额外的内存，你会使用快速排序，这需要O(n^2)在最坏的情况下，没有改进在最坏的情况下，在蛮力。
您可以使用Levenshtein转换器，它"接受[s]一个查询词，并返回字典中与它拼写错误在n以内的所有词"。下面是一个演示
所有记录的两两比较是O(N^2)而不是指数。基本上有两种方法可以减少这种复杂性。
第一个是阻塞，在这种情况下，你只比较那些已经有一些容易计算的共同点的记录，比如前三个字母或一个共同的n-gram。这与局部敏感哈希基本相同。dedupe python库实现了许多块技术，文档对通用方法进行了很好的概述。
在最坏的情况下，带有阻塞的两两比较仍然是O(N^2)。最好的情况是O(N)在实践中，最好或最坏的情况都不会真正出现。通常，阻塞将需要比较的对的数量减少了99.9%以上。
对于不基于两两比较的记录链接，有一些有趣的、可选择的范例。它们有更好的坏情况复杂性保证。看看贝卡·斯特尔茨和迈克尔·威克的作品。
我认为这是一次性清理。我认为问题不在于做太多的比较，而在于决定哪些比较值得做。你提到了姓名和地址，所以请看这个链接，你会遇到一些比较问题。
确实，为了将一百万条记录与它们自己进行比较，你必须进行近5000亿次暴力比较，但这是假设你从未跳过任何先前声明匹配的记录(即，从不在下面的伪代码中执行j循环的"break")。
我的pokey E-machines T6532 2.2gHz对100字节的文本文件记录每秒进行140万次查找和读取，所以5000亿次比较大约需要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()，那么大多数数据库可以在一个命令行中完成上述操作。
无论如何，根据上面的链接，困难的部分将是弄清楚是什么使两个记录成为重复的。
等价关系是特别好的匹配类型;它们满足三个属性:
- 自反性:对于任意值A, A ~ A
- 对称性:如果A ~ B，则必然是B ~ A
- 传递性:如果A ~ B和B ~ C，则必然是A ~ C
的优点在于，它们允许您将数据划分为不相交的集合，使得任何给定集合中的每对元素都通过~相关联。因此，您可以做的是应用并查找算法首先对所有数据进行分区，然后从分区中的每个集合中挑选一个具有代表性的元素;这完全消除了数据的重复数据(这里的"duplicate"表示"与~相关")。此外，该解决方案是规范的，因为无论您碰巧从每个分区中选择哪个代表，您都会得到相同数量的最终值，并且每个最终值都是成对不重复的。
不幸的是，模糊匹配不是等价关系，因为它可能不是传递的(尽管它可能是自反的和对称的)。这样做的结果是，没有一个规范的方式来划分数据;你可能会发现，无论你用什么方式划分数据，一个集合中的一些值与另一个集合中的值是等价的，或者单个集合中的一些值是不等价的。
那么，在这些情况下，你到底想要什么行为呢?