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这里输出的方法是正确的。

\n\n

不过，你有理由想知道为什么difflib选择这种奇怪的转变而不是那个转变是正确的：

\n\n

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

\n\n

归结为一件事：autojunk=True

\n\n

准备了解一下junk！

\n\n

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

\n\n

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

\n\n

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

\n\n

来自difflib文档：

\n\n

\n

自动垃圾启发式：[...] 如果一个项目\xe2\x80\x99s 重复项（在第一个之后）占序列的 1% 以上，并且序列\n 至少有 200 个项目长，则该项目被标记为 \xe2\x80\x9cpopular\xe2\x80\x9d 并出于序列匹配的目的而被视为垃圾。[...]

\n

\n\n

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

\n\n

处理垃圾

\n\n

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

\n\n

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

\n\n

这会输出您期望的内容：

\n\n

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

\n\n

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

\n\n

\n

[...]这些 \xe2\x80\x9cjunk\xe2\x80\x9d 元素在某种意义上是无趣的，例如空行或空格 [...]

\n

\n\n

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

\n\n

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

\n\n

import difflib\nfrom string import whitespace\n\n...\n\ndifflib.SequenceMatcher(lambda x: x in whitespace, str1, str2, autojunk=False)\n

\n