比方说，你有10000个电子邮件地址的列表，而且你想查找一些在此列表中最接近的“邻居”的是 - 定义是，可疑接近其他电子邮件地址在列表中的电子邮件地址。
我知道如何计算Levenshtein距离两个字符串（感谢之间的这个问题 ），这会给我的得分需要多少操作，将一个字符串转换为另一种。
比方说，我定义“可疑接近另一电子邮件地址”为具有莱文斯坦两串得分小于N
有没有找到对字符串，其得分比除每一个可能比较字符串列表中的所有其他可能的字符串此阈值低的更有效的方法？ 换言之，可以在此类型的问题比来解决更快O(n^2)
是莱文斯坦得分的算法选择不当这个问题？
是的-你可以找到一个字符串在O定距离内的所有字符串使用（log n）的时间BK-树 。 涉及生成每个字符串与距离n替代解决方案可以是用于1:1的Levenshtein距离更快，但功的量迅速气球出较长距离的控制。
您可以在莱文斯坦做O(kl)其中k是你的最大距离，l是最大字符串。
基本上，当你知道如何计算基本莱文斯坦则很容易弄清楚，每个结果比进一步k从主对角线上必须比大k 。 所以，如果你计算主对角线宽度为2k + 1就足够了。
如果你有10000个电子邮件地址，您将不再需要一个更快的算法。 计算机可以计算出O(N^2)速度不够快。
莱文斯坦是这种问题相当不错。
另外你可能会考虑是比较之前，把用同音电子邮件。 你可能会得到更好的结果。
这个问题被称为集群 ，是一个更大的问题， 重复数据删除 （如果你决定哪些成员集群是“正确的”一节），也被称为合并吹扫的一部分。
我曾经看过一些研究论文的正是这个话题（名称如下），基本上，作者使用有限的尺寸滑动窗口在字符串的排序列表。 他们只会比较（使用编辑距离算法）N * N串的窗口内 ，从而降低计算复杂度。 如果任何两个字符串看上去类似，将它们组合成群集 （通过插入记录到一个单独的集群表）。
第一次通过列表随后在丝线得到整理之前扭转 了第二遍 。 这种方式与不同的头弦再有一次机会得到足够接近为同一窗口的一部分进行评估。 在第二遍，如果一个字符串看上去足够接近两个（或更多）的字符串的窗口，这些字符串已经自己簇的部分（第一通过找到），两个集群将被合并 （通过更新群集表）以及当前字符串将被添加到新合并的集群。 这种聚类方法就是所谓的合并-查找算法。
然后，他们通过与顶部X 实质上唯一的原型的列表更换窗口改进的算法。 每一个新的字符串将作为比较对象顶的X原型。 如果字符串看起来足够接近的原型之一，这将被添加到该原型的集群 。 如果没有原型看起来很相似，该字符串将成为一个新的原型， 推动历史最悠久的原型出前X名单。 （有用来决定哪个原型的集群中的串的应作为代表整个集群的新原型的启发式算法逻辑）。 同样，如果字符串看起来类似于几个原型，所有的集群将被合并。
有一次，我实现了这个算法与列表被周围10-50万条记录尺寸的名称/地址记录重复数据删除和它的工作非常该死的快（发现重复的也很好）。
总体来说这样的问题，当然最棘手的部分是找到相似性阈值的权值。 这样做是为了捕获所有的DUP W / O产生太多的误报 。 具有不同特性的数据往往需要不同的阈值。 编辑距离算法的选择也很重要，因为有些算法是错误的OCR更好，而另一些错别字更好的，还有一些是拼音错误更好的（例如通过电话得到一个名称时）。
一旦聚类算法实现，测试它的好办法是让独特样本名单和人为变异每个样品产生及其变化，同时保持一个事实，即所有的变化都来自相同的父。 然后这个列表洗牌，送入算法。 通过重复数据删除算法产生的聚类原集群比较会给你的得分效率 。
埃尔南德斯M. 1995年，合并/清除问题的大型数据库。
蒙赫A. 1997年， 一种高效领域无关的检测算法大约有重复记录。
我不认为你可以为O做的更好（N ^ 2），但你可以做一些小的优化，这可能是一个加速的只是为了让您的应用程序可用：
编辑：其实您可以用比为O（n ^ 2）做的更好，只是看看尼克约翰逊回答以下。
万个电子邮件地址听起来不太多。 为了在更大的空间相似性搜索可以使用的压挤和最小散列 。 这种算法比较复杂一点实现，但多是在一个大空间更有效率。
这是可能做的更好，在扭转问题的条件。
我想，在这里，你的10000个地址是相当“固定”的，否则，你将需要添加的更新机制。
我们的想法是使用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
比方说，你有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为3的距离L（取代的每个字符），也没有办法，这可能是因为第一2所计算的分数来推断。 分数不透露是否缺失，进行插入或替换操作。
所以，我会说，莱文斯坦是一个大名单一个糟糕的选择。
如果你真的是比较电子邮件地址，然后一个明显的方法来做到这将是一个Levenshtein算法与域映射结合起来。 当我上的电子邮件地址的用户名部分签署了一些使用相同的域多次，但变化我能想到的时间。
