引言
「这段代码改了什么」——git diff 只是扔出两行颜色，但背后是计算机科学一个优雅的问题：给定两个文本序列，找到差异最小的编辑方式。本文把 diff/patch 从「会用 git」讲到「懂算法」：先定义 diff 问题与最长公共子序列（LCS）的联系，再深入 Myers 差异算法（git 的默认引擎）的贪心搜索与编辑脚本，接着讲补丁格式（unified/normal）与 patch 的解析应用，再讲二进制与重命名场景、git 内部 diff 的机制（diff driver/外部 diff 工具），最后给代码审查与数据同步里的 diff 实战，以及工具链速查。
前置：/others-big-o-complexity-guide/（复杂度分析）、/text-processing-toolkit/（命令行工具）。版本控制实战见 DevOps 专题。
目录
- 1. diff 问题定义：差异最小化
- 2. LCS 与动态规划：经典解法
- 3. Myers 算法：贪心搜索编辑脚本
- 4. 补丁格式：unified 与 normal
- 5. patch 的解析与应用
- 6. 二进制与重命名 diff
- 7. git 内部的 diff 机制
- 8. diff 驱动的优化：diff driver 与相似度
- 9. 代码审查与数据同步中的 diff
- 10. 速查表与一句话记忆
- 延伸阅读
1. diff 问题定义：差异最小化
给定两个序列 A 与 B，找一条编辑路径：
A = 把 大象 装进 冰箱 需要 几步
B = 把 大象 放进 冰箱 需要 几步
编辑脚本（最小）：
删除「装」、插入「放」
→ 2 步操作，A → B
操作只有三种：删除（-）、插入（+）、保留（保持原样）。修改 = 删除 + 插入的组合。
diff 的目标：编辑脚本（含保留）的总长度最短——等价于最大化保留的公共部分，即最长公共子序列（LCS）：
diff 最小编辑距离 ⟺ |A| + |B| - 2 × |LCS(A,B)|
保留长度 = |LCS|，删除 = |A| - |LCS|，插入 = |B| - |LCS|
为什么「最短」不一定最好看：最小编辑脚本可能产生「大段删除 + 大段插入」而非「局部小改动」——人类更关心「哪里改了」，所以 git 还在最小脚本基础上做了「启发式对齐」（让改动尽量聚拢、让空白/换行尽量保留）。
心智：diff = 找最长公共子序列——删除+插入的总和最小 = 保留的公共部分最大。
2. LCS 与动态规划：经典解法
LCS 的动态规划递推：
dp[i][j] = A[1..i] 与 B[1..j] 的 LCS 长度
if A[i] == B[j]: dp[i][j] = dp[i-1][j-1] + 1
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
def lcs_len(a, b):
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[n][m]
复杂度：O(n·m) 时间、O(n·m) 空间。
工程缺陷：
- 大文件（万行级）O(n·m) 太慢 → 需要 Myers/Hunt–Szymanski 等优化
- 全 DP 矩阵空间巨大 → 可只保留两行（只求长度）；求具体子序列要回溯
从 LCS 还原 diff：DP 表回溯，匹配的字符「保留」，A 独有「删除」，B 独有「插入」。
心智：LCS 是 diff 的数学内核——DP 可解但 O(n·m)，生产引擎用更聪明的搜索。
3. Myers 算法：贪心搜索编辑脚本
Myers 算法（git 的默认 diff 引擎）：在「编辑图」上做贪心 + 广度搜索，找最短编辑路径，复杂度通常接近 O((N+M)·D)（D = 编辑距离），远好于 DP 的 O(NM)。
核心直觉：
把 A 与 B 排成一张图：
横轴 = A（向右 = 删除 A 的行）
纵轴 = B（向下 = 插入 B 的行）
对角 = A、B 相同的行（保留，不花代价）
目标：从 (0,0) 走到 (N,M)，对角走不要钱，
水平（删除）+ 垂直（插入）算代价
→ 找「最少非对角步数」的路径 = 最小编辑脚本
贪心搜索：
第 d 步：当前可到达的对角线集合
每条对角线用 k = x - y 标识
从 d-1 步的状态扩展：
- 优先从「能走对角最多」的位置继续
- 每次优先「删除」（往右）再「插入」（往下）
- 走到 (N,M) 即找到最小脚本
为什么优先删除：保证「后插入的行靠前」，让 diff 更符合人类直觉
（这也是 Myers 产生「删除块在前」的原因）
编辑脚本示例：
def myers_edit_script(a, b):
# 示意：返回 (delete | insert | keep) 操作序列
# 完整实现涉及 d 层 trace 回溯，此处展示思想骨架
pass
Myers vs LCS DP：
| 维度 | LCS DP | Myers |
|---|---|---|
| 复杂度 | O(N·M) | 约 O((N+M)·D)，差异小时极快 |
| 空间 | O(N·M) | O(N+M) 级别 |
| 输出 | 理论最小 | 最小 + 启发式更「像人」 |
| 用途 | 教学/小数据 | git/生产 |
git 的启发式加成：
- 折叠空行/空白（-w 忽略空白）
- 相似块合并（不把一块改动拆碎）
- 对标点/缩进的细粒度 diff（--word-diff）
心智：Myers 在编辑图上贪心找最短路——对角线白嫖、先删后插，差异越小跑得越快，git 用它再做启发式对齐让结果更像人。
4. 补丁格式：unified 与 normal
diff 只是「展示差异」，patch 是「可应用的差异」。常见格式：
Unified（统一）格式——最主流（git/Unix diff -u）：
--- a/foo.py 2026-09-28 10:00:00
+++ b/foo.py 2026-09-28 10:30:00
@@ -1,4 +1,5 @@
def hello():
- print("old")
+ print("new")
+ print("added")
return 0
结构：
--- 旧文件 +++ 新文件
@@ -起始,行数 +起始,行数 @@ 每个差异块的头
上下文行（前导空格）
删除行（-） 插入行（+）
Normal 格式——较老（diff 默认）：
1,2c1,2
< def hello():
< print("old")
---
> def hello():
> print("new")
补丁格式的工程意义：
- unified 是「机器可读 + 人可读」的最佳平衡
- 上下文行数决定 patch 的「容错性」（上下文越多，位置漂移也能找）
- patch 与位置无关的部分靠「模糊匹配上下文」实现
心智：unified patch = 头信息 + 块头 + 上下文/删除/插入行——上下文是 patch 的「指纹」，让应用更容错。
5. patch 的解析与应用
patch 应用的本质：在目标文件里定位每个块的位置并执行替换。
# 生成与应用
git diff > change.patch
git apply change.patch # 应用（严格）
patch -p1 < change.patch # 经典工具（更宽松）
# 反打（回滚）
git apply -R change.patch
patch 应用的三个阶段：
① 解析：把 diff 文本解析成「文件 + 块 + 行操作」
② 定位：按 @@ 头与上下文在目标文件找位置
③ 应用：执行删除/插入；全部成功才算「干净应用」
容错与冲突：
- 上下文不匹配（目标已被改）→ 该块失败
- 整文件应用 vs 逐块应用（--3way 三方合并）
- 部分块失败 → 报告「哪些块失败」，可单独手动处理
patch 的校验：
- 先 dry-run（--check / --dry-run）确认能否干净应用
- 应用到有副作用的路径前先做「预览 + 备份」
- CI 里用 git apply --check 验证补丁可落地
心智：patch 应用 = 解析 → 定位 → 替换——先 dry-run 再真打，干净应用才放心。
6. 二进制与重命名 diff
文本 diff 对二进制失效（无「行」可对），需要专门策略：
二进制 diff 策略：
1. 只看「变没变 + 大小」：纯元信息（git diff --stat）
2. 相似度对比：内容哈希/模糊指纹
3. 字节级差异：rsync 式滚动校验块（增量同步用）
4. 结构化二进制：图片/PDF 等用专门的比较工具
git 对二进制的处理：
- 默认「二进制文件」标记（不按文本 diff）
- .gitattributes 配置 diff driver：
*.png diff --binary
*.pdf diff --binary
*.docx diff=word (配置外部转换器提取文本)
- git 不存二进制 diff，只存整文件快照（用 zlib 压缩）
重命名检测（git diff -M）：
git 通过「相似度」识别重命名：
rename from / rename to 两个块
相似度阈值（默认 50%）→ 内容不变的文件算「重命名」而非「删除+新增」
场景价值：
git log --follow file 追踪重命名后的历史
重命名保留 blame 归属
文件类型混合：
一个仓库里文本（代码/配置）与二进制（资源/产物）并存：
- 文本走 diff，二进制走快照
- 大型二进制（模型/镜像）不建议进 git → 用 LFS/对象存储
心智：二进制 diff 看「变没变与相似度」而非「行差」，重命名靠相似度检测——大二进制别进 git，交给 LFS/对象存储。
7. git 内部的 diff 机制
git diff 的完整流水线：
工作区/暂存区/HEAD → 读取 blob → 逐行比较 → 输出 diff
│ │
内容来源（三个树） 差异引擎（Myers + 启发式）
git 的三层 diff：
1. 树级 diff（tree）：目录结构变化（新增/删除/重命名文件）
2. 文件级 diff：两个 blob 的差异
3. 行级 diff：差异引擎输出（Myers）
git 的 diff 优化技巧：
# 忽略空白差异
git diff -w # 忽略全部空白
git diff --ignore-space-change
# 词级/字符级 diff（代码审查更精细）
git diff --word-diff # 词级
git diff --word-diff-regex=. # 字符级（-U0 配合）
# 控制上下文
git diff -U5 # 5 行上下文
git diff --unified=0 # 只看改动行
# 只 diff 特定文件/统计
git diff --stat -- <path>
git diff --name-only
外部 diff 工具接入：
# .gitconfig
[diff]
tool = difftastic # 语法感知 diff
[difftool "difftastic"]
cmd = difft --color=always "$LOCAL" "$REMOTE"
git blame 与 diff 的配合：
blame 定位「哪次提交改了这一行」 → 结合该提交的 diff 理解改动原因
心智：git diff = 树级定位文件 → 文件级读 blob → Myers 出行级差异；审查时用 -w/–word-diff/外部工具放大细节。
8. diff 驱动的优化：diff driver 与相似度
diff driver：告诉 git「这类文件怎么比」：
.a/.b 文件 → 二进制
.docx/.pdf → 先提取文本再 diff（external driver）
minified js → 先格式化再 diff（美化后对比）
# .gitattributes
*.docx diff=word
*.min.js diff=js-min
# .gitconfig 配置 driver 命令
[diff "word"]
textconv = pandoc -t plain # 转纯文本再 diff
[diff "js-min"]
textconv = js-beautify # 美化后 diff
相似度阈值（rename detection）：
git diff -M50% # 相似度 ≥50% 视为重命名
git diff -M --no-renames # 关闭重命名检测
git log --follow -- <file> # 跟随重命名追历史
diff 与性能：
- 巨型文件 diff 慢 → 拆分/忽略生成物
- 频繁 diff 的仓库 → 用 git diff --stat 先看规模
- 大仓库 diff 的「单词高亮」有开销 → 按需用
心智：diff driver 让 git 会比「你关心的内容」，textconv 提取可读文本、相似度阈值识别重命名——把工具的力气花在刀刃上。
9. 代码审查与数据同步中的 diff
代码审查：diff 是沟通的语言。
好 diff 的特征：
- 小而聚焦（一次审查 < 400 行，review 质量高）
- 命名与结构改动分离（重构与功能分开提交）
- 有测试、有说明（diff 之外的上下文）
坏 diff 的代价：
- 大而混杂 → 审查者放弃细看 → 风险流入主干
审查时的 diff 技巧：
- 先看文件清单（--stat），定位重点
- 忽略格式化噪音（-w），聚焦逻辑改动
- 按提交逐个 diff（git show <sha>），理解演进
- 结合 blame 与上下文文件，理解「为什么」
数据同步：diff 是「最小变更」的数学。
- 配置同步：新旧配置 diff → 只下发变化的字段
- 数据库迁移：schema diff（工具生成迁移 SQL）
- 文档/翻译同步：diff 定位未同步段落
- 远程增量：rsync 用滚动校验 diff 传输最小字节
diff 在审计与合规：
- 变更审计：每次发布 = 一份可回放 diff
- 合规追溯：谁在何时改了哪行 → git log + blame
- 事故复盘：diff 定位「引入问题的提交」（git bisect 辅助）
心智：diff 在审查里是沟通语言（小而聚焦）、在同步里是最小变更的数学、在审计里是可回放的证据链——同一个算法，三个战场。
10. 速查表与一句话记忆
全篇速查：
| 主题 | 结论 |
|---|---|
| 问题 | diff = 找最小编辑脚本 = LCS |
| LCS DP | O(N·M)，适合教学/小数据 |
| Myers | 编辑图贪心，git 默认，近 O((N+M)·D) |
| 补丁 | unified 为主，上下文做指纹 |
| 应用 | 解析→定位→替换，先 dry-run |
| 二进制 | 看变没变/相似度，大文件用 LFS |
| 重命名 | 相似度阈值 -M 检测 |
| git 内部 | 树→文件→行，-w/–word-diff 放大 |
| driver | textconv 提取文本再比 |
| 场景 | 审查小而聚焦、同步最小变更、审计可回放 |
一句话记忆：diff 的数学是「找最长公共子序列」，Myers 在编辑图上贪心找最短路径让 git 又快又像人；unified 补丁靠上下文做指纹、先 dry-run 再应用；二进制看相似度、重命名靠 -M 阈值、二进制大文件走 LFS；审查讲究小而聚焦、同步追求最小变更、审计留下可回放证据——同一个差异算法，驱动着代码协作的每一天。
延伸阅读
- /others-big-o-complexity-guide/ — 差异算法与编辑距离的复杂度分析
- /text-processing-toolkit/ — 命令行 diff 工具与文本处理
- /others-fuzzy-text-matching/ — 编辑距离（Levenshtein）与相似度度量
- /others-data-compression-guide/ — 差异传输与增量压缩
- DevOps 专题 — Git 工作流与 CI/CD 实践
- 数据库专题 — Schema 迁移与数据同步的 diff 应用
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。