7.4. difflib — 计算差异的辅助工具

2.1 新版功能.

此模块提供用于比较序列的类和函数。 例如，它可以用于比较文件，并可以产生各种格式的不同信息，包括 HTML 和上下文以及统一格式的差异点。 有关目录和文件的比较，请参见 filecmp 模块。

class difflib.SequenceMatcher

This is a flexible class for comparing pairs of sequences of any type, so long as the sequence elements are hashable. The basic algorithm predates, and is a little fancier than, an algorithm published in the late 1980’s by Ratcliff and Obershelp under the hyperbolic name “gestalt pattern matching.” The idea is to find the longest contiguous matching subsequence that contains no “junk” elements (the Ratcliff and Obershelp algorithm doesn’t address junk). The same idea is then applied recursively to the pieces of the sequences to the left and to the right of the matching subsequence. This does not yield minimal edit sequences, but does tend to yield matches that “look right” to people.

耗时: 基本 Ratcliff-Obershelp 算法在最坏情况下为立方时间而在一般情况下为平方时间。 SequenceMatcher 在最坏情况下为平方时间而在一般情况下的行为受到序列中有多少相同元素这一因素的微妙影响；在最佳情况下则为线性时间。

自动垃圾启发式计算: SequenceMatcher 支持使用启发式计算来自动将特定序列项视为垃圾。 这种启发式计算会统计每个单独项在序列中出现的次数。 如果某一项（在第一项之后）的重复次数超过序列长度的 1% 并且序列长度至少有 200 项，该项会被标记为“热门”并被视为序列匹配中的垃圾。 这种启发式计算可以通过在创建 SequenceMatcher 时将 autojunk 参数设为 False 来关闭。

2.7.1 新版功能: autojunk 形参。

class difflib.Differ

这个类的作用是比较由文本行组成的序列，并产生可供人阅读的差异或增量信息。 Differ 统一使用 SequenceMatcher 来完成行序列的比较以及相似（接近匹配）行内部字符序列的比较。

Differ 增量的每一行均以双字母代码打头：

双字母代码	含义
'- '	行为序列 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 设定，默认为三行。

By default, the diff control lines (those with *** or ---) are created with a trailing newline. This is helpful so that inputs created from file.readlines() result in diffs that are suitable for use with file.writelines() since both the inputs and outputs have trailing newlines.

对于没有末尾换行符的输入，应将 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: A function that accepts a single string argument, and returns true if the string is junk, or false if not. The default is (None), starting with Python 2.3. Before then, the default was the module-level function IS_LINE_JUNK(), which filters out lines without visible characters, except for at most one pound character ('#'). As of Python 2.3, the underlying SequenceMatcher class does a dynamic analysis of which lines are so frequent as to constitute noise, and this usually works better than the pre-2.3 default.

charjunk: A function that accepts a character (a string of length 1), and returns if the character is junk, or false if not. The default is module-level function IS_CHARACTER_JUNK(), which filters out whitespace characters (a blank or tab; note: bad idea to include newline in this!).

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 设定，默认为三行。

By default, the diff control lines (those with ---, +++, or @@) are created with a trailing newline. This is helpful so that inputs created from file.readlines() result in diffs that are suitable for use with file.writelines() since both the inputs and outputs have trailing newlines.

对于没有末尾换行符的输入，应将 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)

Return true for ignorable lines. The line line is ignorable if line is blank or contains a single '#', otherwise it is not ignorable. Used as a default for parameter linejunk in ndiff() before Python 2.3.

difflib.IS_CHARACTER_JUNK(ch)

Return true for ignorable characters. The character ch is ignorable if ch is a space or tab, otherwise it is not ignorable. Used as a default for parameter charjunk in ndiff().

参见

模式匹配：格式塔方法

John W. Ratcliff 和 D. E. Metzener 对于一种类似算法的讨论。 此文于 1988 年 7 月发表于 Dr. Dobb’s Journal。

7.4.1. SequenceMatcher 对象

SequenceMatcher 类具有这样的构造器：

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

Optional argument isjunk must be None (the default) or a one-argument function that takes a sequence element and returns true if and only if the element is “junk” and should be ignored. Passing None for isjunk is equivalent to passing lambda x: 0; in other words, no elements are ignored. For example, pass:

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')，如果 i == i', j <= j' 也被满足，则附加条件 k >= k', i <= i'。 换句话说，对于所有最长匹配块，返回在 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 版更改: 此方法将返回一个 named tuple 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 版更改: The guarantee that adjacent triples always describe non-adjacent blocks was implemented.

>>> 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] (两个子序列相同)。

For example:

>>> 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])

返回一个带有最多 n 行上下文的分组的 generator。

从 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. SequenceMatcher 的示例

This example compares two strings, considering blanks to be “junk:”

>>> 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 对象

请注意 Differ 所生成的增量并不保证是 最小 差异。 相反，最小差异往往是违反直觉的，因为它们会同步任何可能的地方，有时甚至意外产生相距 100 页的匹配。 将同步点限制为连续匹配保留了一些局部性概念，这偶尔会带来产生更长差异的代价。

Differ 类具有这样的构造器：

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

可选关键字形参 linejunk 和 charjunk 均为过滤函数 (或为 None)：

linejunk: 接受单个字符串作为参数的函数，如果其为垃圾字符串则返回真值。 默认值为 None，意味着没有任何行会被视为垃圾行。

charjunk: 接受单个字符（长度为 1 的字符串）作为参数的函数，如果其为垃圾字符则返回真值。 默认值为 None，意味着没有任何字符会被视为垃圾字符。

Differ 对象是通过一个单独方法来使用（生成增量）的：

compare(a, b)

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

Each sequence must contain individual single-line strings ending with newlines. Such sequences can be obtained from the readlines() method of file-like objects. The delta generated also consists of newline-terminated strings, ready to be printed as-is via the writelines() method of a file-like object.

7.4.4. Differ 示例

This example compares two texts. First we set up the texts, sequences of individual single-line strings ending with newlines (such sequences can also be obtained from the readlines() method of file-like objects):

>>> 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()