mat*_*t b 15 string algorithm complexity-theory edit-distance cluster-analysis
假设您有一个包含10,000个电子邮件地址的列表,并且您希望找到此列表中一些最接近的"邻居" - 定义为与列表中其他电子邮件地址可疑接近的电子邮件地址.
我知道如何计算两个字符串之间的Levenshtein距离(由于这个问题),这将给我一个将一个字符串转换成另一个字符串需要多少操作的分数.
假设我将"可疑地接近另一个电子邮件地址"定义为Levenshtein得分小于N的两个字符串.
除了将每个可能的字符串与列表中的每个其他可能的字符串进行比较之外,是否有更有效的方法来查找分数低于此阈值的字符串对？换句话说,这种类型的问题可以更快地解决O(n^2)吗？
Levenshtein对这个问题的算法选择是不是很差？
您可以使用中的Levenshtein进行操作O(kl)，其中k最大距离是l，最大字符串是l。
基本上，当您知道如何计算基本Levenshtein时，就很容易弄清楚，每个比k主对角线都远的结果都必须大于k。因此，如果您用宽度计算主对角线2k + 1就足够了。
如果您有10000个电子邮件地址，则不需要更快的算法。计算机可以O(N^2)足够快地进行计算。
Levenshtein对于这种问题非常有用。
另外，您可能会考虑在比较之前使用soundex转换电子邮件。您可能会得到更好的结果。
此问题称为群集，是更大的重复数据删除问题的一部分（在该问题中，您可以确定群集的哪个成员是“正确的”成员），也称为merge-purge。
我曾经读过几篇关于这个主题的研究论文（名称在下面），基本上，作者在排序的字符串列表上使用了一个有限大小的滑动窗口。他们只比较（使用编辑距离算法）窗口内的N * N个字符串，从而降低了计算复杂度。如果任何两个字符串看起来相似，则将它们组合到一个群集中（通过将记录插入到单独的群集表中）。
第一次通过列表，然后第二次通过，在排序之前将字符串反转。这样，具有不同头部的字符串又有机会接近到足以被评估为同一窗口的一部分。在第二遍中，如果一个字符串看起来足够接近窗口中的两个（或更多）字符串，并且这些字符串已经是它们自己的群集的一部分（在第一遍中找到），则这两个群集将被合并（通过更新群集表）和当前字符串将添加到新合并的群集中。这种聚类方法称为联合查找算法。
然后他们通过用顶部的X个基本独特的原型替换窗口改进了算法。每个新字符串将与每个顶级X原型进行比较。如果字符串看起来足够接近原型之一，则将其添加到原型的簇中。如果没有一个原型看起来足够相似，则字符串将成为新的原型，从而将最旧的原型从 X列表中排除。（采用了一种启发式逻辑来决定应使用原型集群中的哪些字符串作为代表整个集群的新原型）。同样，如果字符串看起来类似于几个原型，则它们的所有簇将被合并。
我曾经实现过这种用于名称/地址记录的重复数据删除的算法，列表的大小大约为10到5000万条记录，并且它的工作速度非常快（而且发现重复的很好）。
总体而言，对于此类问题，最棘手的部分当然是找到相似度阈值的正确值。这个想法是要捕获所有不会产生太多误报的假面。具有不同特征的数据往往需要不同的阈值。编辑距离算法的选择也很重要，因为某些算法更适合OCR错误，而其他算法更适合错别字，而另一些算法更适合语音错误（例如通过电话获取姓名时）。
一旦实施了聚类算法，进行测试的一种好方法就是获取唯一样本的列表，并人为地突变每个样本以产生其变异，同时保留所有变异均来自同一父代的事实。然后，此列表被重新整理，并馈送到算法中。将原始聚类与重复数据删除算法产生的聚类进行比较，将获得效率得分。
Hernandez M. 1995，大型数据库的合并/清除问题。
Monge A. 1997，一种有效的与域无关的算法，用于检测近似重复的数据库记录。