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 前後變化，直接把兩段內容粘到文本差異對比工具裏，顏色高亮立即呈現，省去搭環境的麻煩。