7.4. 差异库 — 计算增量的助手

2.1 版中的新功能。

该模块提供用于比较序列的类和函数。例如，它可以用于比较文件，并且可以生成各种格式的差异信息，包括 HTML 和上下文以及统一差异。要比较目录和文件，另请参阅 filecmp 模块。

class difflib.SequenceMatcher

这是一个灵活的类，用于比较任何类型的序列对，只要序列元素是 hashable。基本算法早于 Ratcliff 和 Obershelp 在 1980 年代后期以双曲线名称“格式塔模式匹配”发布的算法，并且比它更高级一些。这个想法是找到不包含“垃圾”元素的最长连续匹配子序列（Ratcliff 和 Obershelp 算法不处理垃圾）。然后将相同的想法递归地应用于匹配子序列左侧和右侧的序列片段。这不会产生最少的编辑序列，但确实会产生对人们来说“看起来正确”的匹配。

Timing: 基本的 Ratcliff-Obershelp 算法在最坏情况下是三次时间，在预期情况下是二次时间。 SequenceMatcher 是最坏情况的二次方时间，其预期情况行为以复杂的方式取决于序列共有多少个元素；最佳情况时间是线性的。

自动垃圾启发式： SequenceMatcher supports a heuristic that automatically treats certain sequence items as junk. The heuristic counts how many times each individual item appears in the sequence. 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. This heuristic can be turned off by setting the autojunk argument to False when creating the SequenceMatcher.

2.7.1 新功能： autojunk 参数。

class difflib.Differ

这是一个用于比较文本行序列并产生人类可读差异或增量的类。 Differ 使用 SequenceMatcher 来比较行序列，以及比较相似（接近匹配）行内的字符序列。

Differ delta 的每一行都以两个字母的代码开头：

代码	意义
`'- '`	序列 1 独有的行
`'+ '`	序列 2 独有的行
`' '`	两个序列共有的行
`'? '`	任一输入序列中都不存在行

以“?”开头的行试图将眼睛引导到行内差异，并且在任一输入序列中都不存在。如果序列包含制表符，这些行可能会令人困惑。

class difflib.HtmlDiff

此类可用于创建 HTML 表格（或包含该表格的完整 HTML 文件），显示文本与行间和行内更改突出显示的并排、逐行比较。该表可以以完整或上下文差异模式生成。

这个类的构造函数是：

__init__(tabsize=8, wrapcolumn=None, linejunk=None, charjunk=IS_CHARACTER_JUNK)

初始化 HtmlDiff 的实例。

tabsize 是一个可选的关键字参数，用于指定制表位间距，默认为 8。

wrapcolumn 是一个可选关键字，用于指定断行和换行的列号，默认为 None 行不换行。

linejunk 和 charjunk 是传递给 ndiff() 的可选关键字参数（由 HtmlDiff 用于生成并排的 HTML 差异）。有关参数默认值和说明，请参阅 ndiff() 文档。

以下方法是公开的：

make_file(fromlines, tolines [, fromdesc][, todesc][, context][, numlines])

比较 fromlines 和 tolines（字符串列表）并返回一个字符串，它是一个完整的 HTML 文件，其中包含一个表格，其中显示了逐行差异并突出显示了行间和行内更改。

fromdesc 和 todesc 是可选的关键字参数，用于指定从/到文件列标题字符串（均默认为空字符串）。

context 和 numlines 都是可选的关键字参数。当要显示上下文差异时，将 context 设置为 True，否则默认为 False 以显示完整文件。 numlines 默认为 5。当 context 为 True numlines 控制围绕差异高光的上下文行数。当 context 为 False numlines 控制使用“next”超链接时在差异突出显示之前显示的行数（设置为零会导致“next” ”超链接将下一个差异突出显示放在浏览器顶部，没有任何前导上下文）。

make_table(fromlines, tolines [, fromdesc][, todesc][, context][, numlines])

比较 fromlines 和 tolines（字符串列表）并返回一个字符串，它是一个完整的 HTML 表格，显示逐行差异，突出显示行间和行内更改。

此方法的参数与 make_file() 方法的参数相同。

