少于指数时间的模糊匹配去重？

Question

我有一个庞大的数据库（可能有数百万条记录），其中包含相对较短的文本字符串（例如街道地址、姓名等）。

我正在寻找一种策略来删除不精确的重复项，模糊匹配似乎是最佳选择的方法。问题在于：许多文章和Stack Overflow问题处理将单个字符串与数据库中的所有记录进行匹配。我希望一次性对整个数据库进行去重。

前者将是一个线性时间问题（每次将一个值与其他一百万个值进行比较，计算一些相似度量）。后者是指数时间问题（将每个记录的值与其他记录的每个值进行比较；对于100万条记录，这大约需要5 x 10^11次计算，而前者选项只需要1,000,000次计算）。

我想知道是否有另一种方法可以代替我提到的“蛮力”方法。我考虑可能会生成一个字符串来将每个记录的值进行比较，然后将具有大致相等相似度度量的字符串分组，随后通过这些组运行“蛮力”方法。虽然无法实现线性时间，但这可能有所帮助。此外，如果我思考正确，这可能会因其与检查字符串C的相似度非常不同而错过字符串A和B之间的潜在模糊匹配，尽管它们非常相似。

有什么想法吗？

附言：我意识到我的时间复杂度可能有误 - 这是我基本掌握的概念，但不足以让我立即将算法放在正确的类别中。如果我使用了错误的术语，欢迎更正，但希望我至少能传递我的观点。

编辑

一些评论者问道，在记录之间存在模糊匹配的情况下，我选择哪些记录进行删除的策略是什么（例如，“foo”，“boo”和“coo”，哪一个会被标记为重复并删除）。我应该指出的是，我不是在寻求自动删除。这个想法是为了标记潜在的重复项，并交由人类审查和评估。如果有一些误判也没关系，只要它是大致可预测/一致的数量即可。我只需要了解重复项有多普遍。但是，如果模糊匹配需要一个月的时间才能运行，那么这根本就不是首选。

- Dave W.

---

第二种方法相比第一种方法提供了更高的准确性... 但是你不需要那么多的计算。假设你一开始给每个记录一个唯一的标识符，并在匹配某些内容时更改这些标识符，随着时间的推移，记录的数量会减少。 - Ben

但是每个记录可能有多个重复项，我关心的是单次遍历的运行时间。因此，我认为边进行更改行ID不会节省任何时间。显然，防止未来的重复项更容易，因为它只是将新插入的记录与所有其他记录进行比较 - O（1）时间。但第一次遍历需要O（n ^ 2）时间，对于拥有6300万条记录和严格限制硬件的情况，我们需要数月的计算时间才能完成单次遍历。因此，我需要更快的选项... - Dave W.

Answer 1

请查看http://en.wikipedia.org/wiki/Locality-sensitive_hashing。一种非常简单的方法是将每个地址（或其他内容）分成一组重叠的n-gram。例如 STACKOVERFLOW 可以被分成集合{STACKO，TACKO，ACKOV，CKOVE...，RFLOW}。然后使用大型哈希表或排序合并查找相互碰撞的n-grams，并使用模糊匹配来检测碰撞。因此，STACKOVERFLOW 和 SXACKOVRVLOX 将发生碰撞，因为它们都与具有碰撞的n-gram ACKOV 相关联。

在更高级别的技术中，可以选择一个随机的哈希函数，例如具有任意键的HMAC，并且从找到的n-grams中仅保留具有最小哈希值的n-gram。然后，您只需要跟踪较少的n-grams，但只有在两种情况下最小的哈希值都是ACKOV时才会看到匹配项。显然，在n-gram长度和误报概率之间存在权衡。事实上，人们似乎会将n设置得很小，并通过在同一记录中串联多个哈希函数的结果来获得更高的准确性，这样就需要同时在多个不同的哈希函数中获得匹配，我认为这种方法的概率更好。尝试在 Google 上搜索“duplicate detection minhash”。

- mcdowella

---

