Jaro-Winkler和Levenshtein距离之间的区别？
我有一个用例，我需要对来自多个文件的数百万条logging进行模糊匹配。 我确定了两个algorithm： Jaro-Winkler和Levenshtein编辑距离。
当我开始探索这两者时，我无法理解两者之间的确切区别。 Levenshtein似乎给出了两个string之间的编辑数量，Jaro-Winkler给出了0.0到1.0之间的匹配分数。 我不明白这个algorithm。 因为我需要使用任何一种algorithm，所以我需要知道algorithm性能的确切区别。
Levenshtein计算将一个string转换为另一个string所需的编辑（插入，删除或replace）次数。 Damerau-Levenshtein是一个修改后的版本，也将转换视为单个编辑。 尽pipe输出是整数编辑，但可以通过公式将其归一化以给出相似值
1 - (edit distance / length of the larger of the two strings) Jaroalgorithm是一个共同的字符的度量，不超过距离较长的string长度的一半，考虑到转置。 Winkler修改了这个algorithm，以支持这样一个思想，即在string开头附近的差异比在string末尾附近的差异更重要。 Jaro和Jaro-Winkler适合比较较小的string，如单词和名字。
决定使用哪一个不只是performance的问题。 select一个适合您所比较的string的性质的方法非常重要。 一般来说，你提到的两种algorithm都可能是昂贵的，因为每个string都必须与其他string进行比较，并且在数据集中有数百万个string，这是大量的比较。 这比为每个string计算语音编码之类的东西要昂贵得多，然后简单地将共享相同编码的string分组。
这些algorithm和互联网上的其他模糊string匹配algorithm有大量的详细信息。 这一个会给你一个开始：
个人名字匹配比较：技巧与实践问题
根据那篇论文，我提到的四个Jaro和Levenshteinalgorithm的速度是从最快到最慢：
- 哈罗
- 哈罗，温克勒
- 莱文斯坦
- Damerau – 莱文斯坦
最慢的是最快的2到3倍。 当然，这些时间取决于string的长度和实现，还有一些方法可以优化这些可能没有被使用的algorithm。
