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

准备了解 `junk`！

生成操作码的主要算法来自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)

difflib 无法正确找到操作码

difflib cannot correctly find the opcodes

python

difflib

准备了解 junk！

处理垃圾

准备了解 `junk`！