Tools/scripts/diff.py 是此类的命令行前端，并包含一个很好的使用示例。

2.4 版中的新功能。

difflib.context_diff(a, b[, fromfile][, tofile][, fromfiledate][, tofiledate][, n][, lineterm])

比较 a 和 b（字符串列表）；以上下文差异格式返回增量（generator 生成增量线）。

上下文差异是一种紧凑的方式，仅显示已更改的行加上几行上下文。更改以之前/之后的样式显示。上下文行的数量由 n 设置，默认为 3。

默认情况下，差异控制行（带有 *** 或 --- 的那些）使用尾随换行符创建。这很有用，因此从 file.readlines() 创建的输入会产生适合与 file.writelines() 一起使用的差异，因为输入和输出都有尾随换行符。

对于没有尾随换行符的输入，将 lineterm 参数设置为 "" 以便输出将统一无换行符。

上下文差异格式通常有一个文件名和修改时间的标题。可以使用 fromfile、tofile、fromfiledate 和 tofiledate 的字符串指定其中的任何一个或全部。修改时间通常以 ISO 8601 格式表示。如果未指定，则字符串默认为空白。

>>> s1 = ['bacon\n', 'eggs\n', 'ham\n', 'guido\n']
>>> s2 = ['python\n', 'eggy\n', 'hamster\n', 'guido\n']
>>> for line in context_diff(s1, s2, fromfile='before.py', tofile='after.py'):
...     sys.stdout.write(line)  
*** before.py
--- after.py
***************
*** 1,4 ****
! bacon
! eggs
! ham
  guido
--- 1,4 ----
! python
! eggy
! hamster
  guido

有关更详细的示例，请参阅 difflib 的命令行界面。

2.3 版中的新功能。

difflib.get_close_matches(word, possibilities[, n][, cutoff])

返回最佳“足够好”匹配的列表。 word 是需要接近匹配的序列（通常是字符串），possibilities 是与 word 匹配的序列列表（通常是列表字符串）。

可选参数 n（默认 3）是要返回的最大匹配数； n 必须大于 0。

可选参数 cutoff（默认 0.6）是 [0, 1] 范围内的浮点数。得分不至少与 word 相似的可能性将被忽略。

可能性中最好的（不超过 n）匹配在列表中返回，按相似度得分排序，最相似的在前。

>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
['apple', 'ape']
>>> import keyword
>>> get_close_matches('wheel', keyword.kwlist)
['while']
>>> get_close_matches('apple', keyword.kwlist)
[]
>>> get_close_matches('accept', keyword.kwlist)
['except']

difflib.ndiff(a, b[, linejunk][, charjunk])

比较 a 和 b（字符串列表）；返回一个 Differ 样式的增量（一个 generator 生成增量线）。

可选关键字参数 linejunk 和 charjunk 用于过滤函数（或 None）：

linejunk：接受单个字符串参数的函数，如果字符串是垃圾则返回真，否则返回假。默认为 (None)，从 Python 2.3 开始。在此之前，默认是模块级函数 IS_LINE_JUNK()，它过滤掉没有可见字符的行，除了最多一个磅字符（'#'）。从 Python 2.3 开始，底层的 SequenceMatcher 类对哪些行如此频繁以至于构成噪声进行动态分析，这通常比 2.3 之前的默认值更有效。

charjunk：接受一个字符（长度为1的字符串）的函数，如果字符是垃圾则返回，否则返回false。默认是模块级函数 IS_CHARACTER_JUNK()，它过滤掉空白字符（空白或制表符；注意：在此包含换行符是个坏主意！）。

Tools/scripts/ndiff.py 是此函数的命令行前端。

>>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
...              'ore\ntree\nemu\n'.splitlines(1))
>>> print ''.join(diff),
- one
?  ^
+ ore
?  ^
- two
- three
?  -
+ tree
+ emu

difflib.restore(sequence, which)

返回生成增量的两个序列之一。

给定由 Differ.compare() 或 ndiff() 生成的序列，提取源自文件 1 或 2 的行（参数 which )，去掉行前缀。

例子：

