logo标签列表

当样本数量较大时，计算字符串相似度得分的高效方法是什么？

algorithmstringcluster-analysiscomplexity-theoryedit-distance
15
假设你有一份包含10,000个电子邮件地址的列表，并且你想找到在该列表中非常接近的“邻居”——即被定义为在列表中与其他电子邮件地址非常接近的电子邮件地址。
我知道如何计算两个字符串之间的Levenshtein距离（感谢这个问题），它将给出一个得分，表示需要多少操作才能将一个字符串转换成另一个字符串。
假设我将“与另一个电子邮件地址非常接近”定义为两个字符串的Levenshtein得分小于N。
除了将每个可能的字符串与列表中的每个其他可能的字符串进行比较之外，是否有更有效的方法来查找得分低于此阈值的字符串对？换句话说，是否可以比O(n^2)更快地解决这种类型的问题？
Levenshtein得分是解决此问题的不良算法选择吗？
请看下面我的回复，这个问题非常普遍，因为你实际上是在寻找一个拼写更正。 - Matthieu M.
请考虑取消Nick Johnson的回答的“被接受的答案”状态，因为其关于近似搜索O(log n)时间的核心声明是不正确的。 - j_random_hacker
8个回答
7

是的 - 你可以使用BK-Tree在O（log n）时间内找到与给定距离内的所有字符串。对于Levenshtein距离为1的情况，生成每个距离为n的字符串的备选解可能会更快，但对于更长的距离，工作量会迅速膨胀。

查询预构建树的时间复杂度为 O(log n)，但是如果在遍历电子邮件列表时同时构建和查询树，会怎样呢？我认为这对于聚类问题来说并不好。 - Andriy Volkov
1
看起来是一个很好的算法，大部分时间可能都能很好地工作，但从链接页面上并不清楚它是否可以在O(log n)的时间内找到给定L距离内的所有字符串（即与距离d无关）——首先，如果整个字符串集足够接近呢？仅仅输出它们意味着至少需要O(n)的时间 :-P 更深入地说，O(log n)的边界通常适用于树搜索，其中每个级别只访问一个子节点，但似乎搜索BK树可能需要检查许多子节点。在你解释清楚之前，我给你-1分！ - j_random_hacker
1
当你说“文章确实涵盖了编辑距离和搜索树比例之间的关系”时，你是指从你的博客文章链接到的B＆K原始论文吗？因为我无法访问该论文，就像您还链接到的“字典中的快速近似字符串匹配”文章一样，在您链接的博客文章中没有声称，更不用说证明O（log n）行为了。您承认我的BK树的O（n）评估是正确的，但然后责怪我不理解？（而且我不确定快速排序与任何事情有关。） - j_random_hacker
甚至只需清理并澄清复杂性描述（“在平均情况下为O(log n)，与距离无关”），并说这在B＆K论文中已得到证明，如果事实上是如此的话，那就足够了。 - j_random_hacker
1
我已经阅读了这两篇论文。BK73论文证明了仅对于“类0”（精确匹配）查询，查找时间为O(log n)。他们没有尝试分析近似匹配查询，只给出了一些实验结果。B-YN98论文在其附录中给出了分析，显示对于非精确查询，BK树是O(n^a)，其中0 < a < 1是任意一对对象之间预期距离的函数。简而言之，无论是理论还是实证，都没有证据支持你声称BK树可以在O(log n)时间内找到任意距离的最近邻居，所以请删除它。 - j_random_hacker
显示剩余10条评论
6
这个问题被称为聚类，是更大的去重问题的一部分（在这个问题中，你需要决定哪个群集成员是“正确”的），也被称为合并-清除。
我曾经阅读过几篇关于这个主题的研究论文（名称如下），基本上，作者使用了一个有限大小的滑动窗口来遍历已排序的字符串列表。他们只会比较窗口内的N*N个字符串（使用编辑距离算法），从而降低计算复杂度。如果有任何两个字符串看起来相似，它们就会被组合成一个聚类（通过将记录插入到单独的群集表中）。
列表的第一次遍历后，进行第二次遍历，在排序之前将字符串反转。这样，具有不同头部的字符串有另一个机会变得足够接近，以便作为同一窗口的一部分进行评估。在第二次遍历中，如果一个字符串看起来足够接近窗口中的两个（或更多）字符串，并且这些字符串已经是它们自己集群的一部分（由第一次遍历找到），则这两个集群将被合并（通过更新集群表），当前字符串将被添加到新合并的集群中。这种聚类方法称为并查集算法。
然后，他们通过用一组前X个“显著独特的原型”替换窗口来改进算法。每个新字符串都将与前X个原型进行比较。如果字符串看起来足够接近其中一个原型，它将被添加到“原型的聚类”中。如果没有一个原型看起来足够相似，该字符串将成为一个新的原型，并将“推出最老的原型”出前X个列表。 （有一种启发式逻辑用于决定应将原型聚类中的哪些字符串用作代表整个聚类的新原型）。同样，如果字符串与多个原型相似，则将合并所有聚类。我曾经使用此算法实现了姓名/地址记录的去重，列表大小约为1000-5000万条记录，速度非常快（也很好地找到了重复项）。
对于这些问题，最棘手的部分当然是找到合适的相似度阈值。想法是捕获所有的重复项而不产生太多假阳性。具有不同特征的数据往往需要不同的阈值。选择一个编辑距离算法也很重要，因为一些算法更适合OCR错误，而另一些算法更适合拼写错误，还有一些算法更适合语音错误（例如通过电话获取姓名时）。
实现聚类算法后，测试它的好方法是获取唯一样本列表并人工变异每个样本以产生其变化，同时保留所有变化都来自同一父项的事实。然后将此列表随机排序并馈送给算法。将原始聚类与去重算法产生的聚类进行比较，将为您提供效率得分。
参考文献：
Hernandez M. 1995，《大型数据库的合并/清除问题》。
Monge A. 1997，《一种用于检测近似重复数据库记录的高效领域无关算法》。
5
你可以使用Levenshtein算法在O(kl)的时间复杂度内完成操作，其中k是最大距离，l是最长字符串。
基本上，当你知道如何计算基本的Levenshtein距离时，很容易发现，每个距离主对角线超过k的结果都必须大于k。因此，如果你用宽度为2k + 1的主对角线进行计算就足够了。
如果你有10000个电子邮件地址，你不需要更快的算法。计算机可以以O(N^2)的速度快速计算。
Levenshtein算法对于这种问题非常有效。
另外，你可能还要考虑在比较之前使用Soundex转换电子邮件地址。这样可能会得到更好的结果。
你能定义一下“主对角线”是什么意思吗？ - matt b
你有一个用于计算Levenshtein距离的矩阵。它的维度是m*n，因此主对角线将在那里，(i,i)，其中0 <= i < min(m,n)。 - Egon
这样考虑。当给定一个矩阵来计算Levenshtein距离时，向右或向上下移动会进行删除或插入操作，这意味着如果最佳对齐路径来自该路径，则将1添加到距离中。因此，如果您从对角线超过k次移开，则距离不会比k更好。 - Egon
你也可以使用自动机来加速比较。构建一个能够识别最大距离为k的单词的自动机需要O(nk)的时间，但检查单词是否匹配只需要O(n)的时间。因此，如果你有N封电子邮件，获取所有自动机将需要O(Nnk)的时间。然后检查每个电子邮件将需要O(NNn)的时间。 - Egon
谢谢，这很有帮助。如果我理解正确的话，这意味着对于阈值=3，我不应该计算任何得分，对于那些长度与被测试字符串相差+/-3的字符串 - 这将是一个不错的优化。 - matt b
1
看那张图片。使用阈值3，您就不需要计算红色部分了。 - Egon
2

