是-您可以通过使用 BK-Tree .对于Levenshtein距离为1的情况,使用距离n生成每个字符串的替代解决方案可能更快,但对于较长的距离,工作量会迅速超出控制范围。

你可以和Levenshtein一起做 O(kl) 在哪里 k 是你最大的距离,L是最大的字符串。

基本上,当你知道如何计算基本的列文士登时,你很容易就会发现每一个结果都比 K 从主对角线开始必须大于 K . 所以如果你用宽度计算主对角线 2k + 1 就够了。

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

列文施泰因对这类问题很在行。

另外,你可能会考虑在比较之前用Soundex转换电子邮件。你可能会得到更好的结果。

这个问题被称为 聚类 是一个更大的 重复删除 问题(决定集群中哪个成员是“正确”的),也称为 合并清除 .

我曾经读过一些关于这个主题的研究论文(名字如下),基本上,作者使用 有限尺寸的滑动窗 在已排序的字符串列表上。他们只会比较(使用 edit distance 算法)n*n字符串 里面 窗口,从而降低了计算的复杂性。如果任何两个字符串看起来相似,则将它们组合成 集群 (通过将记录插入到单独的集群表中)。

第一次通过列表后是 第二关 弦在哪里? 颠倒的 在排序之前。这样弦 不同头部 有另一个接近的机会被评估为同一窗口的一部分。在第二遍中,如果一个字符串看起来足够接近窗口中的两个(或更多)字符串,并且这些字符串已经是它们自己集群的一部分(在第一遍中找到),那么两个集群将是 合并 (通过更新集群表)和当前字符串将添加到新合并的集群中。这种聚类方法被称为 联合查找 算法。

然后他们改进了算法,将窗口替换为前X个列表。 非常独特的原型 . 每个新字符串将与前X个原型进行比较。如果字符串看起来足够接近其中一个原型,那么它将被添加到 原型集群 . 如果没有一个原型看起来足够相似,那么字符串将成为一个新的原型, 推出最古老的原型 在前X个列表中。(使用了一种启发式逻辑来决定原型集群中的哪些字符串应该用作表示整个集群的新原型)。同样,如果字符串看起来类似于几个原型,那么它们的所有集群都将被合并。

我曾经为名称/地址记录的重复数据消除实施过这种算法,列表的大小大约为1000-5000万条记录,而且工作非常快(而且发现重复也很好)。

总的来说,对于这些问题,最棘手的部分当然是找到 相似性阈值 . 其目的是捕获所有产生过多数据的dup。 假阳性 . 具有不同特征的数据往往需要不同的阈值。选择编辑距离算法也很重要,因为有些算法对OCR错误更好,而另一些算法对打字错误更好,而另一些算法对语音错误更好(例如通过电话获取姓名)。

一旦实现了聚类算法,测试它的一个好方法是获得一个唯一样本列表,然后 对每个样本进行人工变异 产生它的变体,同时保留所有变体都来自同一父代的事实。然后,这个列表被洗牌并送入算法。将原始群集与重复数据消除算法生成的群集进行比较,可以得到 效率得分 .

参考文献:

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

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

我不认为你能做得比O(n^2)更好,但是你可以做一些较小的优化,这可能仅仅是为了使你的应用程序可用而加速:

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

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

10000个电子邮件地址听起来不算太多。在更大的空间进行相似性搜索时,可以使用 shingling 和 min-hashing . 该算法实现起来有点复杂,但在大空间上效率更高。

在扭转问题的情况下,可以做得更好。

我认为您的10000个地址是相当“固定”的,否则您必须添加一个更新机制。

其思想是在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 方法从上一个集合中生成所有可能的变化,减去在上一个级别上已经存在的变化。它将“origin”保留为与键关联的值。

然后,您只需在不同的集合中查找您的单词:

  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

假设您有三个字符串:

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算法与域映射相结合。我可以想象我曾经多次使用同一个域注册某个东西,但是电子邮件地址的用户名部分有所不同。