>>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
...              'ore\ntree\nemu\n'.splitlines(1))
>>> diff = list(diff) # materialize the generated delta into a list
>>> print ''.join(restore(diff, 1)),
one
two
three
>>> print ''.join(restore(diff, 2)),
ore
tree
emu

difflib.unified_diff(a, b[, fromfile][, tofile][, fromfiledate][, tofiledate][, n][, lineterm])

比较 a 和 b（字符串列表）；以统一的差异格式返回一个增量（一个 generator 生成增量线）。

统一差异是一种紧凑的方式，仅显示已更改的行加上几行上下文。更改以内联样式显示（而不是单独的前/后块）。上下文行的数量由 n 设置，默认为 3。

默认情况下，差异控制行（带有 ---、+++ 或 @@ 的那些）使用尾随换行符创建。这很有用，因此从 file.readlines() 创建的输入会产生适合与 file.writelines() 一起使用的差异，因为输入和输出都有尾随换行符。

对于没有尾随换行符的输入，将 lineterm 参数设置为 "" 以便输出将统一无换行符。

上下文差异格式通常有一个文件名和修改时间的标题。可以使用 fromfile、tofile、fromfiledate 和 tofiledate 的字符串指定其中的任何一个或全部。修改时间通常以 ISO 8601 格式表示。如果未指定，则字符串默认为空白。

>>> s1 = ['bacon\n', 'eggs\n', 'ham\n', 'guido\n']
>>> s2 = ['python\n', 'eggy\n', 'hamster\n', 'guido\n']
>>> for line in unified_diff(s1, s2, fromfile='before.py', tofile='after.py'):
...     sys.stdout.write(line)   
--- before.py
+++ after.py
@@ -1,4 +1,4 @@
-bacon
-eggs
-ham
+python
+eggy
+hamster
 guido

有关更详细的示例，请参阅 difflib 的命令行界面。

2.3 版中的新功能。

difflib.IS_LINE_JUNK(line): 对于可忽略的行返回 true。如果行为空白或包含单个'#'，则行行可忽略，否则不可忽略。在 Python 2.3 之前用作 ndiff() 中参数 linejunk 的默认值。

difflib.IS_CHARACTER_JUNK(ch): 对于可忽略的字符返回 true。如果 ch 是空格或制表符，字符 ch 是可忽略的，否则不可忽略。用作 ndiff() 中参数 charjunk 的默认值。

也可以看看

模式匹配：格式塔方法: John W. 对类似算法的讨论。拉特克利夫和 D. E. 梅泽纳。这是发表在博士。多布的日记 1988 年 7 月。

7.4.1. SequenceMatcher 对象

SequenceMatcher 类有这个构造函数：

class difflib.SequenceMatcher(isjunk=None, a=, b=, autojunk=True)

可选参数 isjunk 必须是 None（默认值）或一个单参数函数，当且仅当该元素是“垃圾”并且应该被忽略时，该函数接受一个序列元素并返回 true。为 isjunk 传递 None 相当于传递 lambda x: 0；换句话说，不会忽略任何元素。例如，通过：

lambda x: x in " \t"

如果您将行作为字符序列进行比较，并且不想在空白或硬制表符上进行同步。

可选参数 a 和 b 是要比较的序列；两者都默认为空字符串。两个序列的元素必须是 hashable。

可选参数 autojunk 可用于禁用自动垃圾启发式。

2.7.1 新功能： autojunk 参数。

SequenceMatcher 对象有以下方法：

set_seqs(a, b): 设置要比较的两个序列。

SequenceMatcher计算并缓存第二个序列的详细信息，所以如果你想比较一个序列和多个序列，使用set_seq2()设置一次常用序列并调用 ]set_seq1() 重复，每个其他序列一次。

set_seq1(a): 设置要比较的第一个序列。要比较的第二个序列没有改变。

set_seq2(b): 设置要比较的第二个序列。要比较的第一个序列没有改变。

find_longest_match(alo, ahi, blo, bhi)

在 a[alo:ahi] 和 b[blo:bhi] 中找到最长的匹配块。

