python - 使用 fuzzywuzzy 的字符串匹配 - 它是使用 Levenshtein 距离还是 Ratcliff/Obershelp 模式匹配算法？

Question

fuzzywuzzy是一个非常流行的字符串匹配库。根据 documentation库的一部分，提到它使用 Levenshtein 距离来计算序列之间的差异。但关闭后inspection ，我发现它实际上使用了 difflib 库中的 SequenceMatcher 函数。而这个功能，根据documentation使用 Ratcliff/Obershelp 模式匹配算法。

根据定义，Levenshtein distance是将一个字符串转换为另一个字符串所需的最少编辑次数，Ratcliff/Obershelp pattern-matching algorithm计算匹配字符数的两倍除以两个字符串中的字符总数。密切相关post比较两者。

当我运行一个示例时，我在 Fuzzywuzzy 中得到了 SequenceMatcher 和比率函数的相同结果。

from difflib import SequenceMatcher
from fuzzywuzzy import fuzz
s = SequenceMatcher(None, "abcd", "bcde")
s.ratio()
# 0.75
fuzz.ratio("abcd", "bcde")
# 75

如果我手动计算两个字符串之间的 Levenshtein 距离，我猜它只会是 2。在这种情况下，它如何变成贡献者在文档中写的使用 Levenshtein 距离？

Answer 1

FuzzyWuzzy.ratio using python-Levenshtein不返回 Levenshtein 分数，而是返回 Levenshtein 比率，即 (a+b - LevenshteinScore)/(a+b)，其中 a 和 b 是要比较的两个字符串的长度。

如果您没有安装 python-Levenshtein，那么 fuzzywuzzy 根本不会使用 Levenshtein。 Fuzzywuzzy 的主页在这方面具有误导性，尽管它确实建议安装 python-Levenshtein。

python-Levenshtein 在安装时有一些问题；我使用了对 this stackoverflow 的第二个回复问题来解决它。

如果你没有安装 python-Levenshtein，FuzzyWuzzy 使用 difflib相反，这对于许多输入值都是相同的，但不是全部。开发人员推荐使用 python-Levenshtein。参见 this issue on fuzzywuzzy's git ，其中包括一个示例，其中使用包的结果与没有包的结果不同。这可能不应该发生，或者至少文档应该清楚地说明这一点，但 FuzzyWuzzy 的开发人员似乎至少对功能感到满意。