每个 diff 都是最短路径问题:Myers 算法与 LCS
你读过的几乎每一个 diff — git diff、GNU diff、下方的输出 — 都源自 1986 年的一篇论文:Eugene Myers 的 "An O(ND) Difference Algorithm and Its Variations"。它解决的问题是寻找最短编辑脚本(shortest edit script):把文本 A 变成文本 B 所需的最少行插入与删除次数。这在数学上等价于求最长公共子序列(LCS)— 在两段文本中以相同顺序出现(不必相邻)的最长行序列。属于 LCS 的行成为未变化的上下文,其余全部变成红色减号或绿色加号。
Myers 把两段文本建模为编辑图(edit graph):向右移动表示从 A 删除一行,向下移动表示插入 B 的一行,而在两行匹配的位置可以走免费的对角线。最短编辑脚本就是从一角到另一角的最廉价路径,算法逐次编辑地贪心探索它。O(ND) 这个名字点出了关键性质:N 是总长度,D 是差异数量,所以当两段文本相似时 — 同一文档的不同修订版,这正是最常见的情况 — 算法极快,只有当两个输入几乎毫无共同点时才会退化。
值得知道的一个细节:最短脚本通常不唯一。多个不同的 diff 可能都达到最小编辑数,你看到哪一个取决于实现内部的平局裁决。这就是为什么两个 diff 工具都"正确",却对同一对输入渲染出不同结果。
old: A B C A B B A new: C B A B A C
LCS: C A B A (longest common subsequence, length 4)
shortest edit script (D = 5 edits):
-A -B C +B A B -B A +C
del del keep ins keep keep del keep ins → C B A B A CPatience diff:最短的 diff 未必是最清晰的
最优不等于可读。Myers 最小化编辑次数,但代码里充满重复行 — 右花括号、空行、"end"、"return nil" — 在算法眼中它们是完全相同的行,于是它心安理得地把你新函数的右花括号匹配到另一个函数的右花括号上。经典症状是:在现有函数上方插入一个新函数,得到的 diff 却把两个函数的边界画在莫名其妙的位置 — 技术上最小,人类看来却是错的。
Bram Cohen 的 patience diff 用"拒绝在噪声上锚定"来解决这个问题。它先只考虑在两个文件中都恰好出现一次的行 — 函数签名、有辨识度的语句 — 对这些唯一匹配求最长递增子序列(用的正是给算法命名的纸牌游戏 patience 排序),把它们锁定为锚点,再在锚点对之间递归处理。花括号和空行因为不唯一,再也当不了假锚点。结果有时比 Myers 多几个编辑,但与人类看到的语义结构对齐。
histogram diff 是 git 对同一思想的改进,把锚定扩展到低频(不严格唯一)的行,实践中更快;它是 JGit 的默认算法,也是 git config diff.algorithm 的热门选择。下次遇到移动或重复代码的 diff 看起来一团乱时,试试 git diff --patience 或 --histogram — 同样的输入,截然不同的叙事。
# Same change, two algorithms
git diff file.py git diff --patience file.py
def totals(): def totals():
return sum(rows) return sum(rows)
+
+def averages(): +def averages():
+ return sum(rows)/n + return sum(rows)/n
+ +
def render(): def render():
# Myers may anchor on the shared 'return sum(rows)' line and
# split the new function across the old one; patience anchors
# on the unique 'def' lines and keeps each function intact.行、词、字符:选择正确的比较粒度
行级 diff 之所以是默认,一是因为代码按行变化,二是因为它便宜:先对整行做哈希,可以在昂贵算法运行之前把每个文件压缩成一个短 token 序列。但行粒度有盲区 — 在一个 300 字符的行里改一个字符,diff 会把整行报告为删除加重新添加,剩下的就靠你肉眼玩"找不同"。
代码评审工具采用的方案是两遍 diff:先做行级比较找出哪些行变了,再只对每对删除/新增的行运行字符级或词级比较,生成行内高亮。直接对整个文件做字符级 diff 很少值得 — 编辑图随输入长度平方增长,而无关行之间的单字符对齐产生的是噪声,不是洞见。git 用 git diff --word-diff(token 输出)和 --color-words(行内着色)提供词级视图,对散文、Markdown 和翻译文本 — 那里的"一行"其实是一个段落 — 极为有用。
第三个维度是结构。两个 JSON 文档可以语义完全相同而文本不同 — 键顺序、缩进、尾随逗号 — 所以对原始 JSON 做文本 diff,量出来的多半是格式。稳妥的工作流是先归一化:把两个文档过同一个格式化器(稳定键序、固定缩进)再比较。同样的技巧适用于 SQL、XML 以及被不同工具格式化过的代码;针对代码甚至有完全无视格式的 AST 级比较工具,如 difftastic。diff 的意义,取决于你在它之前做了多少归一化。
空白、换行符与其他看不见的差异
最令人困惑的 diff,是两边看起来一模一样的那种。头号嫌疑人是换行符:Windows 工具写 CRLF(\r\n),Unix 写 LF,于是在错误的操作系统上保存过一次的文件会显示每一行都变了。git 的防线是 core.autocrlf,更好的是提交一份带显式 eol 规则的 .gitattributes,让全队以同一方式归一化。在原始 diff 输出里,混入的回车常显示为行尾的 ^M。
第二类是行尾空格和 Tab 与空格缩进。有标准开关可以抑制它们:diff -b 忽略空白数量的变化,diff -w 完全忽略空白,git diff 支持 -w、-b 和 --ignore-blank-lines。这些是检查工具,不是修复手段 — 如果空白噪声污染了你的 diff,应该用格式化器和 .editorconfig 修源头,而不是永远带着 -w 比较,因为在 Python 或 YAML 里,那些"噪声"可能是真正的语义变化。
第三类是 Unicode。从网页粘贴来的不换行空格(U+00A0)、零宽空格(U+200B)、文件开头的字节序标记(U+FEFF),渲染上与普通字符毫无区别,却都会造成不匹配。类似地,一个带音符的字符可以是单个码点(NFC),也可以是基础字母加组合符号(NFD)— macOS 的文件 API 以产生 NFD 著称。当 diff 标记了一行你看不出差别的文本时,别再相信眼睛,把两行 hexdump 出来;答案永远在字节里。
# Both lines render as "hello" — the bytes disagree
$ printf 'hello \n' | xxd # trailing space: ...6f 20 0a
$ printf 'hello\r\n' | xxd # CRLF ending: ...6f 0d 0a
# Ignore whitespace while investigating
git diff -w # all whitespace
git diff -b --ignore-blank-lines # amount + blank lines
# Normalize line endings for the whole team (.gitattributes)
* text=auto
*.sh text eol=lf像母语者一样读懂 unified diff 输出
unified 格式 — 为 GNU diffutils 发明,自 git 采用后成为通用标准 — 用寥寥几个符号装载了大量信息。像 @@ -117,6 +117,8 @@ 这样的 hunk 头应这样读:这个 hunk 覆盖原文件从第 117 行起的 6 行,以及新版本从第 117 行起的 8 行。行数包含未变化的上下文行(默认上下各 3 行,可用 -U 调整)。由于被替换的行是一个减号加一个加号,新增数减删除数永远等于两个行数之差 — 手工编辑补丁时的快速检验法。
有两个标记常把人绊倒。第二个 @@ 之后的文字不是 diff 的一部分,而是包裹该处的函数名或章节标题,用来帮你定位。而 "\ No newline at end of file" 这一行不是字面内容,它标记前一行缺少末尾换行 — 这就是为什么给文件补一个结尾换行,一个字符的改动却产生两行的 diff。
理解 hunk 也揭开了打补丁的神秘面纱。patch 和 git apply 并不盲目使用行号:它们在标注位置附近搜索上下文行,文件整体偏移时带 offset 应用,上下文部分匹配时带 fuzz 应用 — 这就是针对上周文件写的补丁今天仍能打上的原因。这也是上下文在合并中重要的原因:三方合并冲突(<<<<<<< / ======= / >>>>>>>)恰恰是同一片上下文区域收到了两个不同 hunk 的情形,git 的 diff3 风格(merge.conflictStyle = diff3)会在标记之间加入共同祖先,让你看清双方各自从什么改成了什么。
@@ -117,6 +117,8 @@ function render() {
const rows = fetchRows(); ← context (3 lines above)
const total = sum(rows);
- return format(total); ← removed from old file
+ const avg = total / rows.length;
+ return format(total, avg); ← added in new file
}
// counts: old 6 = 3+1+2 ctx, new 8 = 3+2+2 ctx +1
\ No newline at end of file