我认为你无法做到比O(n^2)更好，但是你可以进行一些较小的优化，这些优化可能足以加速你的应用程序，使其可用：

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

编辑：实际上，您可以做得比O(n^2)更好，只需查看下面Nick Johnsons的答案即可。

2
你可以做得比O(n^2)更好 - 参考我的答案。 :) - Nick Johnson
1

如果反转问题，就有可能做得更好。

我假设你的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 方法从先前的集合中生成所有可能的变体，减去已经存在于前一个级别的变体。 它将“原点”保留为与键关联的值。

然后，您只需要在不同的集合中查找您的单词：

  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
这听起来是一个相当不错的方法，只是我预计我的数据集每天都会发生变化；所以我很好奇每次都需要重新生成所有的变体是否会损失一些效率。不过还是谢谢你的建议，Norvig的链接我一直很喜欢！ - matt b
生成可以通过离线过程完成，然后进行序列化并按需加载。 - Matthieu M.
这对于大型列表（数千万条记录）不起作用。为此，请参见我的答案。 - Andriy Volkov
实际上会的。Norvig 给它喂了一个 6.2Mo 的单词文件来 '训练' 它的算法。但我觉得我们在谈论不同的问题 > 我假设'正确'答案集事先已知，而你只是尝试将各种地址 '分组' 在一起。 - Matthieu M.
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（替换每个字符），由于前两个计算的分数不揭示删除、插入或替换操作，因此无法推断出这一点。

因此，我认为Levenshtein对于大型列表来说是一个糟糕的选择。

2
是的，但根据度量的性质，您至少可以假设距离为2+2或更少。如果您有一个字符串列表，其中有趣的距离远小于字符串的长度，则这可能是有价值的信息。 - jprete
1

1万个电子邮件地址听起来不算太多。如果要在更大的空间中进行相似性搜索，您可以使用shingling和min-hashing。这个算法实现起来有点复杂，但在大空间中效率更高。

1
我随意挑选了一万这个数字，希望听起来“很大”，实际的问题空间要大几倍（但不是数百万级别）。 - matt b
@Yuval，你提到的两种方法都是用于比较两个大型文档，而这个问题是关于聚类大量小字符串的。完全不同的问题。 - Andriy Volkov
@zvolkov - 我听了一场关于这些方法的讲座。它们是否适用于小型文档尚有争议。毫无疑问，它们是用来在非常大的集合中寻找相似文档的。 - Yuval F
@zvolkov：“Shingling”（我知道它作为n-grams/k-tuples）是一种寻找可能具有低L距离的字符串组的好方法。1）将每个地址拆分成n-gram。2）构建一个由n-gram索引的数组（如果n=4且允许的字符为A-Z，则它将具有例如26^4个条目），其中每个条目包含包含该n-gram的所有地址的列表（地址由整数标识）。3）对于每个这样的列表，例如长度为k，请写出k *（k-1）/ 2个整数对——每个整数对共享该n-gram。4）对此对列表进行排序。5）在重复运行中相同对的数量≈相似度。 - j_random_hacker
@j_random_hacker 我明白了。所以shingling确实可以用于聚类，但是不会很高效。 - Andriy Volkov
@zvolkov：你确定吗？:-P 这是许多生物信息学程序查找匹配的DNA序列的方法。它甚至可以扩展到不适合内存的数据集，因为每个步骤（甚至“构建数组”）都可以使用排序完成，并且有相当有效的外部排序算法。诀窍是尽可能使n变大，以便每个数组元素中的列表很小。（但是n太大意味着会错过一些相似之处。） - j_random_hacker
1

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接