6.3. difflib - 计算增量的助手

源代码: Lib / difflib.py

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

class difflib.SequenceMatcher

这是用于比较任何类型的序列对的灵活类,只要序列元素hashable基本算法比20世纪80年代末由Ratcliff和Obershelp在双曲线名称“gestalt模式匹配”下发布的算法早,并且是一个有趣的人。这个想法是找到不包含“垃圾”元素的最长的连续匹配子序列;这些“垃圾”元素在某种意义上是不感兴趣的元素,例如空白行或空格。(处理垃圾是Ratcliff和Obershelp算法的扩展。)然后将相同的想法递归地应用于匹配子序列左侧和右侧的序列片段。这不产生最小的编辑序列,但往往产生“看起来正确”的人的匹配。

计时:基本Ratcliff-Obershelp算法是最坏情况下的三次时间和预期情况下的二次时间。SequenceMatcher是最坏情况的二次时间,并且预期情况行为以复杂的方式依赖于序列具有共同数量的元素;最佳情况时间是线性的。

自动垃圾启发式: SequenceMatcher支持自动将某些序列项视为垃圾的启发式算法。启发式计算每个单个项目在序列中出现的次数。如果项目的重复项(在第一个项目之后)占序列的1%以上且序列长度至少为200个项目,则该项目被标记为“流行”,并被视为垃圾以用于序列匹配。在创建SequenceMatcher时,可以通过将autojunk参数设置为False来关闭此试探。

版本3.2中的新功能: 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,其中行不换行。

linejunkcharjunk是传递到ndiff()中的可选关键字参数(由HtmlDiff HTML差异)。有关参数默认值和说明,请参见ndiff()文档。

以下方法是公共的:

make_file(fromlines, tolines, fromdesc='', todesc='', context=False, numlines=5, *, charset='utf-8')

比较fromlinestolines(字符串列表),并返回一个字符串,它是一个完整的HTML文件,包含一个表格,显示逐行和行内变化突出显示。

fromdesctodesc是指定从/到文件列标题字符串(默认为空字符串)的可选关键字参数。

上下文numlines都是可选的关键字参数。当要显示上下文差异时,将上下文设置为True,否则默认值为False,以显示完整文件。numlines默认为5上下文True numlines控制围绕差异亮点的上下文线的数量。上下文False numlines控制在使用“下一个”超链​​接时显示在差异突出显示之前的行数导致“下一个”超链​​接将下一个差异突出显示在浏览器的顶部,而没有任何前导上下文)。

在版本3.5中已更改: charset仅添加了关键字参数。HTML文档的默认字符集从'ISO-8859-1'更改为'utf-8'

make_table(fromlines, tolines, fromdesc='', todesc='', context=False, numlines=5)

比较fromlinestolines(字符串列表),并返回一个字符串,它是一个完整的HTML表格,显示逐行间差异,突出显示行间和行内更改。

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

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

difflib.context_diff(a, b, fromfile='', tofile='', fromfiledate='', tofiledate='', n=3, lineterm='\n')

比较ab(字符串列表);在上下文差异格式中返回Δ(生成Δ行的generator)。

上下文差异是一种紧凑的方式,只显示已更改的行和上下文的几行。更改以前/后样式显示。上下文线的数量由n设置,默认为三个。

默认情况下,diff控制行(具有***---的行)使用尾随换行符创建。这有助于使从io.IOBase.readlines()创建的输入产生适合与io.IOBase.writelines()一起使用的差异,因为输入和输出具有尾随换行符。

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

上下文差异格式通常具有文件名和修改时间的头。可以使用fromfiletofilefromfiledatetofiledate的字符串指定这些中的任何一个或全部。修改时间通常以ISO 8601格式表示。如果未指定,则字符串默认为空。

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

有关更详细的示例,请参见A command-line interface to difflib

difflib.get_close_matches(word, possibilities, n=3, cutoff=0.6)

返回最好的“足够好”匹配的列表。是希望接近匹配的序列(通常是字符串),可能是匹配通常是字符串列表)。

可选参数n(默认3)是要返回的最大匹配数; n必须大于0

可选参数cutoff(默认0.6)是范围[0,1]中的浮点型。忽略至少类似于的分数的可能性。

在列表中返回可能性中的最佳(不超过n)个匹配,按照相似性分数排序,首先最相似。

>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
['apple', 'ape']
>>> import keyword
>>> get_close_matches('wheel', keyword.kwlist)
['while']
>>> get_close_matches('pineapple', keyword.kwlist)
[]
>>> get_close_matches('accept', keyword.kwlist)
['except']
difflib.ndiff(a, b, linejunk=None, charjunk=IS_CHARACTER_JUNK)