如果 isjunk 被省略或 None，find_longest_match() 返回 (i, j, k) 使得 a[i:i+k] 等于 b[j:j+k] ]，其中 alo <= i <= i+k <= ahi 和 blo <= j <= j+k <= bhi。对于所有满足这些条件的(i', j', k')，附加条件k >= k'、i <= i'，如果i == i'、j <= j'也满足。换句话说，在所有最大匹配块中，返回最早开始于 a 的块，在所有最大匹配块中最早开始于 a 的块中，返回最早开始于 a 的块b。

>>> s = SequenceMatcher(None, " abcd", "abcd abcd")
>>> s.find_longest_match(0, 5, 0, 9)
Match(a=0, b=4, size=5)

如果提供了 isjunk，首先如上所述确定最长匹配块，但附加限制是块中不出现垃圾元素。然后通过匹配（仅）两侧的垃圾元素来尽可能地扩展该块。因此，结果块永远不会与垃圾匹配，除非相同的垃圾碰巧与有趣的匹配相邻。

这是与之前相同的示例，但将空白视为垃圾。这可以防止 ' abcd' 直接匹配第二个序列尾端的 ' abcd'。相反，只有 'abcd' 可以匹配，并匹配第二个序列中最左边的 'abcd'：

>>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
>>> s.find_longest_match(0, 5, 0, 9)
Match(a=1, b=0, size=4)

如果没有块匹配，则返回 (alo, blo, 0)。

2.6 版更改：该方法返回一个名为的元组 Match(a, b, size)。

get_matching_blocks()

返回描述非重叠匹配子序列的三元组列表。每个三元组的形式为 (i, j, n)，表示 a[i:i+n] == b[j:j+n]。三元组在 i 和 j 中单调递增。

最后一个三元组是一个哑元，值为 (len(a), len(b), 0)。它是唯一带有 n == 0 的三元组。如果 (i, j, n) 和 (i', j', n') 是列表中的相邻三元组，并且第二个不是列表中的最后一个三元组，则 i+n < i' 或 j+n < j'；换句话说，相邻的三元组总是描述不相邻的相等块。

2.5 版更改：实现了相邻三元组总是描述非相邻块的保证。

>>> s = SequenceMatcher(None, "abxcd", "abcd")
>>> s.get_matching_blocks()
[Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]

get_opcodes()

返回描述如何将 a 转换为 b 的 5 元组列表。每个元组的形式为 (tag, i1, i2, j1, j2)。第一个元组有 i1 == j1 == 0，其余元组有 i1 等于前一个元组的 i2，同样，j1 等于之前的 j2。

tag 值是字符串，具有以下含义：

价值	意义
`'replace'`	`a[i1:i2]` 应替换为 `b[j1:j2]`。
`'delete'`	`a[i1:i2]` 应该被删除。请注意在这种情况下 `j1 == j2`。
`'insert'`	`b[j1:j2]` 应插入 `a[i1:i1]`。请注意在这种情况下 `i1 == i2`。
`'equal'`	`a[i1:i2] == b[j1:j2]`（子序列相等）。

例如：

>>> a = "qabxcd"
>>> b = "abycdf"
>>> s = SequenceMatcher(None, a, b)
>>> for tag, i1, i2, j1, j2 in s.get_opcodes():
...    print ("%7s a[%d:%d] (%s) b[%d:%d] (%s)" %
...           (tag, i1, i2, a[i1:i2], j1, j2, b[j1:j2]))
 delete a[0:1] (q) b[0:0] ()
  equal a[1:3] (ab) b[0:2] (ab)
replace a[3:4] (x) b[2:3] (y)
  equal a[4:6] (cd) b[3:5] (cd)
 insert a[6:6] () b[5:6] (f)

get_grouped_opcodes([n])

返回一个 generator 组，最多 n 行上下文。

从 get_opcodes() 返回的组开始，此方法拆分出较小的更改集群并消除没有更改的中间范围。

这些组以与 get_opcodes() 相同的格式返回。

2.3 版中的新功能。

ratio()

以 [0, 1] 范围内的浮点数形式返回序列相似性的度量。

其中 T 是两个序列中元素的总数，M 是匹配的数量，这是 2.0*M / T。请注意，如果序列相同，则为 1.0，如果它们没有共同点，则为 0.0。

如果 get_matching_blocks() 或 get_opcodes() 尚未被调用，则计算成本很高，在这种情况下，您可能想尝试 quick_ratio() 或real_quick_ratio() 首先得到一个上限。

quick_ratio(): 相对较快地返回 ratio() 的上限。

real_quick_ratio(): 非常快速地返回 ratio() 的上限。

尽管 quick_ratio() 和 real_quick_ratio() 始终至少与 ratio() 一样大，但返回匹配与总字符比的三种方法由于近似程度不同而可能给出不同的结果：

>>> s = SequenceMatcher(None, "abcd", "bcde")
>>> s.ratio()
0.75
>>> s.quick_ratio()
0.75
>>> s.real_quick_ratio()
1.0

7.4.2. 序列匹配器示例

此示例比较两个字符串，将空白视为“垃圾”：

>>> s = SequenceMatcher(lambda x: x == " ",
...                     "private Thread currentThread;",
...                     "private volatile Thread currentThread;")

ratio() 在 [0, 1] 中返回一个浮点数，衡量序列的相似性。根据经验，ratio() 值超过 0.6 意味着序列是接近匹配的：

>>> print round(s.ratio(), 3)
0.866

如果您只对序列匹配的位置感兴趣，get_matching_blocks() 很方便：

>>> for block in s.get_matching_blocks():
...     print "a[%d] and b[%d] match for %d elements" % block
a[0] and b[0] match for 8 elements
a[8] and b[17] match for 21 elements
a[29] and b[38] match for 0 elements

请注意，get_matching_blocks() 返回的最后一个元组始终是一个哑元，(len(a), len(b), 0)，并且这是最后一个元组元素（匹配的元素数）为 0 的唯一情况.

如果您想知道如何将第一个序列更改为第二个序列，请使用 get_opcodes()：

>>> for opcode in s.get_opcodes():
...     print "%6s a[%d:%d] b[%d:%d]" % opcode
 equal a[0:8] b[0:8]
insert a[8:8] b[8:17]
 equal a[8:29] b[17:38]

也可以看看

此模块中的 get_close_matches() 函数展示了如何使用在 SequenceMatcher 上构建简单代码来完成有用的工作。
简单版本控制配方，用于使用SequenceMatcher构建的小型应用程序。

7.4.3. 不同的对象

请注意，Differ 生成的增量并没有声称是最小差异。相反，最小差异通常是违反直觉的，因为它们在任何可能的地方同步，有时会意外匹配相隔 100 页。将同步点限制为连续匹配保留了一些局部性的概念，但偶尔会产生更长的差异。

Differ 类具有以下构造函数：

class difflib.Differ([linejunk[, charjunk]])

可选关键字参数 linejunk 和 charjunk 用于过滤函数（或 None）：

linejunk：一个接受单个字符串参数的函数，如果字符串是垃圾则返回真。默认值为 None，这意味着没有线路被视为垃圾。

charjunk：接受单个字符参数（长度为 1 的字符串）的函数，如果字符是垃圾字符则返回 true。默认值为 None，表示没有字符被视为垃圾。

Differ 对象通过单一方法使用（生成增量）：

compare(a, b)

比较两个行序列，并生成增量（行序列）。

每个序列必须包含单独的以换行符结尾的单行字符串。这样的序列可以从类文件对象的 readlines() 方法中获得。生成的 delta 还包含以换行符结尾的字符串，可以通过类似文件的对象的 writelines() 方法按原样打印。

7.4.4. 不同的例子

此示例比较两个文本。首先我们设置文本，以换行符结尾的单个单行字符串的序列（此类序列也可以从类文件对象的 readlines() 方法中获得）：

>>> text1 = '''  1. Beautiful is better than ugly.
...   2. Explicit is better than implicit.
...   3. Simple is better than complex.
...   4. Complex is better than complicated.
... '''.splitlines(1)
>>> len(text1)
4
>>> text1[0][-1]
'\n'
>>> text2 = '''  1. Beautiful is better than ugly.
...   3.   Simple is better than complex.
...   4. Complicated is better than complex.
...   5. Flat is better than nested.
... '''.splitlines(1)

接下来我们实例化一个Differ对象：

>>> d = Differ()

请注意，在实例化 Differ 对象时，我们可能会传递函数来过滤掉行和字符“垃圾”。有关详细信息，请参阅 Differ() 构造函数。

最后，我们比较一下两者：

>>> result = list(d.compare(text1, text2))

result 是一个字符串列表，所以让我们漂亮地打印它：

>>> from pprint import pprint
>>> pprint(result)
['    1. Beautiful is better than ugly.\n',
 '-   2. Explicit is better than implicit.\n',
 '-   3. Simple is better than complex.\n',
 '+   3.   Simple is better than complex.\n',
 '?     ++\n',
 '-   4. Complex is better than complicated.\n',
 '?            ^                     ---- ^\n',
 '+   4. Complicated is better than complex.\n',
 '?           ++++ ^                      ^\n',
 '+   5. Flat is better than nested.\n']

作为单个多行字符串，它看起来像这样：

>>> import sys
>>> sys.stdout.writelines(result)
    1. Beautiful is better than ugly.
-   2. Explicit is better than implicit.
-   3. Simple is better than complex.
+   3.   Simple is better than complex.
?     ++
-   4. Complex is better than complicated.
?            ^                     ---- ^
+   4. Complicated is better than complex.
?           ++++ ^                      ^
+   5. Flat is better than nested.

7.4.5. difflib 的命令行界面

此示例显示如何使用 difflib 创建类似 diff 的实用程序。它也包含在 Python 源代码分发中，作为 Tools/scripts/diff.py。

""" Command line interface to difflib.py providing diffs in four formats:

* ndiff:    lists every line and highlights interline changes.
* context:  highlights clusters of changes in a before/after format.
* unified:  highlights clusters of changes in an inline format.
* html:     generates side by side comparison with change highlights.

"""

import sys, os, time, difflib, optparse

def main():
     # Configure the option parser
    usage = "usage: %prog [options] fromfile tofile"
    parser = optparse.OptionParser(usage)
    parser.add_option("-c", action="store_true", default=False,
                      help='Produce a context format diff (default)')
    parser.add_option("-u", action="store_true", default=False,
                      help='Produce a unified format diff')
    hlp = 'Produce HTML side by side diff (can use -c and -l in conjunction)'
    parser.add_option("-m", action="store_true", default=False, help=hlp)
    parser.add_option("-n", action="store_true", default=False,
                      help='Produce a ndiff format diff')
    parser.add_option("-l", "--lines", type="int", default=3,
                      help='Set number of context lines (default 3)')
    (options, args) = parser.parse_args()

    if len(args) == 0:
        parser.print_help()
        sys.exit(1)
    if len(args) != 2:
        parser.error("need to specify both a fromfile and tofile")

    n = options.lines
    fromfile, tofile = args # as specified in the usage string

    # we're passing these as arguments to the diff function
    fromdate = time.ctime(os.stat(fromfile).st_mtime)
    todate = time.ctime(os.stat(tofile).st_mtime)
    with open(fromfile, 'U') as f:
        fromlines = f.readlines()
    with open(tofile, 'U') as f:
        tolines = f.readlines()

    if options.u:
        diff = difflib.unified_diff(fromlines, tolines, fromfile, tofile,
                                    fromdate, todate, n=n)
    elif options.n:
        diff = difflib.ndiff(fromlines, tolines)
    elif options.m:
        diff = difflib.HtmlDiff().make_file(fromlines, tolines, fromfile,
                                            tofile, context=options.c,
                                            numlines=n)
    else:
        diff = difflib.context_diff(fromlines, tolines, fromfile, tofile,
                                    fromdate, todate, n=n)

    # we're using writelines because diff is a generator
    sys.stdout.writelines(diff)

if __name__ == '__main__':
    main()

7.4. difflib — 计算增量的助手 — Python 文档

7.4. 差异库 — 计算增量的助手

7.4.1. SequenceMatcher 对象

7.4.2. 序列匹配器示例

7.4.3. 不同的对象

7.4.4. 不同的例子

7.4.5. difflib 的命令行界面