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

我有一个用例,我需要对来自多个文件的数百万条logging进行模糊匹配。 我确定了两个algorithmJaro-WinklerLevenshtein编辑距离。

当我开始探索这两者时,我无法理解两者之间的确切区别。 Levenshtein似乎给出了两个string之间的编辑数量,Jaro-Winkler给出了0.0到1.0之间的匹配分数。 我不明白这个algorithm。 因为我需要使用任何一种algorithm,所以我需要知道algorithm性能的确切区别。

One Solution collect form web for “Jaro-Winkler和Levenshtein距离之间的区别?”

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。