Closed. This question needs to be more focused。它当前不接受答案。
想改善这个问题吗？更新问题，使其仅关注editing this post的一个问题。
6年前关闭。
Improve this question
我有一个用例，需要对多个文件中的数百万条记录进行模糊匹配。我为此确定了两种算法: Jaro-Winkler 和 Levenshtein 编辑距离。
当我开始探索两者时，我无法理解两者之间的确切区别。似乎Levenshtein给出了两个字符串之间的编辑次数，而Jaro-Winkler提供了0.0到1.0之间的归一化分数。我不了解该算法。
由于我需要使用任何一种算法，因此我需要知道这两种算法之间的根本区别是什么。
其次，我想了解这两种算法之间的性能差异。
Jaro算法是对共同字符的一种度量，考虑到换位，长度不超过较长字符串的长度的一半。 Winkler修改了该算法，以支持这样的想法，即字符串开头附近的差异比字符串结尾附近的差异更为重要。 Jaro和Jaro-Winkler适用于比较较小的字符串，例如单词和名称。
决定使用哪个不只是性能问题。选择适合您所比较字符串性质的方法很重要。但总的来说，您提到的两种算法都可能很昂贵，因为必须将每个字符串与其他每个字符串进行比较，并且数据集中有数百万个字符串，因此比较的次数很多。这比诸如为每个字符串计算语音编码，然后简单地将共享相同编码的字符串分组那样的东西要昂贵得多。
互联网上有大量有关这些算法和其他模糊字符串匹配算法的详细信息。这将给您一个开始:
A Comparison of Personal NameMatching: Techniques and PracticalIssues
根据该论文，我提到的四种Jaro和Levenshtein算法的速度从最快到最慢:
Jaro Jaro-Winkler Levenshtein Damerau-Levenshtein
最慢的时间是最快的时间的2至3倍。当然，这些时间取决于字符串的长度和实现，并且存在优化这些算法的方法，这些方法可能尚未使用。
想改善这个问题吗？更新问题，使其仅关注editing this post的一个问题。
6年前关闭。
Improve this question
我有一个用例，需要对多个文件中的数百万条记录进行模糊匹配。我为此确定了两种算法: Jaro-Winkler 和 Levenshtein 编辑距离。
当我开始探索两者时，我无法理解两者之间的确切区别。似乎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适用于比较较小的字符串，例如单词和名称。
决定使用哪个不只是性能问题。选择适合您所比较字符串性质的方法很重要。但总的来说，您提到的两种算法都可能很昂贵，因为必须将每个字符串与其他每个字符串进行比较，并且数据集中有数百万个字符串，因此比较的次数很多。这比诸如为每个字符串计算语音编码，然后简单地将共享相同编码的字符串分组那样的东西要昂贵得多。
互联网上有大量有关这些算法和其他模糊字符串匹配算法的详细信息。这将给您一个开始:
A Comparison of Personal NameMatching: Techniques and PracticalIssues
根据该论文，我提到的四种Jaro和Levenshtein算法的速度从最快到最慢:
最慢的时间是最快的时间的2至3倍。当然，这些时间取决于字符串的长度和实现，并且存在优化这些算法的方法，这些方法可能尚未使用。
07-24 18:58