Git 是怎么找出代码改动的？：diff 算法原理与 LCS 详解

你每天都在用 diff，但未必知道它怎么工作的

执行 git diff，终端里出现红色和绿色的行，精准标出哪里删了、哪里加了。Code Review 时 GitHub 把两个版本的代码并排对比，每一处改动一目了然。

这背后用的算法叫 diff，全称 difference。它要解决的问题看似简单：给定两段文本，找出最小的改动集合，让文本 A 变成文本 B。但"最小"两个字让这个问题变得很有意思。

diff 的核心：最长公共子序列（LCS）

diff 算法的核心是求两段文本的最长公共子序列（Longest Common Subsequence，LCS）。

子序列不要求连续，只要顺序一致即可。比如：

文本A：ABCDEF
文本B：ACDFGH

LCS：ACDF（长度4）

找到 LCS 的意义在于：LCS 中的行是"不需要改动的行"，剩下的就是需要增加或删除的行。改动量越少，LCS 越长——这就是"最小改动"的数学定义。

一个具体的例子

假设有两段代码：

版本A（原始）：

def greet(name):
    print("Hello")
    print(name)
    return True

版本B（修改后）：

def greet(name):
    msg = f"Hello, {name}"
    print(msg)
    return True

LCS 是：

def greet(name):
    [公共行]
    return True

因此 diff 的输出是：

  def greet(name):
-     print("Hello")
-     print(name)
+     msg = f"Hello, {name}"
+     print(msg)
  return True

- 表示删除，+ 表示新增，没有符号的行是公共行（上下文）。

Myers diff 算法：Git 背后的实现

最朴素的 LCS 算法时间复杂度是 O(n²)，对大文件性能很差。Git 实际使用的是 Myers diff 算法（由 Eugene Myers 在 1986 年提出），在实践中接近线性时间。

Myers 算法的核心思路是把 diff 问题转化成图上的最短路径问题：

把两段文本的所有行排列成一个网格
横向移动代表"删除A中的一行"
纵向移动代表"插入B中的一行"
对角线移动代表"两边的行相同，保留"
目标：从左上角走到右下角，对角线移动尽可能多（即改动尽可能少）

这个"最短编辑路径"就是最优的 diff 结果。

unified diff 格式：标准输出格式

你在终端看到的 git diff 输出，遵循 unified diff 格式，这是 1988 年由 GNU diff 定义的标准，至今仍是最通用的 diff 格式。

--- a/hello.py
+++ b/hello.py
@@ -1,4 +1,4 @@
 def greet(name):
-    print("Hello")
-    print(name)
+    msg = f"Hello, {name}"
+    print(msg)
 return True

格式说明：

--- a/hello.py：原始文件
+++ b/hello.py：新文件
@@ -1,4 +1,4 @@：hunk header，表示原文件从第1行起的4行，对应新文件从第1行起的4行
（空格开头）：上下文行，两边都有
-：只在原文件中存在（删除）
+：只在新文件中存在（新增）

逐字符 diff vs 逐行 diff

标准 diff 是逐行对比的，一行只要有任何改动就整行标红/绿。但有时候你只改了一行里的一个单词，整行高亮反而不好定位。

这就是逐字符 diff（word-level diff 或 character-level diff）的价值，GitHub 的 Code Review 界面和很多现代 diff 工具都支持在行内进一步高亮精确改动的字符。

- print("Hello, world!")
+ print("Hello, World!")
          ↑
       这一个字母大小写改了，字符级 diff 能精准标出

diff 的实际应用场景

版本控制

git diff、git diff HEAD~1、git diff branch1 branch2——这是开发者每天都在用的工具，背后全是 diff 算法。

代码审查（Code Review）

GitHub、GitLab 的 Pull Request / Merge Request 界面，用 diff 展示每次提交的改动，是现代团队协作的基础。

配置文件对比

服务器迁移或升级后，对比新旧配置文件，快速找出差异，避免遗漏。

文档版本管理

合同、文档修订时，用 diff 找出两个版本的差异，比逐字阅读高效得多。

数据库 Schema 对比

对比两个数据库的表结构，找出字段增减、类型变更等改动。

三路合并：解决冲突的原理

Git 合并分支时用的是三路合并（3-way merge）：

       Base（共同祖先）
      /                \
Branch A（你的改动）   Branch B（同事的改动）

算法分别对比 A 与 Base、B 与 Base 的 diff：

只有 A 改了的地方：采用 A 的版本
只有 B 改了的地方：采用 B 的版本
A 和 B 都改了同一地方：冲突，需要人工介入

这就是为什么 Git 冲突标记长这样：

<<<<<<< HEAD
你的代码
=======
同事的代码
>>>>>>> feature-branch

两边都改了同一行，算法无法自动决定用哪个，所以标记出来让人选择。

需要快速对比两段文本？

不管是对比两版配置文件、检查文档改动，还是核对接口返回的 JSON 前后变化，直接把两段内容粘到文本差异对比工具里，颜色高亮立即呈现，省去搭环境的麻烦。