performance - Jaro-Winkler 和 Levenshtein 距离之间的区别？

Question

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

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

我的问题：

1. 两种算法的根本区别是什么？

2. 两种算法之间的性能差异是什么？

Answer 1

Levenshtein 计算将一个字符串转换为另一个字符串所需的编辑次数（插入、删除或替换）。Damerau-Levenshtein 是一个修改版本，它也将转置视为单一编辑。虽然输出是整数编辑数，但可以通过公式对其进行归一化以给出相似度值

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

Jaro 算法是对共同字符的度量，在距离上不超过较长字符串长度的一半，并考虑了换位。Winkler 修改了该算法以支持字符串开头附近的差异比字符串结尾附近的差异更显着的想法。Jaro 和 Jaro-Winkler 适合比较较小的字符串，如单词和名称。

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

互联网上有大量关于这些算法和其他模糊字符串匹配算法的详细信息。这会给你一个开始：

人名匹配比较：技术与实际问题

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

• 哈罗
• 雅罗-温克勒
• 文史丹
• Damerau-Levenshtein

最慢的时间是最快的时间的 2 到 3 倍。当然，这些时间取决于字符串的长度和实现，并且有一些方法可以优化这些可能尚未使用的算法。