Levenshtein距离给出了奇怪的值

Question

Levenshtein距离给出了奇怪的值

6

这里有一个字符串 T：

'men shirt team brienne funny sarcasm shirt features graphic tees mugs babywear much real passion brilliant design detailed illustration strong appreciation things creative br shop thousands designs found across different shirt babywear mugs funny pop culture abstract witty many designs brighten day well day almost anyone else meet ul li quality short sleeve crew neck shirts 100 cotton soft durable comfortable feel fit standard size doubt l xl available li li sustainability label company conceived belief textiles industry start acting lot responsibly made cotton li li clothing printed using state art direct garment equipment crack peel washed li li graphic tee designs professionally printed unique design look great make someone smile funny cute vintage expressive artwork 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 库后运行的另一个示例：

'first succeed way wife told v 2 long sleeve shirt id 1084 first succeed way wife told v 2 long sleeve shirt design printed quality 100 long sleeve cotton shirt sports gray 90 cotton 10 polyester standard long sleeve shirts fashion fit tight fitting style please check size chart listed additional image feel free contact us first sizing questions satisfaction 100 guaranteed shirts usually ship business day ordered noon est next business day ordered noon est long sleeve shirts 100 cotton standard shirt fashion fit combined shipping multiple items'

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 库。

- user9343456

你确定你正确地使用了Levenshtein算法吗？它应该用于长度相似的字符串。如果你想在一大堆文本中寻找“相似”的字符串，我建议你使用一个“窗口”进行搜索，并每次移动一个字符。此外，如果你将该段落与fuzzy中的任何字符串进行比较，这不是搜索操作，而是“多接近”这些字符串之间的操作。 - Iluvatar

我认为你没有遗漏任何东西。这个库似乎有一个微妙的错误。正在尝试确定到底发生了什么。 - Andrew Guy

是的，他说得对，在对齐块之后应该是100。我将使用代码库进行调试，查看它在哪里出错或者函数中是否存在假设。 - the23Effect

2个回答

1

算法的一般思想是在较长的字符串中找到最佳匹配子串。然而，在FuzzyWuzzy中这样做存在一些问题。在下面的算法描述中，s1指较短的字符串，s2指较长的字符串，s2_substr指s2的一个子字符串。他们按照以下步骤实现了该算法：

使用最长公共子序列算法查找s1在s2中的最长公共子串。
使用这些公共子序列的起始索引从s2中提取长度为s1_len的子字符串。当该子串位于s2的末尾时，它可能比s1_len要短。
迭代这些子字符串s2_substr，并使用标准化的InDel-Distance（类似于Levenshtein Distance但不包括替换）与s1进行比较。

我意识到此实现存在以下缺陷。

当使用python-Levenshtein时，FuzzyWuzzy同时使用它来查找最长公共子序列和计算相似度。然而，python-Levenshtein用于查找最长公共子序列的实现已知存在问题（参见这里），我不知道有什么简单的修复方法。有人提出了一个修复方法，但只能修复这个问题，并在不同情况下引入问题。（这是您描述的原始问题）

当未使用python-Levenshtein时，使用difflib计算最长公共子序列。然而，正如这里所述，FuzzyWuzzy没有禁用自动垃圾启发式，这会导致字符串长度差异很大时产生错误结果。我刚刚创建了一个PR来解决这个问题：https://github.com/seatgeek/fuzzywuzzy/pull/303，但该存储库并没有得到积极维护，SeatGeek似乎对许多缺陷感到满意，因为它对他们的用例足够好用。（这是您后来添加的与difflib相关的问题）

相似度比本身存在缺陷。它假设最佳匹配子字符串s2_substr始终从最长公共子序列之一的起始点开始。虽然在许多情况下这是正确的，但并不总是如此。（您没有遇到这个问题，我也没有在FuzzyWuzzy或RapidFuzz中看到有关此问题的错误报告。结果只在一些非常特定的边缘情况下存在很大差异，大多数用户可能不经常遇到）

哪种算法更适合主要取决于您的需求。一个简单的解决方案是使用我的库RapidFuzz替换FuzzyWuzzy。这样可以解决我描述的LCS算法问题。然而，它使用与FuzzyWuzzy相同的算法来计算相似度，因此第三个问题仍然存在。我正在寻找更好的算法（有关更多详细信息，请查看以下问题）。正如Andrew Guy所指出的那样，Smith-Waterman距离也是一种替代方案。但是，它与fuzz.partial_ratio有一些重大区别：

它使用统一的Levenshtein距离（插入/删除/替换都有1的权重），而fuzz.partial_ratio使用InDel距离。如果这对您很重要，实现时可以通过给替换赋予2的权重来适应InDel距离。
fuzz.partial_ratio始终使用长度为s1_len的子字符串，而Smith Waterman算法搜索最佳对齐的子字符串，不关心其长度。这并不是坏事，只是应该意识到这一点。一个缺点是难以将结果归一化（使其成为0到100之间的相似度得分），因为不知道子字符串的长度。这并不是真正的问题，因为您可以搜索最低距离而不是最高相似度。

我没有在RapidFuzz中使用Smith-Waterman算法来计算fuzz.partial_ratio的原因是，我希望它能直接替代FuzzyWuzzy中的实现。但是，我计划在未来添加Smith-Waterman算法。

- maxbachmann

1

非常好的回答，很明显你比我更深入地理解了这个问题的复杂性。我应该指出，我提出Smith-Waterman算法的建议来自于我的生物序列分析背景，这与NLP有些不同。一个重要的点是，它不会将单词边界与其他字符区别对待，因此在NLP环境中使用时可能会产生奇怪的结果。 - Andrew Guy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Andrew Guy · Accepted Answer

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 后，我可以将您的示例简化为：

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 可能是一个合适的替代品。

更新：

我认为这个错误可能与使用python-Levenshtein库中的opcodes有关：

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"中，应该优先考虑连续块，而Levenshtein距离的正式定义并没有给连续块和非连续块优先权（至少我理解的是这样）。请注意，"difflib.SequenceMatcher.get_opcodes()"会产生不同的结果。

我怀疑需要非常仔细地思考才能修复这个bug并且做对。