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

Z时代
2024-01-10
分类：问答

我有一个用例，其中我需要对多个文件中的数百万条记录进行模糊匹配。我为此确定了两种算法：和

编辑距离。

当我开始探索两者时，我无法理解两者之间的确切区别。看起来Levenshtein给出了两个字符串之间的编辑次数，而Jaro-Winkler给出了0.0到1.0之间的匹配分数。我不了解该算法。由于我需要使用任何一种算法，因此我需要知道算法性能方面的确切差异。

回答：

Levenshtein计算将一个字符串转换为另一个字符串所需的编辑（插入，删除或替换）次数。Damerau-

Levenshtein是修改后的版本，也将换位视为单个编辑。尽管输出是编辑的整数，但是可以将其归一化以通过公式给出相似度值

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

Jaro算法是对共同字符的一种度量，考虑到换位，长度不超过较长字符串的长度的一半。Winkler修改了该算法，以支持这样的想法，即字符串开头附近的差异比字符串结尾附近的差异更为重要。Jaro和Jaro-

Winkler适合比较较小的字符串，例如单词和名称。

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

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

人名匹配的比较：技巧和实践问题

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