是的！我认为这可能就是我正在寻找的东西。我对LSH进行了一些阅读，但在实现方面有些迷失。该想法似乎是以这样的方式计算值的哈希，以使相似的值具有高概率的冲突哈希。然后您可以在具有碰撞哈希的值上运行更精确的算法。基本上，降低维数以减少计算强度。我不理解要使用什么哈希函数-它们不是设计用来尝试最小化冲突吗？我们是在谈论诸如SHA或MD5之类的散列函数吗？ - Dave W.

好的哈希函数 - 如SHA - 被定义为看起来像随机函数，它们产生的冲突比一些非常糟糕的哈希函数要少。但是，证明局部敏感哈希（LSH）的计算假定完全随机的哈希函数作为构建块，所以这很好。糟糕的哈希函数通过将相似的输入哈希到相同的输出来产生冲突，但是LSH根本不依赖于此。它只依赖于哈希函数的一致性，因此如果h(ACKOV) = 13在一个地方，h(ACKOV) = 13在另一个地方。如果您找到了一个好的LSH实用写作，使用写作中的哈希函数。 - mcdowella

我认为这很有道理 :) ... 你知道这样的写作，或者至少一个方向去寻找吗？到目前为止，我的尝试大多都是徒劳无功的。我找到了几个高度技术化的资源，但是考虑到我的背景，它们比我能够处理的更加复杂。 - Dave W.

我从未在实践中做过这个 - 只是在注意到时试图跟上文献。然而，快速的网络搜索找到了一个网站 http://nlp.stanford.edu/IR-book/html/htmledition/near-duplicates-and-shingling-1.html ，看起来不太难读懂。一如既往，请记住您可以切割掉您不想要的文件 - 也就是说，对于您无用的文件可能仍然提供有用的关键词以进行更多的网络搜索。 - mcdowella

Answer 2

你可以使用Levenshtein transducer，它可以“接受一个查询词并返回与之相差n个拼写错误的字典中的所有词”。这里有一个演示。

- 1''

Answer 3

我认为你可能错误地计算了所有组合的复杂度。如果将一个字符串与所有其他字符串进行比较是线性的，这意味着由于长度很小，每个比较都是O(1)。将每个字符串与每个其他字符串进行比较的过程不是指数级别的，而是二次的，这并不完全是坏事。简单来说，您正在比较nC2或n(n-1)/2对字符串，因此它只是O(n^2)。

我想不到任何方法可以按顺序对它们进行排序，因为您无法编写客观比较器，但即使您这样做，排序也需要O(nlogn)的时间复杂度，使用归并排序，由于您有如此多的记录，可能更喜欢不使用额外的内存，所以您会使用快速排序，在最坏情况下，它的时间复杂度是O(n^2)，与暴力破解的最坏情况时间没有改进。

- Adithya Surampudi

---

我猜我的“check-string”是我希望实现客观比较器的希望。你认为这不可能吗？我对自己在问题中提到的怀疑并不确定 - 这种比较器方法是否会错过类似的一对？此外，感谢您提供复杂度时间，我不确定我是否使用了正确的术语。但即使复杂度没有改进，实际运行时间也会改善，不是吗？因为暴力算法必须在每个周期内进行密集的字符串相似性计算，但排序只是将相似性评分与客观比较器进行比较，这是一种更快的计算方法。 - Dave W.

我想不出一个比较器，考虑三个字符串abcd、efcd和abef。任意两个字符串之间恰好相差2个字符，那么应该按照什么顺序排列呢？这6种排列方式都是有意义的。如果你能想出一个非常聪明的比较器，那么在平均情况下可以做到O(nlgn)，但我想不出来，也许你需要在小数据集上尝试一些比较器并观察。其中一个比较器是编辑距离，http://en.wikipedia.org/wiki/Edit_distance。 - Adithya Surampudi

考虑到给定的字符串 "abcd"、"efcd" 和 "abef"，我想将它们与某种“中立”的任意检查字符串进行比较，以充当比较的第三方。例如，将每个值与 "abcdef" 进行比较，使用成对距离作为比较函数（http://www.catalysoft.com/articles/StrikeAMatch.html）。"abcd" 有三对，而 "efcd" 和 "abef" 只有两对。因此，您可以获取所有具有两对的值，并在它们之间运行精确比较。也许可以使用不同的检查字符串进行多次重复，以获得更高的准确性。 - Dave W.

