文本差异对比算法：Myers Diff 的精妙之处
什么是文本差异对比？
文本差异对比（Diff）要解决的问题看似很简单：给你两个字符串 A 和 B，找出它们之间最小的改动步骤——哪些行删了、哪些行加了、哪些行改了。
但这个”看似简单”的问题其实暗藏玄机。我用 git diff 看了好几年代码变更，从来没想过背后是什么算法在干活。直到有一次，我写了个简单的命令行 Diff 工具对比两个 5000 行的日志文件，结果跑了将近 10 秒——那一刻我才意识到，Diff 不是”肉眼扫一遍”那么简单，算法选错了真的会慢到离谱。
Diff 到底在算什么？本质上是在求两个序列的最长公共子序列（LCS，Longest Common Subsequence）。找到了 LCS，剩下的部分就是差异。这跟你在两个版本之间找”哪些东西没变”是一个道理——变了的就是 diff 输出。
Diff 算法的工作原理
把 Diff 变成图论问题
Eugene Myers 在 1986 年发表的论文《An O(ND) Difference Algorithm》用一个极其优雅的思路重新定义了 Diff 问题，至今仍是 Git 等工具默认算法的理论基础。
他把两个字符串的对比转化成一个编辑图（Edit Graph）：画一个网格，横轴是旧文件的行，纵轴是新文件的行。从左上角出发，每一步只能向右走（表示删除旧文件的一行）、向下走（表示插入新文件的一行），或者沿对角线走（表示这一行两边相同，不需编辑）。
目标变成了：找到从左上角到右下角的最短路径。路径上的每一步非对角线移动就是一个编辑操作。这个转化妙在哪里？它把一个自然语言处理式的问题变成了一个纯粹的图搜索问题。
核心推理：走对角线和 D 值
怎么找到最短路径？朴素想法是 BFS 一层层搜，但编辑图可能非常大。Myers 的关键洞察是：设 D 为编辑次数（即非对角线步数），当 D 固定时，往 K 个对角线方向上能走到的最远距离是可以递推的。每次 D 增 1（多做一次编辑），就能沿着对角线探索更远的区域。一旦某条路径摸到了右下角，这个 D 就是最优编辑距离。
用生活里的比喻来说：就像你在一个密集的城市街区从 A 点到 B 点，有些路是斜穿公园的捷径（对角线），不用绕路。Myers 的做法就是不断尝试”多兜一个街区”能不能多走几条捷径，直到抵达终点。
算法复杂度是 O(ND)，其中 N 是总行数，D 是编辑距离。两个几乎一样的文件 D 很小，跑得飞快；但如果两个文件面目全非，D ≈ N，复杂度就退化到了 O(N^2)，这也是大文件 Diff 突然变慢的根源。
LCS：Diff 的另一面
LCS 和 Diff 是同一枚硬币的两面。两序列的 LCS 越长，意味着共同内容越多，编辑操作就越少。用公式说：编辑距离 = 总长度 - 2 × LCS 长度。实际算 LCS 的传统动态规划是 O(M×N)，Myers 的 O(ND) 在编辑距离较小的场景（比如连续改动的代码文件）性能明显更好。
我第一次手写 LCS 的 DP 解法时，用 Python 对比两个 2000 行的文件，内存直接飙到几个 G——因为 DP 矩阵是 M×N 的。后来改用 Hirschberg 的线性空间算法，内存降到了 O(N)，但速度也更慢了。空间和时间的这个跷跷板关系，在 Diff 算法里体现得淋漓尽致。
Git 的选择：Patience Diff 和 Histogram Diff
Git 早期用的是 Myers 算法，但在某些场景下结果不够直观。比如你移动了一段函数的位置，Myers 可能会把它识别为”删除一大块 + 插入一大块”，而不是”这是一个移动操作”。
Patience Diff（耐心算法）是 Bram Cohen（BitTorrent 作者）提出的改进。它的核心思想很朴素：先找出两个文件中唯一且匹配的行（在这个文件里只出现一次、在那个文件里也只出现一次、而且内容相同），以这些行为”锚点”先分段，然后递归处理段内内容。这就像拼图时先把四个角和边框找出来，里面的碎片自然就好拼了。用在代码 Diff 上，Patience Diff 更容易把函数定义行作为锚点，识别出函数移动而不是删除重写。
Histogram Diff 是 Git 当前的默认算法（从 Git 2.27 开始）。它在 Patience 的基础上做了优化：不只看”唯一匹配”，而是统计每一行在两边各出现多少次，选择出现次数最少的匹配行作为锚点。这样兼顾了 Patience 的结构可读性和 Myers 的通用效率。说实话，大部分日常 git diff 输出看起来”很合理”，背后就是 Histogram 在默默干活。
核心特性
| 特性 | 说明 |
|---|---|
| 核心问题 | 求两个序列的最短编辑脚本，等价于求 LCS |
| Myers 复杂度 | O(ND)，D 为编辑距离，相似文件接近线性，差异大时退化到 O(N²) |
| LCS DP 复杂度 | O(M×N) 时间，O(M×N) 或 O(N) 空间（Hirschberg 优化） |
| Git 默认算法 | Histogram Diff（2.27+），兼顾锚点匹配和通用效率 |
| 行级 vs 词级 | 主流工具先做行级 Diff，再在变化行内做词级 Diff（高亮具体字符） |
| 大文件性能 | 主要瓶颈在 D 值大小和总行数乘积；极端情况下秒级甚至分钟级 |
特别说一下大文件的问题。我那次被 5000 行日志对比慢到 10 秒的教训之后，才去查了代码——原来我当时用的是最朴素的 O(N²) 逐行比较，5000×5000 = 2500 万次字符串比较，每次比较还做了 trim() 和 toLowerCase()。优化后换成分片 + 哈希索引，同样的文件不到 100 毫秒就出结果。算法选型真的不是一句”都差不多”能带过的。
实际应用场景
1. 版本控制系统
这是 Diff 最主场的应用。git diff、svn diff、hg diff 全部依赖 Diff 算法来展示代码变更。每次你做 git add -p 交互式暂存时，Git 在后台跑的就是行级 Diff + 变更块切片。
2. 文档协作与合并
Google Docs 这类在线协作工具的”查看修订历史”、Word 的”比较文档”、乃至你用的任何”合并冲突解决”工具，背后都有 Diff 引擎在驱动。多人同时编辑同一段文字时，怎么合并各自的修改而不互相湮没——这本质上是三路 Diff（three-way merge）问题，比两路 Diff 又复杂了一个纬度。
3. 代码审查平台
GitHub PR、GitLab MR 的变更对比页面，不仅要做行级 Diff，还要做词级高亮——把同一行里具体改了什么字符标出来。这个”行内 Diff”通常用 Myer 或 LCS 在字符粒度上再跑一遍。
4. 增量备份
rsync 的块级同步策略本质上也是一种 Diff——把目标文件切成固定大小的块，计算每块的哈希，然后和源文件比对，只传输不一致的块。
5. 前端虚拟 DOM Diff
React 等框架的虚拟 DOM 对比也是一种 Diff 算法（O(n) 的启发式算法，而非严格的 Myers）。不过 DOM Diff 关心的是节点树的对比，和文本的行级 Diff 不完全一样，但思想同源——找最小编辑操作集。
常见误区
误区一：Diff 只是简单的行级比对
很多人（包括曾经的我）以为 Diff 就是一行行逐行 == 比较。那可太天真了。逐行比对遇到”插入了一行”的场景，后续所有行都会错位，被标记成删除+新增。真正的 Diff 要做的是找到最优匹配——哪些行是保持不变的，哪些变了。
误区二：算法不重要，结果都一样
不同的 Diff 算法输出差异可能很大，尤其是在内容大幅重组的场景下。下面是对同一组输入，三种算法可能给出的不同输出：
旧文件 新文件
A B
B C
C A
Myers 可能输出：删除 A（第一行）+ 在末尾添加 A。Patience 可能输出：识别 A 的移动 + 识别 B、C 被 C、B 替换。人眼一看就知道 Patience 的结果更容易理解。实际中，Git 曾经因为使用 Myers 导致某些合并冲突的标记极其不直观，Histogram Diff 很大程度上缓解了这个问题。
误区三：Diff 对任何大小的文件都很快
大文件 + 高修改比例 = 致命组合。前面说了 Myers 退化到 O(N²) 的条件就是 D 接近 N。如果你的旧文件和新文件几乎没有共同行，10000 行的文件跑出几秒甚至几十秒一点也不奇怪。大型 JSON 文件、自动生成的代码、日志文件都是重灾区。解决思路一般是先做轻量级预判（比如抽样哈希比对），如果确定差异过大就切换策略。
对比替代方案
| Myers Diff | Patience Diff | Histogram Diff | |
|---|---|---|---|
| 核心思路 | 编辑图最短路径 | 唯一匹配行锚点 | 低频匹配行锚点 |
| 时间复杂度 | O(ND) | O(N²) 最坏 | O(N²) 最坏 |
| 适用场景 | 连续小改动 | 代码重构、函数移动 | 通用型，Git 默认 |
| 结果可读性 | 中（有时不直观） | 高（结构感强） | 较高（兼顾） |
| 实现复杂度 | 中等 | 相对简单 | 中等 |
Git 的演化路径很说明问题：Myers（快但有时反直觉）→ Patience（git diff --patience，结构好但慢）→ Histogram（折中方案，已成为默认）。这背后反映了一个规律：对于开发者工具来说，结果的可理解性往往比理论最优解更重要。
常见问题
Q: Git 用的是什么 Diff 算法？
Git 2.27 起默认使用 Histogram Diff。你可以通过 git diff --patience 切换到 Patience 算法，或设置 diff.algorithm 为 myers、patience、histogram 三种之一。
Q: Myers Diff 的 “O(ND)” 里的 D 到底指什么？
D 就是编辑距离——从旧文件变到新文件需要的最少增删行数。两个文件越相似 D 越小，算法就快。我刚入门时老把它和 DP 里的矩阵维度搞混，其实它是结果的一部分，不是输入参数。
Q: 为什么大文件 Diff 会这么慢？
两个因素叠加：N（行数）大，加上 D（编辑距离）也大。Myers 在 D≈N 时复杂度接近 O(N²)。10000 行就是 1 亿次操作量级。而且实际工具往往还有行内字符级 Diff 和语法高亮的额外开销。所以处理大型生成文件（如 JSON 压缩成一行 + 大量修改）时，先做格式化展开、或者用 --minimal 之类的选项有时反而更慢——它在死磕一个”理论最优”的结果。
Q: 行级 Diff 和词级 Diff 是什么关系？
主流做法是两轮处理：先做行级 Diff，确定哪些行是新增、删除、或修改的；然后对每一对”修改行”做词级（或字符级）Diff，高亮出具体变化。你看到的 IDE 侧边栏变更预览、GitHub 的红色绿色高亮，都是两轮 Diff 的结果。单独只用行级 Diff 的话，你只能看到”这行变了”，却看不到变了哪个字。
Q: LCS 问题的 DP 解法为什么在实际中不常用？
经典的 O(M×N) DP 在有 10000 行时，DP 矩阵有 1 亿个元素。即使每个元素只占 8 字节，也要 800MB 内存。Hirschberg 算法把空间压到 O(N) 但时间要翻倍。Myers 算法对编辑距离小的场景又快又省空间，所以实际的 Diff 工具更倾向于 Myers 及其变体。