Levenshtein 距离给出奇怪的值

Question

这是一个字符串T：

'男士衬衫团队 brienne 有趣的讽刺衬衫具有图形 T 恤杯子 婴儿装 真正的激情 辉煌的设计 详细的插图 强烈的欣赏 东西 创意 br 商店 在不同的衬衫上发现了数千种设计 婴儿装杯子 有趣的流行文化 抽象 诙谐 很多设计使一天好起来 几乎所有其他人都会遇到 ul li 质量短袖圆领衬衫 100 棉柔软耐用舒适手感合身标准尺寸怀疑 l xl 可用 li li 可持续性标签公司构想的信念纺织品行业开始采取行动，负责任地制造棉 li li 服装使用 state art 直接服装设备印刷裂纹剥离水洗 li li图形 T 恤设计专业印刷独特的设计看起来很棒让人微笑有趣可爱的复古富有表现力的艺术品 li ul'

我已经突出显示了上面字符串的一部分，因为上面是字符串的预处理版本，因此可能难以阅读。

我得到以下值：

fuzz.partial_ratio('short sleeve', T) 给 50

fuzz.partial_ratio('long sleeve', T) 给 73

fuzz.partial_ratio('dsfsdf sleeve', T) 给 62

fuzz.partial_ratio('sleeve', T) 给 50

我对此感到非常困惑。第一个和第四个值不应该是 100 吗？当然我错过了一些东西，但我无法弄清楚。

编辑：这是我在卸载 python-Levenshtein 库后运行的另一个示例：

'第一个成功方式妻子告诉 v 2 长袖衬衫 id 1084 第一个成功方式妻子告诉 v 2 长袖衬衫设计印刷质量 100 长袖棉衬衫运动灰色 90 棉 10 涤纶标准长袖衬衫时尚合身紧身款式请查看尺码表列出的附加图片随时与我们联系 第一尺寸问题 满意度 100 件保证衬衫通常在工作日中午 est 下订单 下一个工作日中午 est 长袖衬衫 100 件棉质标准衬衫 时尚合身 合并运输多个项目

fuzz.partial_ratio('long sleeve', T) 给出 27

fuzz.partial_ratio('short sleeve', T) 给 33

fuzz.partial_ratio('sleeveless', T) 给 40

fuzz.partial_ratio('dsfasd sleeve', T) 给 23

不幸的是，这个问题似乎不是 python-Levenshtein 库独有的。

Answer 1

图书馆的某个地方有一个非常奇怪和微妙的错误fuzzywuzzy。

如果我们运行以下命令

from fuzzywuzzy import fuzz

fuzz.partial_ratio('funny', 'aa aaaaa aaaa aaaaaaa funny aaaaaaa aaaaaaaa aaaaaaa aaaa aaaa aaayaaaa auaa aaaa aaaaaaaa aaaaaaaaa aaaaaa aaaaaaaa aaaaa aaaa aa aaaaaaaaaaa aaaaaa aaaffaaaaaaa aaaaa aaayaaaa auaa funny aaaa aaaaaa')

它返回0

而如果我们从该字符串的开头删除一个字母：

fuzz.partial_ratio('funny', 'a aaaaa aaaa aaaaaaa funny aaaaaaa aaaaaaaa aaaaaaa aaaa aaaa aaayaaaa auaa aaaa aaaaaaaa aaaaaaaaa aaaaaa aaaaaaaa aaaaa aaaa aa aaaaaaaaaaa aaaaaa aaaffaaaaaaa aaaaa aaayaaaa auaa funny aaaa aaaaaa')

它返回100

（很抱歉又长又可怕的字符串。我试图将其减少为尽可能简单的字符串，但我似乎看不到驱动此错误的逻辑）

Github 上似乎也有类似的 bug 报告。

安装python-Levenshtein似乎修复了我上面的示例（fuzzywuzzy 恢复为difflib如果python-Levenshtein未安装），但不会更改您的原始示例。

安装后python-Levenshtein，我可以将您的示例简化为：

fuzz.partial_ratio('sleeve', 's l e e v sleeve e ')

哪个返回50。

从较长的字符串中删除第一个字母：

fuzz.partial_ratio('sleeve', 'l e e v sleeve e ')

返回100。

这提供了有关可能发生的情况的某种提示，但我怀疑需要深入研究才能python-Levenshtein弄清楚。

我的推荐？提交错误报告。然后找到另一个库来比较字符串。RapidFuzz可能是一个合适的替代方案。

更新：

我认为该错误可能与使用opcodesfrompython-Levenshtein库有关：

from Levenshtein import opcodes

opcodes('sleeve', 's l e e v sleeve e ')

返回：

[('equal', 0, 1, 0, 1),
 ('insert', 1, 1, 1, 2),
 ('equal', 1, 2, 2, 3),
 ('insert', 2, 2, 3, 4),
 ('equal', 2, 3, 4, 5),
 ('insert', 3, 3, 5, 6),
 ('equal', 3, 4, 6, 7),
 ('insert', 4, 4, 7, 8),
 ('equal', 4, 5, 8, 9),
 ('insert', 5, 5, 9, 12),
 ('equal', 5, 6, 12, 13),
 ('insert', 6, 6, 13, 19)]

当在 中使用时fuzzywuzzy，这显然不是预期的结果，即使这些是一组最小编辑操作。在 中fuzzywuzzy，优先级应该放在连续块上，而编辑距离的正式定义并没有优先考虑连续块与非连续块（至少在我看来不是）。请注意，这difflib.SequenceMatcher.get_opcodes()给出了不同的结果。

我怀疑需要非常仔细的思考来修复这个错误并使其正确。