是的先生，那绝对是一种做事情的方式，它只不过是多次运行您在问题中提到的线性时间算法。 - Adithya Surampudi

那么你有什么建议如何最有效地构建这个“检查字符串”吗？我想包含字母表中的每个字母组合，并使用成对距离比较函数进行相似性检查。我认为这种方法是最保守的（它不会错过任何可能的重复项，但会出现大量误报）。但是，这个检查字符串将超过一千个字符 - 我认为非常低效。 - Dave W.

Answer 4

对所有记录进行两两比较的复杂度为O(N^2)，而不是指数级别。基本上有两种方法来降低这种复杂性。

第一种是阻塞，其中您只比较已经具有易于计算的共同点的记录，例如前三个字母或常见的n-gram。这基本上与局部敏感哈希的想法相同。 dedupe python library 实现了许多阻塞技术，文档提供了概述。

在最坏的情况下，使用阻塞进行两两比较仍然是O(N^2)。在最好的情况下，它是O(N)。实际上通常既不是最好的也不是最坏的情况。通常，阻塞将要比较的对数减少了99.9%以上。

还有一些有趣的、不基于两两比较的记录链接替代范式。这些具有更好的最坏情况复杂性保证。请参见Beka Steorts和Michael Wick的工作。

- fgregg

Answer 5

我猜这是一次性的清理工作。我认为问题不在于要进行太多比较，而在于决定哪些比较值得进行。你提到了姓名和地址，所以可以参考this link了解一些你可能会遇到的比较问题。

确实，如果要将一百万条记录与自身进行比较，就需要进行近5000亿次暴力比较，但这是假设你从未跳过任何已经被声明为匹配的记录（即从未在下面的伪代码中使用“break”语句）。

我的E-machines T6532 2.2gHz电脑每秒可以处理1.4m个100字节文本文件记录的查找和读取，因此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()，大多数数据库可以在一条命令行中完成上述操作。

无论如何，根据上面的链接，难点在于弄清楚什么使两个记录成为重复记录。

- Witness Protection ID 44583292

---

你使用什么语言/环境来实现每秒1.4百万次的查找和读取？你发布的第一个代码示例是我目前正在使用的方法。在我的次要笔记本电脑上运行（承认这是一种性能较差的设置），我估计需要一个月的时间来计算5000亿个比较。此外，我不理解你的第二个代码示例——fuzzykey()函数调用会将什么写入scratchfile？为什么要对scratchfile进行排序？按字母顺序排序的相邻字符串（即你的scratchfile）会错过只有转置字符的重复项（例如“foobar”与“ofobar”）。 - Dave W.

此外，根据我对正在处理的数据的了解，实际重复计数不太可能占数据库中所有记录的大部分，因此在粗略的第一次去重操作中进行去重不会显著减少记录数量，从而使未来的暴力扫描更快。 - Dave W.

我正在使用Delphi，但速度来自于使用文本文件+避免数据库驱动程序。用于fuzzykey()的是一个$64问题。这是您决定两个记录是否重复的标准，并且是您最终会花费大部分时间解决的问题。根据链接文档中的合并/清除策略/战术，fuzzykey()可能是名称的SortedSoundex，地址的CASS-scrubbed输出，电话号码的仅数字过滤器等。排序将密钥聚集在一起。例如，“foobar”和“ofobar”的SortedSoundex都相同，PO BOX 1和BOX 1的CASS相同，等等。 - Witness Protection ID 44583292

如果你的列表确实是姓名和地址，我不会接这份工作，除非我被允许对地址进行CASS认证。我会(1)将RECORD ID、LASTNAME、ADDRESS、ZIP导出到一个固定字段文本文件中，并为DUPDTECT在http://www.semaphorecorp.com/mpdd/dupdtect.html使用留出GROUP和MEMBER字段的空间，(2)对所有地址进行CASS处理，(3)让DUPDTECT基于相同的姓名/地址/邮编为所有重复项分配组和成员编号，然后(4)导入RECORD ID/GROUP/MEMBERS以供审核或删除。如果电话号码可用，我会包括它们以提高重复项检测的质量。 - Witness Protection ID 44583292