比较ab(字符串列表);返回Differ样式增量(a generator生成增量线)。

可选的关键字参数linejunkcharjunk是过滤函数(或None):

linejunk:接受单个字符串参数的函数,如果字符串为junk则返回true,否则返回false。默认值为None还有一个模块级函数IS_LINE_JUNK(),它过滤掉没有可见字符的行,除了最多一个字符('#') - SequenceMatcher类对哪些行频繁构成噪声进行动态分析,这通常比使用此函数工作更好。

charjunk:接受字符(长度为1的字符串)的函数,如果字符是垃圾则返回,否则返回false。默认是模块级函数IS_CHARACTER_JUNK(),它过滤掉空格字符(空格或制表符;在这里包含换行符是个不错的主意!)。

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

>>> diff = ndiff('one\ntwo\nthree\n'.splitlines(keepends=True),
...              'ore\ntree\nemu\n'.splitlines(keepends=True))
>>> print(''.join(diff), end="")
- one
?  ^
+ ore
?  ^
- two
- three
?  -
+ tree
+ emu
difflib.restore(sequence, which)

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

给定由Differ.compare()ndiff()生成的序列,提取源自文件1或2(参数),剥离离线前缀。

例:

>>> diff = ndiff('one\ntwo\nthree\n'.splitlines(keepends=True),
...              'ore\ntree\nemu\n'.splitlines(keepends=True))
>>> diff = list(diff) # materialize the generated delta into a list
>>> print(''.join(restore(diff, 1)), end="")
one
two
three
>>> print(''.join(restore(diff, 2)), end="")
ore
tree
emu
difflib.unified_diff(a, b, fromfile='', tofile='', fromfiledate='', tofiledate='', n=3, lineterm='\n')

比较ab(字符串列表);以统一差分格式返回增量(generator生成增量线)。

统一差异是一种紧凑的方式,仅显示已更改的行,以及几行上下文。更改以内联样式显示(而不是单独的前/后块)。上下文线的数量由n设置,默认为三个。

默认情况下,使用尾随换行创建diff控制行(具有---+++@@的那些)这有助于使从io.IOBase.readlines()创建的输入产生适合与io.IOBase.writelines()一起使用的差异,因为输入和输出具有尾随换行符。

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

上下文差异格式通常具有文件名和修改时间的头。可以使用fromfiletofilefromfiledatetofiledate的字符串指定这些中的任何一个或全部。修改时间通常以ISO 8601格式表示。如果未指定,则字符串默认为空。

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

有关更详细的示例,请参见A command-line interface to difflib

difflib.diff_bytes(dfunc, a, b, fromfile=b'', tofile=b'', fromfiledate=b'', tofiledate=b'', n=3, lineterm=b'\n')

使用dfunc比较ab(字节对象列表);以dfunc返回的格式生成一个delta行(也是字节)序列。dfunc必须是可调用的,通常为unified_diff()context_diff()

允许您比较未知或不一致编码的数据。n之外的所有输入必须是字节对象,而不是str。通过将所有输入(除n)无损地转换为str并调用dfunc(a, b, tofile, fromfiledate, tofiledate, n, lineterm)dfunc的输出然后转换回字节,因此您接收的delta线具有与ab相同的未知/不一致编码, 。

版本3.5中的新功能。

difflib。 IS_LINE_JUNK 线

对于可忽略的行返回true。如果为空白或包含单个'#',则可忽略,否则不可忽略。用作旧版本中ndiff()中参数linejunk的默认值。

difflib.IS_CHARACTER_JUNK(ch)

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

也可以看看

模式匹配:Gestalt方法
讨论John W. Ratcliff和D. E. Metzener的类似算法。这发表在Dr。 Dobb's Journal

6.3.1.SequenceMatcher对象

SequenceMatcher类具有此构造函数:

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

可选参数isjunk必须是None(默认值)或单参数函数,它接受一个序列元素,并且当且仅当元素是“junk”被忽略。None传递给isjunk等效于传递lambda x: 0 ;换句话说,没有元素被忽略。例如,pass:

lambda x: x in " \t"

如果你将行作为字符序列进行比较,并且不想在空白或硬标签上同步。

可选参数ab是要比较的序列;两者默认为空字符串。这两个序列的元素必须hashable

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

版本3.2中的新功能: autojunk参数。

SequenceMatcher对象获得三个数据属性:bjunkb的元素集合,isjunkTruebpopular是启发式算法流行的非垃圾元素集合(如果未禁用); b2j是将b的其余元素映射到它们出现的位置的列表的dict。bset_seqs()set_seq2()复位时,

版本3.2中的新功能: bjunkbpopular属性。

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]中查找最长匹配块。

