Jaro-Winkler距离和Levenshtein距离的区别是什么？

Question

111

我希望对来自多个文件的数百万条记录进行模糊匹配，我确定了两种算法：Jaro-Winkler 和 Levenshtein 编辑距离。

我无法理解这两者之间的区别。似乎 Levenshtein 给出了两个字符串之间的编辑次数，而 Jaro-Winkler 提供了一个介于 0.0 到 1.0 之间的归一化分数。

我的问题：

- Bhavesh Shah

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hatchet - done with SOverflow · Accepted Answer

Levenshtein算法计算将一个字符串转换为另一个字符串所需的编辑次数（包括插入、删除或替换）。Damerau-Levenshtein是其修改版，它将转置操作视为单个编辑操作。尽管输出结果是整数编辑次数，但可以通过以下公式进行归一化处理，得到相似度值：

1 - (edit distance / length of the larger of the two strings)

Jaro算法是一种衡量共同字符数量的测量方法，距离不超过较长字符串长度的一半，并考虑到位置错位。Winkler修改了这个算法以支持这样一个想法：与字符串开头附近的差异相比，字符串结尾附近的差异更不重要。Jaro和Jaro-Winkler适用于比较单词和姓名等较短的字符串。

决定使用哪个算法不仅仅是性能问题。选择适合你要比较的字符串性质的方法很重要。总的来说，你提到的这两个算法都可能很昂贵，因为每个字符串都必须与其他每个字符串进行比较，在数据集中有数百万个字符串时，这是一个惊人的比较数量。这比计算每个字符串的语音编码并简单地分组共享相同编码的字符串要昂贵得多。

在互联网上有大量关于这些算法和其他模糊字符串匹配算法的详细信息。这篇文章将为您提供一个起点：

根据那篇论文，我提到的四个Jaro和Levenshtein算法的速度从最快到最慢分别是：

最慢的比最快的花费的时间要多2到3倍。当然，这些时间取决于字符串的长度和实现方式，并且有一些优化这些算法的方法可能没有被使用。