15

假设您有一个包含 10,000 个电子邮件地址的列表，并且您想查找此列表中一些最接近的“邻居”是什么 - 定义为与您列表中的其他电子邮件地址可疑地接近的电子邮件地址。

我知道如何计算两个字符串之间的Levenshtein 距离（感谢这个问题），这将为我提供将一个字符串转换为另一个字符串需要多少操作的分数。

假设我将“可疑地靠近另一个电子邮件地址”定义为 Levenshtein 分数小于 N 的两个字符串。

除了将每个可能的字符串与列表中的每个其他可能的字符串进行比较之外，是否有更有效的方法来查找分数低于此阈值的字符串对？换句话说，这种类型的问题能比 解决得更快O(n^2)吗？

Levenshtein 对这个问题的算法选择是否糟糕？

4

8 回答 8

7

是的-您可以使用BK-Tree在 O(log n) 时间内找到字符串给定距离内的所有字符串。涉及生成距离为 n 的每个字符串的替代解决方案对于 levenshtein 距离为 1 可能更快，但是对于更长的距离，工作量迅速膨胀失控。

于 2009-10-23T13:19:22.627 回答
6

这个问题被称为集群，是更大的重复数据删除问题的一部分（你可以决定集群的哪个成员是“正确的”），也称为merge-purge。

我曾经读过一些关于这个主题的研究论文（名字在下面），基本上，作者在一个排序的字符串列表上使用了一个有限大小的滑动窗口。他们只会比较（使用编辑距离算法）窗口内的N*N 个字符串，从而降低计算复杂度。如果任何两个字符串看起来相似，则将它们组合成一个簇（通过将一条记录插入一个单独的簇表中）。

第一次遍历列表之后是​​第二次遍历，其中字符串在排序之前被反转。这样，具有不同头的琴弦就有另一个机会接近到足以作为同一窗口的一部分进行评估。在第二遍中，如果一个字符串看起来与窗口中的两个（或更多）字符串足够接近，并且这些字符串已经是它们自己的集群的一部分（由第一遍找到），那么这两个集群将被合并（通过更新集群表），当前字符串将被添加到新合并的集群中。这种聚类方法称为联合查找算法。

然后，他们通过将窗口替换为前 X 个基本独特的原型列表来改进算法。每个新字符串都将与前 X 个原型中的每一个进行比较。如果 string 看起来足够接近原型之一，那么它将被添加到原型的 cluster中。如果没有一个原型看起来足够相似，则该字符串将成为一个新原型，将最旧的原型从顶部 X 列表中推出。（采用启发式逻辑来决定原型集群中的哪些字符串应该用作代表整个集群的新原型）。同样，如果字符串看起来与几个原型相似，则它们的所有集群都将被合并。

我曾经实现过这个算法用于名称/地址记录的重复数据删除，列表的大小约为 10-50 百万条记录，它运行得非常快（并且也很好地发现了重复项）。

总体而言，对于此类问题，最棘手的部分当然是找到相似阈值的正确值。这个想法是捕获所有不产生太多误报的重复数据。具有不同特征的数据往往需要不同的阈值。编辑距离算法的选择也很重要，因为一些算法更适合 OCR 错误，而另一些更适合拼写错误，而另一些则更适合语音错误（例如通过电话获取姓名时）。

一旦实现了聚类算法，测试它的一个好方法是获取一个唯一样本列表并人为地变异每个样本以产生其变化，同时保留所有变化都来自同一个父节点的事实。然后将该列表打乱并馈送到算法。将原始聚类与重复数据删除算法产生的聚类进行比较将为您提供效率分数。

参考书目：

Hernandez M. 1995，大型数据库的合并/清除问题。

Monge A. 1997，一种用于检测近似重复数据库记录的有效领域无关算法。

于 2009-10-23T22:46:24.170 回答
5

您可以使用 Levenshtein in 来完成O(kl)，其中k是您的最大距离，l 是最大字符串。

基本上，当您知道如何计算基本的 Levenshtein 时，很容易找出比k主对角线更远的每个结果都必须大于k. 所以如果你用宽度计算主对角线2k + 1就足够了。

如果您有 10000 个电子邮件地址，则不需要更快的算法。计算机可以O(N^2)足够快地计算。

Levenshtein 非常适合这类问题。

此外，您可能会考虑在比较之前使用 soundex 转换电子邮件。你可能会得到更好的结果。

于 2009-10-22T20:29:20.937 回答
2

我认为你不能比 O(n^2) 做得更好，但你可以做一些较小的优化，这可能足以让你的应用程序可用：

  • 您可以先按 @ 之后的部分对所有电子邮件地址进行排序，然后仅比较相同的地址
  • 当两个地址变得大于 n 时，您可以停止计算两个地址之间的距离

编辑：实际上你可以做得比 O(n^2) 更好，看看下面尼克约翰逊的回答。

于 2009-10-22T20:31:10.030 回答
1

假设您有 3 个字符串：

1 - “abc” 2 - “bcd” 3 - “cde”

1 和 2 之间的 L 距离为 2（减去“a”，加上“d”）。2 和 3 之间的 L 距离为 2（减去“b”，加上“e”）。

您的问题是我们是否可以通过使用上面的 2 个比较来推断 1 和 3 之间的 L 距离。答案是不。

1 和 3 之间的 L 距离为 3（替换每个字符），由于前 2 次计算的分数，无法推断出这一点。分数不显示是否执行了删除、插入或替换操作。

所以，我会说 Levenshtein 对于大名单来说是一个糟糕的选择。

于 2009-10-22T20:36:16.073 回答
1

10,000 个电子邮件地址听起来不算多。对于更大空间中的相似性搜索，您可以使用shingling和min-hashing。这个算法实现起来有点复杂，但在大空间上效率更高。

于 2009-10-22T20:39:50.117 回答
1

如果您真的在比较电子邮件地址，那么一种明显的方法是将 levenshtein 算法与域映射相结合。我可以想到有时我使用同一个域多次注册某些东西，但电子邮件地址的用户名部分有所不同。

于 2009-10-22T22:08:36.027 回答
1

在扭转问题的情况下，有可能做得更好。

我在这里假设您的 10.000 个地址非常“固定”，否则您将不得不添加更新机制。

这个想法是在 Python 中使用 Levenshtein 距离，但在“反向”模式下：

class Addresses:
  def __init__(self,addresses):
    self.rep = dict()
    self.rep[0] = self.generate_base(addresses)
      # simple dictionary which associate an address to itself

    self.rep[1] = self.generate_level(1)
    self.rep[2] = self.generate_level(2)
    # Until N

该generate_level方法从先前的集合中生成所有可能的变化，减去先前级别已经存在的变化。它将“原点”保留为与键关联的值。

然后，您只需在各种集合中查找您的单词：

  def getAddress(self, address):
    list = self.rep.keys()
    list.sort()
    for index in list:
      if address in self.rep[index]:
        return (index, self.rep[index][address]) # Tuple (distance, origin)
    return None

这样做，您计算各种集合一次（这需要一些时间......但是您可以将它序列化并永远保留它）。

然后查找比 O(n^2) 更有效，尽管准确给出它有点困难，因为它取决于生成的集合的大小。

作为参考，请查看： http: //norvig.com/spell-correct.html

于 2009-10-23T08:10:25.460 回答