python - difflib 无法正确找到操作码

Question

我在 python 的 difflib 库中遇到了一个非常奇怪的问题。我有两个字符串，如下所示，我对它们运行 get_opcodes ，如下所示:

import difflib

str1 = "MatrixElement(MatrixSymbol('Btd', Integer(11), Integer(11)), Integer(0), Integer(9))), Mul(Float('1.0', precision=24), MatrixElement(MatrixSymbol('Btd', Integer(11), Integer(11)), Integer(0), Integer(10))))"
str2 = "MatrixElement(MatrixSymbol('Btd', Integer(11), Integer(11)), Integer(1), Integer(9))), Mul(Float('1.0', precision=24), MatrixElement(MatrixSymbol('Btd', Integer(11), Integer(11)), Integer(1), Integer(10))))"
difflib.SequenceMatcher(None, str1,str2).get_opcodes()

仅在这个具体示例中，diff 的输出如下所示，这显然是错误的。

[('equal', 0, 69, 0, 69),
 ('replace', 69, 70, 69, 70),
 ('equal', 70, 188, 70, 188),
 ('insert', 188, 188, 188, 201),
 ('equal', 188, 190, 201, 203),
 ('replace', 190, 206, 203, 206)]

正确的输出不应包含insert操作码，因为没有添加任何新内容。

这是否是 difflib 中潜在的错误？

Answer 1

这不是一个错误。有多种方法可以将一个序列转换为另一个序列，这里的 difflib 输出是正确的。

不过，您想知道为什么 difflib 选择那个奇怪的转换而不是那个转换是正确的:

[('equal', 0, 69, 0, 69),
 ('replace', 69, 70, 69, 70),
 ('equal', 70, 188, 70, 188),
 ('replace', 188, 189, 188, 189),
 ('equal', 189, 206, 189, 206)]

归结为一件事:autojunk=True

准备好了解垃圾!

生成操作码的主要算法来自 SequenceMatcher.get_matching_blocks ，此方法将提供的序列分解为匹配的子序列。

为了有效地做到这一点，它首先解析 str2 并构建一个 dict，其中键是序列中的字符，值是相应字符的索引列表。

尽管如此，这可能非常消耗内存，因此，默认情况下，difflib.SequenceMatcher 会将一些重复出现的字符视为垃圾，并且不存储其索引。

来自difflib doc :

Automatic junk heuristic: [...] If an item’s duplicates (after the first one) account for more than 1% of the sequence and the sequence is at least 200 items long, this item is marked as “popular” and is treated as junk for the purpose of sequence matching. [...]

在您的具体情况下，罪魁祸首是字符 ( ，它被视为垃圾。SequenceMatcher 对象无法看到从索引 189 开始的匹配序列，因为它是一个 (.

处理垃圾

获得预期输出的最简单方法是设置 autojunk=False。

difflib.SequenceMatcher(None, str1, str2, autojunk=False).get_opcodes()

这将输出您期望的内容:

[('equal', 0, 69, 0, 69),
 ('replace', 69, 70, 69, 70),
 ('equal', 70, 188, 70, 188),
 ('replace', 188, 189, 188, 189),
 ('equal', 189, 206, 189, 206)]

不过，请注意，有时完全关闭 autojunk 可能不是最佳选择，因为它可能会消耗更多内存和时间。更好的方法是指定什么被视为垃圾。

[...] these “junk” elements are ones that are uninteresting in some sense, such as blank lines or whitespace [...]

当您使用 difflib.ratio 时尤其如此。以获得序列之间相似性的度量。在这种情况下，您可能想要忽略空格，因为它们在文本比较方面通常没有意义。

因此，如果您关闭 autojunk，您仍然可以提供 isjunk 函数来指示忽略空格等内容。此参数是您在示例中设置为 None 的参数。

import difflib
from string import whitespace

...

difflib.SequenceMatcher(lambda x: x in whitespace, str1, str2, autojunk=False)