令牌排序比例如何运作？

Question

有人能解释一下Python中fuzzywuzzy库的这个函数是如何工作的吗？我知道编辑距离是如何工作的，但我不明白比率是如何计算的。

b = fuzz.token_sort_ratio('controlled', 'comparative')

结果是38

Answer 1

编辑距离

您可能已经知道，编辑距离是将一个序列转换为另一序列的最小插入/删除/替换量。它可以归一化为dist / max_dist，其中max_dist是给定两个序列长度的可能的最大距离。在编辑距离的情况下，这会导致归一化dist / max(len(s1), len(s2))。此外，可以通过反转以下内容来计算归一化相似度：1 - normalized distance。

>>> from rapidfuzz.distance import Levenshtein
>>> Levenshtein.distance('controlled', 'comparative')
8
>>> Levenshtein.similarity('controlled', 'comparative')
3
>>> Levenshtein.normalized_distance('controlled', 'comparative')
0.7272727272727273
>>> Levenshtein.normalized_similarity('controlled', 'comparative')
0.2727272727272727

插入缺失距离

Indel距离是将一个序列转换为另一序列的最小插入/删除量。因此它的行为类似于编辑距离，但不允许替换。由于任何替换都可以通过插入+删除来替换，因此这可以通过例如将编辑距离中的替换成本修改为2来计算。Indel距离可以以与编辑距离类似的方式标准化，但使用不同的max_dist：dist / (len(s1) + len(s2))。

>>> from rapidfuzz.distance import Indel
>>> Indel.distance('controlled', 'comparative')
13
>>> Indel.similarity('controlled', 'comparative')
8
>>> Indel.normalized_distance('controlled', 'comparative')
0.6190476190476191
>>> Indel.normalized_similarity('controlled', 'comparative')
0.38095238095238093

比率

in //是归一化ratio的插入缺失相似度缩放至100。fuzzywuzzythefuzzrapidfuzz

>>> from rapidfuzz.distance import Indel
>>> from rapidfuzz import fuzz
>>> Indel.normalized_similarity('controlled', 'comparative') * 100
38.095238095238095
>>> fuzz.ratio('controlled', 'comparative')
38.095238095238095

fuzzywuzzy/中的唯一区别thefuzz是结果四舍五入：

>>> from fuzzywuzzy import fuzz
>>> fuzz.ratio('controlled', 'comparative')
38

令牌排序比率

token_sort_ratio是 的变体ratio，它在比较两个序列之前对它们进行排序：

s1 = " ".join(sorted(s1.split()))
s2 = " ".join(sorted(s2.split()))
fuzz.ratio(s1, s2)

在您的示例中，token_sort_ratio结果将与 相同ratio，因为两个序列都已排序。