diff 和 patch 工具的使用
双文件 diff 和 patch
很多 shell 或者版本控制系统都内置 diff 工具，用来逐行对比两个或多个文件。以最常用的两个文件 diff 为示例。【例子1】按下图创造 a.txt 和 b.txt 两个文件，运行 shell 内置的 diff 工具： diff a.txt b.txt，会输出如下的 diff：
ln +==a.txt==+==b.txt==+==diff==
1 |this |this |3,7c3
2 |is |is |< some
3 |some |the |< text
4 |text |changed |< that
5 |that |text |< will
6 |will | |< be
7 |be | |---
8 |changed | |> the
9 | | |8a5
10 | | |> text观察 diff 的结构，它实际上告诉我们如何将原始文件 a.txt 转换到新文件 b.txt：
- 3,7c3，即将原始文件的第 3~7 行替换掉（去掉 some text that will be），替换为 “the”，插入新文件作为第 3 行
- 8a5，即在原始文件第 8 行后面的位置插入一行 “text”，作为新文件的第 5 行
- 这里没有出现的 d 代表删除，例如 145,146d144 代表删除原始文件第 145~146 行，删除的位置位于新文件的第 144 行（换言之，原始文件被删除的区间后面的内容接在新文件的第 144 行之后）
- 这种表示差异的格式被称为 default output format，是很多 shell 内置的 diff 工具默认采用的格式。格式不唯一，如它并不是 Git 表示 diff 的默认格式
正因此，已有 a.txt 和 diff 的情况下，原则上恢复出 b.txt – 事实上，patch 工具就可以自动帮我们完成这个操作。假设我们将 diff 存储到一个 patch 文件里：diff a.txt b.txt > c.patch。运行 patch a.txt c.patch，a.txt 原先的内容就会被覆盖，成为和 b.txt 相同的内容。
如 diff 命令帮助的开头所说：”Compare FILES line by line.“，diff 是 “逐行” 进行的，这个颗粒度恰到好处，比段落要细，比字符或者 symbol 要粗，刚好能够捕捉很多文本文件，特别是源代码的语义变化。也因此，diff 和 patch 这一对工具成为了存储、传输和应用代码仓库改动的标准。例如：A 和 B 有同一份代码仓库，A 在仓库的基础上做了一些修改，那么 A 只要运行一下 diff，把 diff 用电子邮件发给 B，B 就可以应用这些更改，看到和 A 同样的、改动后的仓库。
文件夹或仓库的 diff 和 patch
让我们以 Git 仓库和 Git 提供的一对 diff 和 patch 工具为例，看看上面的流程在操作上是如何进行的。
假设原始仓库中有 a, b 两个文件，A，B 各自 clone 了一份远程仓库。A 在本地仓库删除了 a，修改了 b，创建了一个新文件 c。接着，A 将 a, b, c 加入工作区，运行 git diff --staged > repo.patch，就可以得到一个记录其更改的 patch 文件。检查 patch 文件内容，其中记录了仓库中文件增加、删除和修改（此时伴随单文件 diff）的情况。
此后，A 将 repo.patch 发送给 B，B 在自己本地的仓库中运行 git apply repo.patch，就可以应用这些更改，拥有和 B 相同的仓库了。
diff 算法的评价标准：合法操作集合和最小代价改变
回到双文件 diff，思考 diff 工具是如何完成对比文件这一任务的。一个合法但无用的解法是输出 “将原始文件的所有行一并替换为新文件的所有行” ，但这样做没有实质上做对比。一个好的对比尽量避免重复两个文件都有的内容，仅仅指出它们不同之处。这在某种程度上等价于寻找如何做最少的改动 (diff) 将 a 变换到 b，因为 “最小” 意味着不做不必要的重复。
如此看来，每一组合法的 “改动” 组成的集合，都可以称为一个定义 diff 算法和格式的框架，在此框架下，可以通过 “改动” 的代价之和来评价 diff 算法好坏的标准。
删除行+插入行
回到【例子1】，尽管 default output format 有 a,d,c 三种变更方式，但我们不妨做如下简化的假设：1）认为 c 与它分解得到的 a 和 d 两次操作是同等代价的；2) 认为一次插入 N 行和 N 次插入一行是同等代价的。那么操作就归约到了如下两种：插入一行 和 删除一行。不妨设定，改动的代价 = 这两种操作的次数（也就是行数）之和。
- 该例子中， shell 内置的 diff 工具用 2 行插入和 5 行删除完成了从 a.txt 到 b.txt 的改动，代价为 7。注意到复用 “text” 而非 “changed” 同样代价为 7。
- 如果使用合法但无用的 “删除全部、替换全部” 算法，需要做 5 行插入和 8 行删除，代价为 13；如果只复用 “this is”，则需要做 3 行插入和 6 行删除，代价为 9
删除行+插入行+移动行
代价为 7 尽管很优，但我们看到其实我们在一处删除了 “text”，在另一处插入了 “text”，实际上重复了这一个 a.txt 和 b.txt 都有（但位置不同）的内容。设想我们额外允许第三种操作：移动行，将一行移动到另一处；然后让改动的代价等于这三种操作的次数之和。那么就有一种更优的改动方案：先将 text 移动到文件末尾，然后删除 “is some that will be”，代价为 6。这个改动方案进一步剔除了两个文件都有的内容，更加简洁。
更强大的合法操作集合意味着 diff 和 patch 算法及其文件格式变得更复杂，但能够以更少重复已有信息的方式完成改动，从而更清晰地刻画老文件到新文件之间的改变。
手搓一个简易的 diff 和 patch 工具组
让我们以 “删除一行” 和 “插入一行” 作为合法操作和代价的单位，寻找这个框架下的最优的双文件 diff 算法。要解决这个问题，只需注意到：将 a.txt 通过插入行和删除行变换到 b.txt 的路径和代价，等价于将 a.txt 和 b.txt 各自删除若干行，使得两者相同的路径和代价——只需将对 a 的插入转换为对 b 的删除即可。
后一个问题，删除的行数最少等价于最终二者公共的文件（或者说行的序列）最长。这个问题就是最长公共子序列问题（Longest Common Subsequence, LCS）。
this is some text that will be changed
+ + + +
| | \ /--------------/
| | X
| | / \--\
+ + + +
this is the changed text再次回到【例子1】，上面的示意图画出了 a.txt 和 b.txt 的两个最长的公共子序列：”this is text” 和 “this is changed”。它们事实上也对应上一节提到的两种代价为 7 的改动方案。由于没有交换的操作，无法得到 “this is changed text” 这种序列。
LCS 可以通过动态规划解决：设状态 S[i,j] 为 a.txt 前 i 行和 b.txt 前 j 行的最长公共行数，则以 a[i] 代表 a.txt 的第 i 行（从 1 计数），
S[i,0] = S[0,j] = 0,
S[i,j] = S[i-1,j-1] + 1 # If line a[i] equals line b[j]
S[i,j] = max( S[i-1, j], S[i, j-1] ) # Otherwise求解出状态表后，从表的右下角回溯到左上角，可以求出具体要删除哪些行。若向左走数字不减少则可以向左走，删除 b.txt 的对应行；若向上走数字不减少则可以向上走，删除 a.txt 的对应行；若都减少，则必然有 a[i] 行与 b[j] 行相同，此时向左上角走一步，掠过 a,b 中相同的这一行（这一行在 LCS 中）。
一旦确定 a.txt 和 b.txt 各自要删除哪些行，不难将其转换为 default output format 的 diff。
要编写 patch 程序，一种方案是创造一个指针数组，初始每个指针指向 a.txt 的每一行，按照 patch 文件的要求将这些指针指向的内容增减；最后遍历指针数组，归并结果即可。代码链接。
距离实用 diff 算法还差什么
文件末尾换行符的特殊处理
这个用 Python3 编码得到的简易 diff 和 patch 工具，首先没有对文件末尾换行符做特殊处理。例如，简易程序会给出如下的结果，并不如 shell 自带的 diff 工具清晰直观：
ln +==a.txt==+==b.txt==+===diff===+ diff (shell)
1 |title |(empty) |1d0 |1,4d0
2 | | |< title |< title
3 |content | |3d1 |<
4 |(No newl)| |< content |< content
5 | | | |\No newline at end of file换行符：LF? CR+LF?
实际的 diff 工具有时还需要面临不同系统中换行符不同（CR? LF? CR+LF?）造成的问题。这常常体现为 patch 时 “different line endings” 的报错，通常可以通过 “–binary” 选项解决。错误通常在 Windows 系统下使用 Linux 工具时出现（二者换行符不同），原因可能和具体使用的工具有关。Python3 帮我们屏蔽了这个问题：用文本模式打开文件时，会自动将所有检测到的换行符替换为 ‘\n’，这就是所谓的 universal newline translation。
降低复杂度
简易的 diff 算法在求解 LCS 的过程中，使用的是未经优化的 O(N*M) 的空间 / 时间复杂度来计算 S[i,j] 表，其中 N,M 为两个文件的长度。如果有两个区别不大但极长的文件需要 diff（如两个万行级别的文本文件，之间仅有几行的区别），那么这个算法就很低效乃至变得不可用。
对编辑次数敏感的 Myers 算法可以解决这个问题：Myers 在 Edit Graph上从左上角出发，用动态规划到达右下角的最小代价路径。这个 Edit graph 是一个网格，和S[i,j] 状态表相似，不同之处在于每个网格内并没有装填数值。Myers 算法的时间复杂度是 O((M+N)D)，其中 M, N 是文档长度，D 是输出中的编辑次数。关于这个算法的概述和演示、论文（An O(ND) Difference Algorithm and Its Variations）和有关博文链接在此。
Myers 算法分为多轮，每一轮计算代价为 D 的编辑 “最远” 能到达哪里。注意到，向下、向右走要付出代价 1，而向右下对角走要求 a[i]=b[j]，却不用付出代价。假设所有 x-y=k 的格点构成对角线 k，那不难证明代价为 D 的编辑必然落在编号为 -D, -D+2, …, D-2, D 的对角线上。更进一步，关心代价为 D、落在对角线 k 的所有可能编辑中，最远 (换言之, x 最大) 的那一个，有如下的递推方法：
- 代价为 D-1，落在对角线 k-1 的最远点向右走一格；代价为 D-1，落在对角线 k+1 的最远点向下走一格。这两者取更远者，代价达到 D。
- 因此，接着要不断尝试向右下对角走（x+1, y+1），直到无法行走。
在这个递推 / 动态规划的过程中，只需维护每一个代价的 “最远点” 数组即可。至多需要 O(D^2) 的空间。在到达 (M, N) 后，即可停止，回溯获得路径：每一步，比较 D-1, k-1 的最远点 (x+1) 和 D-1, k+1 的最远点 (y+1) 哪一个更远，它就是编辑路径上的上一步。
Myers 是 Git 默认使用的 diff 算法。注意到，Myers 仍然间是在以 “删除行+插入行” 作为基本操作和代价单位的框架之内的，它给出的 diff 也是最优的。
Git 采纳的 diff 算法概述
Git 采纳的 diff 算法除了 Myers 之外，还有 patience diff 和 histogram。后两者也在 “删除行-插入行” 的框架之内，但未必给出最优解，转而力求输出更人类可读的 diff，就不在此详述。
“移动行” 似乎很少被当作基本操作考虑，大概是因为允许这种操作的话，diff 的算法的复杂度就都要失控了。
Leave a Reply