高效率的方式计算相似的成绩的字符串的时候样品尺寸大？

StackOverflow https://stackoverflow.com/questions/1609742

题

让我们说你有一个列表中的10 000名电子邮件地址，而你想找什么样的一些最亲密的"邻国"在这个列表中的定义作为电子邮件地址可疑附近的其他电子邮件地址列表。

我知道如何计算 Levenshtein distance 两个字符串之间(的感谢 这个问题)，这将给我，这是你的如何许多行动都需要改变一串到另一个。

让我们说，我界定"可疑靠近另一个电子邮件地址"由两个串具有Levenshtein分数小于N。

是否有更有效的方式找到对串的分数低于该阈值之一，比较每一个可能的串到其他每一个可能的串的清单？换句话说，可以此类问题可以解决快 O(n^2)?

是编辑，这是你的一个糟糕的选择的算法对这个问题？

有帮助吗？

解决方案

是的 - 您可以使用 BK-Tree 。当levenshtein距离为1时，涉及生成距离为n的每个字符串的替代解决方案可能会更快，但是工作量会在较长距离内迅速失控。

其他提示

您可以在 O（kl）中使用Levenshtein，其中 k 是您的最大距离，l是最大字符串。

基本上当你知道如何计算基本的Levenshtein时，很容易发现每个比主对角线的 k 更大的结果必须大于 k 。因此，如果您计算宽度 2k + 1 的主对角线就足够了。

如果您有10000个电子邮件地址，则无需更快的算法。计算机可以用 O（N ^ 2）计算得足够快。

Levenshtein非常善于解决这类问题。

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

这个问题被称为 集群 并且是一个更大的 删除重复数据 问题(其中你决定它成员的集群"的权利"之一)，也被称为 合并清除.

我曾经读过一些研究论文的正是这一专题的名称(以下)，并基本上，提交人使用 一个有限的大小的滑动窗 一整串名单。他们只会比较(使用 编辑距离 算法)N*N字符串 内部 窗口，从而降低了计算的复杂性。如果任何两个串看起来相似，他们组合成一个 集群 (通过插入一个记录到一个单独的集群表)。

第一次通过该名单随后由 第二通行证 那里的字符串 颠倒 之前获得的排序。这样的字符串 不同的头 还有另外一个机会，得到足够接近被评为部分相同的窗口。在这第二通行证，如果一串看起来足够接近的两个(或更多)串的窗口，这些字符串中已经部分他们自己的集群(发现，通过第一轮)，这两个集群会随后可以 合并 (通过更新的集群表)和目前的串将增加新合并的集群。这个聚类方法被称为 联盟-找到 算法。

然后他们改进的算法通过更换窗口的一个列表X 基本上唯一的原型.每一个新的串将比每个顶X原型。如果串看起来足够接近的一个原型，随后将加入 原型的集群.如果没有原型看起来足够相似，串将成为一个新的原型， 推动最古老的原型了 顶X名单。(那是一个试探采用逻辑来决定哪些字符串中的原型的集群应用作新的原型代表整个集群)。再次，如果串看起来类似于几个原型，它们的所有集群将被合并。

我曾经实施这种算法，对删除重复的名称/地址记录与大小的名单被周围的10-50万的记录和它的工作漂亮的该死的快速(和发现重复及太)。

整体对于这样的问题，最棘手的部分当然是找到正确的价值 相似性阈值.这个想法是要捕获所有的dup w/o产生太多 误报.数据有不同的特点往往需要不同的阈值。选择一个编辑距离算法也是重要的，因为一些算法更适用于OCR错误，而其他人都更好地用于打字错误，但其他人都更好的用语音错误(如当得到一个名字过电话)。

一旦聚类的算法是实现的，一个良好的方式来测试它是得到一个列表中的唯一样品和 人为地改变每个样品 产生的变化，同时保留事实上，所有的变化都来自相同的父母。这个名单，然后洗牌和喂养的算法。比较原始的集群的聚集产生的清除重复算法会给你的 效率高的分数.

参考书目：

M.Hernandez1995年， 对合并/清除的问题供大型数据库。

A.蒙1997年， 一个有效域的独立算法用于探测大约重复数据库的记录。

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

  • 你可以先排序的所有电子邮件地址通过的第一部分之后@和只有比较的地址是一样的
  • 你可以停止计算之间的距离两个地址的时候，它变得更大的比n

编辑：实际上你可以做得更好O(n^2)，只要看看尼克*约翰逊的答案如下。

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

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

我想这里你的10.000地址非常“固定”，否则你将不得不添加更新机制。

想法是使用Levenshtein距离，但是在'反向'模式下，在Python中：

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

假设您有3个字符串：

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

1＆amp; 1之间的L距离2是2（减去'a'，加'd'）。 2和2之间的L距离3是2（减去'b'，加'e'）。

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

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

所以，我会说Levenshtein是一个不错的选择。

如果你真的在比较电子邮件地址，那么一个明显的方法是将levenshtein算法与域映射相结合。我可以想到，当我使用相同的域名多次注册某些内容时，可以考虑电子邮件地址的用户名部分的变体。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top