CASS不适用于此工作。Soundex和其他基于发音的模糊匹配算法都不适用（即公司名称字段中，“Joe's Plumbing Inc.”和“Joe's Plumbing Incorporated”是重复的，以及任何单词顺序不正确的情况-发音会错过这个，不是吗？）。选择一个模糊匹配算法现在不是困难的部分-可能是pair distance或Levenshtein。我只需要一种快速运行比较的方法。此外，“我不会接受这份工作”的选项不可行。 - Dave W.

Answer 6

等价关系是一种特别好的匹配方式，它们满足三个属性：

• 自反性：对于任何值 A，A ~ A
• 对称性：如果 A ~ B，则必然有 B ~ A
• 传递性：如果 A ~ B 和 B ~ C，则必然有 A ~ C

这些属性之所以好，是因为它们允许您将数据分成不相交的集合，使得给定集合中任意一对元素都通过 ~ 相关联。因此，您可以先将并查集算法应用于所有数据进行分区，然后从每个分区中选择一个单独的代表元素；这样可以完全去重数据（其中“重复”意味着“通过 ~ 相关”）。此外，这个解决方案是规范化的，因为无论您从每个分区中选择哪些代表，您都会得到相同数量的最终值，并且每个最终值都是成对不重复的。

不幸的是，模糊匹配并不是等价关系，因为它可能不是传递性的（虽然它可能是自反和对称的）。这导致的结果是没有一种规范的方式来分割数据；你可能会发现无论你尝试如何分割数据，某些值在一个集合中等价于另一个集合中的值，或者某些来自单个集合的值不等价。

那么，在这些情况下，你想要什么样的行为呢？

- Daniel Wagner

---

我不确定我理解了你的回答，如果这不是你要找的，我很抱歉！那么你的意思是：当我根据数据之间的某些关系将数据分割时，由于模糊匹配无法满足传递性，所以不能保证创建的成对数据将包含所有实际上相似（满足该关系）的数据对；或者说，所有满足条件的数据对都会出现，但也会有一些误报。在这种情况下，我更喜欢准确性，所以如果有选择，我会选择后者。但我可能误解了你的回答 :) - Dave W.

这里是说明困境的最简单的例子。假设 ~ 表示“编辑距离为1”。我们有单词“goo”、“foo”和“food”。它们应该如何去重？在结果 {"goo", "food"} 中没有重复项（而剩余项“foo”至少与其中一个重复）；在结果 {"foo"} 中也没有重复项（而剩余项“goo”和“good”各自至少与其中一个重复）。但这两个结果显然不同。你更喜欢哪一个？你能说出为什么更喜欢那个结果吗？ - Daniel Wagner

假设有单词“goo”、“foo”和“food”，以及一个“重复”阈值为1个编辑距离，我认为“goo”和“foo”应该匹配（即被标记为可能的重复项），而“foo”和“food”也应该如此，但“goo”和“food”不应该被标记为重复项，因为它们之间相差2个编辑距离。但这似乎相对简单，所以我想我可能没有理解您的评论（再次！）。感谢您耐心解释，我非常感激！ - Dave W.

我同意你所声称的匹配。在去重过程结束时，基于这些匹配，哪些将被移除？ - Daniel Wagner

我应该让这部分更加清晰（我将编辑问题以包括此内容）：我不打算自动删除任何记录。我只想标记那些相似度高于某个阈值的记录（即Levenshtein编辑距离<3），作为潜在的重复记录。我有一种单独的方法来存储这些标记 - 我只需要一种快速计算所有记录之间（技术上是所有可能的记录组合）相似性指标的方法。这个想法最终是要为人类审查做好标记，但现有的6300万条记录需要缩小到一个可管理的大小。 - Dave W.