你有没有在git提交代码时，见过这样的界面？
- console.log('hello')
+ console.log('world')
那行减号代表删掉的代码，加号代表新增的代码。但你有没有想过：git是怎么知道哪行删了、哪行加了？
今天就来聊聊这背后的算法——Diff算法。
Diff是什么？
Diff（Difference，差异）算法，就是比较两个文本文件，找出它们的不同之处。
它的输出叫"补丁"（patch），格式很简单：
@@ -1,3 +1,4 @@
line 1
-line 2 old
+line 2 new
line 3
+line 4 added
@@ -1,3 +1,4 @@ 表示：旧文件从第1行开始共3行，新文件从第1行开始共4行。
减号行是旧文件有的，加号行是新文件有的。
为什么要用算法来比较？
你可能会问：直接逐行对比不就行了吗？
逐行对比的问题在于：代码变动往往不只是"替换一行"这么简单。
比如下面两个版本：
// 旧版本
function add(a, b) {
return a + b;
}
// 新版本
function sum(a, b) {
// 返回两数之和
return a + b;
}
如果你逐行对比，会认为第1行变了、第2行没变、第3行没变、第4行没变、第5行变了。
但人类会怎么看？我们会发现：核心逻辑 return a + b; 根本没有变，变的只是函数名和加了一行注释。
Diff算法要解决的就是这个问题——找到最"合理"的改动方案，而不是最简单的逐行替换。
核心思想：最长公共子序列
Diff算法最经典的实现，基于一个叫**最长公共子序列（LCS）**的算法。
什么是"子序列"？简单说，就是从原序列中按顺序取出若干元素，不需要连续。
比如这个序列：A B C D E F
A C E 就是一个子序列——按顺序取了第1、3、5个元素。
A C E 是原序列的子序列，但 A E C 不是，因为顺序乱了。
LCS就是找两个序列最长的共同子序列。
回到刚才的例子：
旧版本：function add(a, b) { return a + b; }
新版本：function sum(a, b) { // 返回两数之和 return a + b; }
它们的LCS是：function (a, b) { return a + b; }
把这个LCS挑出来之后，两边剩下的部分就是"差异"了：
- 旧版剩下
add - 新版剩下
sum和// 返回两数之和
所以Diff算法的输出就是：把 add 删掉，把 sum 和注释加进去。核心代码行标记为"不变"，这才是人类最想看到的结果。
算法是怎么算的？
LCS问题可以用动态规划来解。
想象一个表格，行是旧文件的每一行，列是新文件的每一行。每个格子记录"从这个位置往前，两个文件的最长公共子序列长度"。
填表规则很简单：
- 如果两行内容相同，格子的值 = 左上角格子的值 + 1
- 如果不同，格子的值 = 左上、左边、上边三个格子中的最大值
填完表格后，从右下角往回走，就能找到LCS的路径。
这个路径告诉你：哪些行应该标记为"不变"，哪些应该标记为"新增"或"删除"。
不过要注意，标准的LCS算法时间复杂度是O(m×n)，m和n分别是两个文件的行数。文件越大，计算越慢。
现代Diff算法的进化
git用的不是最朴素的LCS算法，而是经过优化的版本。
Myers Diff算法是git默认使用的。它在1986年由 Eugene Myers 提出，核心改进是：
- 只关注"差异"部分，跳过大量相同的行
- 用"最小编辑距离"代替LCS，计算量更小
- 对于几百行以上的文件，速度提升非常明显
可以这样理解：LCS是在全部格子中找最优路径，Myers算法则是"绕开"相同的大块区域，只盯着不一样的地方算。
另一个常见的算法是 Hunt-McIlroy算法，它是Unix最初diff命令用的，基于LCS但做了很多工程优化。
实际应用：不只是git
Diff算法的应用比你想的广泛得多：
- 代码版本管理：git diff、GitHub PR对比，全靠它
- 文档对比：Word的"比较文档"功能，原理一样
- 版本发布说明：自动生成changelog，也是diff的结果
- 配置文件变更：Kubernetes的apply命令会先diff再执行
- AI辅助编程：Cursor、Copilot展示代码改动时用的也是diff
就连你手机里的「笔记对比」功能，背后也是Diff算法在工作。
一个手算小例子
假设两个文件各只有4行：
旧：A B C D
新：A X C Y
它们的LCS是 A C（长度2）。
填表过程（简化）：
"" A X C Y
"" 0 0 0 0 0
A 0 1 1 1 1
B 0 1 1 1 1
C 0 1 1 2 2
D 0 1 1 2 2
右下角的值是2，说明LCS长度是2，即 A C。
从右下角回溯，得到三条线：
A和A匹配（不变）B在旧文件有、新文件没有 → 删除D在旧文件有、新文件没有 → 删除X在新文件有、旧文件没有 → 新增C和C匹配（不变）Y在新文件有、旧文件没有 → 新增
最终Diff输出：
A ← 不变
-B ← 删除
+X ← 新增
C ← 不变
-D ← 删除
+Y ← 新增
看，这就是git diff的工作原理——不是逐行对比，而是找到最优的"不变"部分，剩下的就是差异。
总结
Diff算法的核心就一句话：找到两个文件最长的公共部分，剩下的就是差异。
- 基础算法是LCS（最长公共子序列），用动态规划求解
- git用的是Myers优化算法，速度更快
- 它不只是git在用，代码对比、文档比较、AI编程都在用
下次当你运行 git diff 看到红绿相间的代码时，你可以想想：这一行行改动背后，是一个在表格中搜索最优路径的算法在默默工作。
理解了Diff算法，你就理解了代码对比工具的本质。下次再看git diff的输出，会不会觉得它比你想象的更聪明？