If isjunk was omitted or None, find_longest_match() returns (i, j, k) such that a[i:i+k] is equal to b[j:j+k], where alo <= i <= i+k <= ahi and blo <= j <= j+k <= bhi. 对于满足那些条件的所有(i', j', k'),附加条件k = k'i / t10> i',并且如果i == t12>,j j'换句话说,在所有最大匹配块中,返回在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' / t3>在第二序列的尾端。而只有'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)

此方法返回named tuple 匹配(a, b, size)

get_matching_blocks()

描述匹配子序列的三元组的返回列表。每个三元组具有形式(i, j, n),并且意味着 a [i:i + n] == b [j:j + n]三元组在ij中单调递增。

最后三个是虚拟的,并且具有值(len(a), len(b), 0) t0>。它是n == 0的唯一三元组。如果(i, j, n)> j', n')是列表中的相邻三元组,第二个不是列表中的最后一个三元组,则 != i'j + n / t14> j';换句话说,相邻三元组总是描述不相邻的相等块。

>>> 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元组返回列表。每个元组具有(标签, i1, i2, j1, j2 )第一个元组有i1 = = j1 = = 0,还有i1等于从前面的元组,和,同样,等于以前的j2 j1 i2剩余的元组。

标记值是字符串,具有以下含义:

含义
'replace'a[i1:i2]应替换为b[j1:j2]
'delete'a[i1:i2]应被删除。注意,在这种情况下,j1 == j2
'insert'应在a[i1:i1]插入b[j1:j2]请注意,在这种情况下,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('{:7}   a[{}:{}] --> b[{}:{}] {!r:>8} --> {!r}'.format(
...         tag, i1, i2, j1, j2, a[i1:i2], b[j1:j2]))
delete    a[0:1] --> b[0:0]      'q' --> ''
equal     a[1:3] --> b[0:2]     'ab' --> 'ab'
replace   a[3:4] --> b[2:3]      'x' --> 'y'
equal     a[4:6] --> b[3:5]     'cd' --> 'cd'
insert    a[6:6] --> b[5:6]       '' --> 'f'
get_grouped_opcodes(n=3)

返回具有高达n行上下文的组的generator

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

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

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

6.3.2.SequenceMatcher示例

此示例比较两个字符串,将空格视为“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]

也可以看看

6.3.3.Differ对象

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

Differ类具有此构造函数:

class difflib.Differ(linejunk=None, charjunk=None)

可选的关键字参数linejunkcharjunk用于过滤器功能(或None):

linejunk:接受单个字符串参数的函数,如果字符串是junk,则返回true。默认值为None,表示没有行被认为是垃圾。

charjunk:接受单个字符参数(长度为1的字符串)的函数,如果字符是垃圾则返回true。默认值为None,表示没有字符被认为是垃圾。

这些垃圾过滤功能加速匹配以发现差异,并且不会导致任何不同的行或字符被忽略。请阅读find_longest_match()方法的isjunk参数的说明,以获取说明。

通过单个方法使用Differ对象(生成增量)

compare(a, b)

比较两个序列的行,并生成增量(行序列)。

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

6.3.4.Differ示例

本示例比较两个文本。首先我们设置文本,以换行符结尾的单个单行字符串的序列(这样的序列也可以从文件状对象的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(keepends=True)
>>> 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(keepends=True)

接下来我们实例化一个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.

6.3.5.A command-line interface to difflib

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

#!/usr/bin/env python3
""" 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, argparse
from datetime import datetime, timezone

def file_mtime(path):
    t = datetime.fromtimestamp(os.stat(path).st_mtime,
                               timezone.utc)
    return t.astimezone().isoformat()

def main():

    parser = argparse.ArgumentParser()
    parser.add_argument('-c', action='store_true', default=False,
                        help='Produce a context format diff (default)')
    parser.add_argument('-u', action='store_true', default=False,
                        help='Produce a unified format diff')
    parser.add_argument('-m', action='store_true', default=False,
                        help='Produce HTML side by side diff '
                             '(can use -c and -l in conjunction)')
    parser.add_argument('-n', action='store_true', default=False,
                        help='Produce a ndiff format diff')
    parser.add_argument('-l', '--lines', type=int, default=3,
                        help='Set number of context lines (default 3)')
    parser.add_argument('fromfile')
    parser.add_argument('tofile')
    options = parser.parse_args()

    n = options.lines
    fromfile = options.fromfile
    tofile = options.tofile

    fromdate = file_mtime(fromfile)
    todate = file_mtime(tofile)
    with open(fromfile) as ff:
        fromlines = ff.readlines()
    with open(tofile) as tf:
        tolines = tf.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)

    sys.stdout.writelines(diff)

if __name__ == '__main__':
    main()