Diff 演算法原理：電腦如何比較兩份文件
每當你在 GitHub 上查看 Pull Request 的變更、在 Word 中追蹤修訂，或是使用任何文字比對工具，背後都有一個精巧的Diff 演算法在運作。這個演算法如何在數毫秒內找出兩份文件的所有差異？讓我們一起深入了解。
什麼是 Diff？
Diff（差異比對）是一種比較兩份文本並找出差異的技術。它的目標是找出最小編輯距離（Minimum Edit Distance）— 也就是從原始文件變成新文件所需的最少操作次數（新增、刪除、修改）。
一個好的 diff 演算法不僅要找出差異，還要產生人類可讀的、直覺的差異報告。同樣的兩份文件可能有多種不同的 diff 結果，演算法的目標是找到最有意義的那一個。
最長公共子序列（LCS）
Diff 演算法的核心概念是最長公共子序列（Longest Common Subsequence, LCS）。簡單來說，LCS 就是兩份文件中相同且順序一致的最長部分。
找到 LCS 之後，不屬於 LCS 的部分就是差異所在 — 在原始文件中有但 LCS 中沒有的是「刪除」，在新文件中有但 LCS 中沒有的是「新增」。
重點摘要：LCS 是 diff 演算法的數學基礎。找到最長的公共子序列，就等於找到了最小的差異集合。
Myers Diff 演算法
1986 年，Eugene W. Myers 發表了一篇開創性的論文 "An O(ND) Difference Algorithm and Its Variations"，提出了現今最廣泛使用的 diff 演算法。
核心思想
Myers 演算法的巧妙之處在於將 diff 問題轉化為圖論中的最短路徑問題。它在一個編輯圖（Edit Graph）上搜尋從左上角到右下角的最短路徑：
- 向右移動 — 代表刪除原始文件的一行
- 向下移動 — 代表新增新文件的一行
- 對角線移動 — 代表兩個文件的行相同（不需修改）
演算法的目標是找到使用最多對角線移動（最少的新增和刪除）的路徑。
時間複雜度
Myers 演算法的時間複雜度為 O(ND)，其中 N 是兩份文件的總長度，D 是差異的數量。當差異較少時（這是最常見的情況），演算法非常高效。
| 演算法 | 時間複雜度 | 特點 |
|---|---|---|
| 暴力法 | O(2^N) | 窮舉所有可能，不實用 |
| 動態規劃 LCS | O(N*M) | 經典方法，空間消耗大 |
| Myers Diff | O(ND) | 差異少時極快 |
| Patience Diff | O(N log N) | 結果更人性化 |
Hunt-McIlroy 演算法
在 Myers 之前，Hunt 和 McIlroy 於 1976 年提出了 Unix diff 工具的原始演算法。這個演算法也基於 LCS，但使用了不同的搜尋策略。它先找出所有匹配的行，然後從中選擇最長的公共子序列。
Hunt-McIlroy 演算法的時間複雜度為 O(N log N)，其中 N 是匹配行的數量。當匹配較少時效率很高，但當匹配很多時可能不如 Myers。
Patience Diff
Patience Diff 是 Myers 的變體，使用了「耐心排序」（Patience Sorting）策略。它的特點是產生的 diff 結果對人類來說更容易閱讀。Git 允許你使用 git diff --patience 來啟用這個演算法。
Patience Diff 的核心理念是先找出兩份文件中唯一出現的行（unique lines），將這些行作為錨點，然後在錨點之間進行細粒度的比對。這樣的結果通常更符合人類的直覺。
行級 vs 字元級比對
大多數 diff 工具預設使用行級比對（line-level diff），但有時候你需要知道一行之中到底改了哪些字元。字元級比對（character-level diff）可以精確到每個字元的變化。
- 行級比對 — 適合程式碼、配置檔等結構化文本
- 字元級比對 — 適合文章、合約等需要精確追蹤的文本
- 詞級比對 — 介於兩者之間，適合自然語言文本
實際應用
Diff 演算法在現代軟體開發中無處不在：
- Git — 版本控制系統的核心功能
- Code Review — GitHub、GitLab 的 PR 差異顯示
- 文件編輯 — Word、Google Docs 的追蹤修訂
- 資料庫 — 比較 schema 變更
我們的文字比對工具就是基於這些演算法，讓你可以快速找出任何兩段文字的差異。
立即使用文字比對工具 →結語
Diff 演算法看似簡單，實則涉及深刻的計算機科學原理。從 1976 年的 Hunt-McIlroy 到 1986 年的 Myers，再到現代的各種變體，這個領域持續在演化。下次當你看到一份整齊的 diff 報告時，你會知道背後有多少巧妙的數學在運作。
參考文獻
- Myers, Eugene W. "An O(ND) Difference Algorithm and Its Variations." Algorithmica, 1(2), 1986, pp. 251-266. https://doi.org/10.1007/BF01840446
- Hunt, James W. and McIlroy, M. Douglas. "An Algorithm for Differential File Comparison." Bell Laboratories Computing Science Technical Report, No. 41, 1976.
- GNU Project. "GNU Diffutils Manual." Free Software Foundation, 2023. https://www.gnu.org/software/diffutils/manual/
- Bram Cohen. "Patience Diff Advantages." Codeville Blog, 2005. https://bramcohen.livejournal.com/73318.html