19

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

我正在寻找一种删除不精确重复的策略，模糊匹配似乎是首选方法。我的问题：许多文章和 SO 问题都涉及将单个字符串与数据库中的所有记录进行匹配。我希望立即对整个数据库进行重复数据删除。

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

我想知道除了我提到的“蛮力”方法之外是否还有另一种方法。我正在考虑可能生成一个字符串来比较每个记录的值，然后对具有大致相等相似性度量的字符串进行分组，然后通过这些组运行蛮力方法。我不会达到线性时间，但它可能会有所帮助。此外，如果我考虑得当，这可能会错过字符串 A 和 B 之间潜在的模糊匹配，因为它们与字符串 C（生成的检查字符串）的相似性非常不同，尽管它们彼此非常相似。

有任何想法吗？

PS 我意识到我可能使用了错误的时间复杂度术语——这是一个我基本掌握的概念，但还不够好，所以我可以当场将算法归入正确的类别。如果我用错了术语，我欢迎更正，但希望我至少能明白我的意思。

编辑

一些评论者问，鉴于记录之间的模糊匹配，我的策略是选择删除哪些记录（即给定“foo”、“boo”和“coo”，它们将被标记为重复并删除）。我应该注意，我不是在这里寻找自动删除。这个想法是在一个 60 多万条记录数据库中标记潜在的重复项，以供人工审查和评估。如果有一些误报是可以的，只要它是一个大致可预测/一致的数量。我只需要了解重复项的普遍性。但是如果模糊匹配传递需要一个月的时间来运行，那么这甚至不是一个选项。

4

6 回答 6

13

看看http://en.wikipedia.org/wiki/Locality-sensitive_hashing。一种非常简单的方法是将每个地址（或其他）分成一组重叠的 n-gram。此 STACKOVERFLOW 变为集合 {STACKO, TACKO, ACKOV, CKOVE... , RFLOW}。然后使用大型哈希表或排序合并来查找冲突的 n-gram 并使用模糊匹配器检查冲突。因此，STACKOVERFLOW 和 SXACKOVRVLOX 将发生冲突，因为两者都与冲突的 n-gram ACKOV 相关联。

更复杂的下一个级别是选择一个随机散列函数 - 例如具有任意键的 HMAC，并且在您找到的 n-gram 中，只保留具有最小散列值的那个。然后您必须跟踪更少的 n-gram，但只有在两种情况下的最小散列值都是 ACKOV 时才会看到匹配。在 n-gram 的长度和错误命中的概率之间显然需要权衡取舍。事实上，人们似乎做的是通过将同一记录中多个哈希函数的结果连接起来，使 n 变得非常小并获得更高的精度，因此您需要同时在多个不同的哈希函数中获得匹配 -我认为这样的概率会更好。尝试谷歌搜索“重复检测 minhash”

于 2011-08-25T20:17:41.990 回答
3

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

我想不出一种方法可以按顺序对它们进行排序，因为你不能写一个客观的比较器，但即使你这样做，排序也需要 O(nlogn) 进行合并排序，因为你有这么多记录，可能更喜欢使用 no额外的内存，你会使用快速排序，在最坏的情况下需要 O(n^2)，在最坏的情况下没有任何改进。

于 2011-08-25T19:38:29.423 回答
3

您可以使用Levenshtein 转换器，它“接受 [s] 一个查询术语并返回 [s] 字典中所有在 n 个拼写错误范围内的术语”。 这是一个演示。

于 2016-02-16T01:54:42.287 回答
2

所有记录的成对比较是 O(N^2) 不是指数的。基本上有两种方法可以减少这种复杂性。

第一个是阻塞，你只比较已经有一些共同点且易于计算的记录，比如前三个字母或一个常见的 n-gram。这与本地敏感散列基本相同。dedupe python 库实现了许多阻塞技术，文档很好地概述了一般方法。

在最坏的情况下，与阻塞的成对比较仍然是 O(N^2)。在最好的情况下，它是 O(N)。在实践中，最好或最坏的情况都没有真正得到满足。通常，阻塞可将要比较的对数减少 99.9% 以上。

记录链接有一些有趣的替代范例，它们不基于成对比较。这些具有更好的更坏情况复杂性保证。查看 Beka Steorts 和 Michael Wick 的作品。

于 2016-09-17T01:07:01.117 回答
1

我认为这是一次性清理。我认为问题将不必进行如此多的比较，而必须决定哪些比较值得进行。您提到了姓名和地址，因此请参阅此链接以了解您将遇到的一些比较问题。

确实，您必须进行近 5000 亿次蛮力比较才能将一百万条记录与自己进行比较，但这是假设您从未跳过任何先前声明为匹配的记录（即，从未在下面的伪代码）。

我的 pokey E-machines T6532 2.2GHz 每秒可以进行 140 万次搜索和读取 100 字节文本文件记录，因此 5000 亿次比较大约需要 4 天。而不是花 4 天时间研究和编写一些奇特的解决方案（只是发现我还需要另外 x 天来实际运行），并假设我的比较例程无法计算和保存我要比较的键，我' d 只是让它蛮力所有这些比较，而我找到其他事情要做：

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()

如果允许您调用自己的自定义代码来计算每条记录的模糊键（），大多数数据库都可以在一个命令行中执行上述操作。

无论如何，根据上面的链接，困难的部分将是弄清楚是什么使两条记录重复。

于 2011-08-27T02:03:02.437 回答
0

等价关系是一种特别好的匹配。它们满足三个性质：

  • 自反性：对于任何值 A，A ~ A
  • 对称性：如果 A ~ B，那么必然是 B ~ A
  • 及物性：如果 A ~ B 和 B ~ C，那么必然是 A ~ C

使这些好的原因在于它们允许您将数据划分为不相交的集合，以便任何给定集合中的每对元素都通过 ~ 关联。所以，你可以做的是应用联合查找算法首先对所有数据进行分区，然后从分区中的每个集合中挑选一个代表元素；这完全消除了数据的重复数据（其中“重复”表示“与〜相关”）。此外，这个解决方案是规范的，无论您碰巧从每个分区中选择哪个代表，您都会获得相同数量的最终值，并且每个最终值都是成对不重复的。

不幸的是，模糊匹配不是等价关系，因为它可能不是传递的（尽管它可能是自反和对称的）。这样做的结果是没有一种规范的方法来划分数据。您可能会发现，无论您尝试以何种方式对数据进行分区，一组中的某些值与另一组中的值等价，或者单个组中的某些值不等价。

那么，在这些情况下，您究竟想要什么行为？

于 2011-08-25T20:10:57.503 回答