文本比較演算法——最小編輯距離、圖的最短路以及最長公共子序列

文本比較演算法是一個經常會被使用到的演算法。當然，大部分時間都是作為版本控制系統的命令來使用，比如 git diff。無論是提交前的差異性檢查，還是多人合作時的分支合併，git diff 都是很合適且很有用的命令。相對而言，工程上需要實現一個文本比較演算法比較少見。於個人而言，似乎只有在 14 年左右，有一個項目需要造輪子實現一個文本比較演算法的變種。不過該演算法更常出現的場景，是在面試環節，畢竟很少有人不使用 git diff / svn diff / shell diff，那麼希望面試者曾今思考過這些命令是如何實現的也就是一件自然而然的事情（當然，真沒用過就算了）。

本文對文本比較演算法進行基本介紹，引入了一個基本模型對文本比較演算法進行討論，並將結合 git diff 的具體多個演算法實現來介紹實踐中文本比較演算法。目錄結構如下

1. 文本比較演算法和最小編輯距離
2. 最小編輯距離的一個模型，圖的最短路和最長公共子序列
3. git diff 的多種演算法選擇和底層實現介紹
4. 結語

1 文本比較演算法和最小編輯距離

文本比較，如果用比較直觀簡單的話來解釋，對於兩個文本 和 ，我們希望能找出他們之間的不同，並用某種方法來衡量不同的程度。這裡的某種方法，一般是指編輯距離 ——可以使用 個動作施加在 上，將其轉換為 ，動作包括插入 （insert）和 刪除 （delete）（注 1），比如

文本 A 文本 B |------------------------------------|------------------------------------ 1|#include <iostream> |#include <iostream>2|using namespace std; |using namespace std;3| |void hello() {4|int main() { | cout << "hello world" << endl;5| cout << "hello world" << endl; |}6|} |7| |int main() {8|------------------------------------| hello();9| |} | |------------------------------------

文本 有 7 行組成，文本 有 9 行組成，使用插入和刪除可以有很多方式將 轉換成 。比如，刪除 的原本 7 行，然後插入 中的 9 行來完成轉換，編輯距離為 7 + 9 = 16

編輯序列, - 代表刪除 / + 代表插入(注意空行）-------------------------------------------|#include <iostream> -|using namespace std;-|-|int main() { -| cout << "hello world" << endl;-|}-|+|#include <iostream>+|using namespace std;+|void hello() {+| cout << "hello world" << endl;+|}+|+|int main() { +| hello();+|}------------------------------------------

事實上，任意文本都可以使用這種全刪除 + 全插入的方式來完成轉換。但是缺點顯而易見，這種方式並沒有體現出文本 和 文本 之間的差異，即使他們是一樣的。我們更傾向於使用這樣的動作序列

編輯序列, - 代表刪除 / + 代表插入(注意空行）------------------------------------------ |#include <iostream> |using namespace std;-|-|int main() { +|void hello() { | cout << "hello world" << endl; |} |+|int main() { +| hello();+|}------------------------------------------

編輯距離為 6，這也是 轉換到 的最小編輯距離。如上所見，在本文中文本的最小單元的行，即所有編輯動作全部是以行為單元。實際上，也有以詞，甚至以字母作為最小編輯單元。無論基本單元是什麼，他們的基本原理都是一致（注 2）。一般我們說文本比較演算法，是希望找出文本之間的最小差異，也就是在基本單元的基礎上求本文之間的最小編輯距離和對應的具體動作序列

2 最小編輯距離的一個模型，圖的最短路和最長公共子序列

本節引入一個模型來表示文本 和 的最小編輯距離。我們先使用一些符號來表示文本 和 的所有行，以及編輯動作序列，這裡我們繼續這個例子

文本 A 文本 B |------------------------------------|------------------------------------ 1|#include <iostream> |#include <iostream>2|using namespace std; |using namespace std;3| |void hello() {4|int main() { | cout << "hello world" << endl;5| cout << "hello world" << endl; |}6|} |7| |int main() {8|------------------------------------| hello();9| |} | |------------------------------------

文本 一共有 行，令 ，其中元素 代表 第 行；同樣文本 有 行，令 ，其中元素 代表 第 行。

對於編輯動作序列， 表示刪除 中的 ，其中 ； 在 中的 後插入 的 ，其中 ， （當 等於 0 時，代表在文本 第 1 行開始插入）。這裡的所有序號，代表任何動作未發生前，文本原本的行位置。如第一節那樣，其中一個滿足最小編輯距離的動作序列是（未必唯一，注 3）

編輯序列, - 代表刪除 / + 代表插入(注意空行，序號分別對應在 A / B 行號------------------------------------------A|B|--------------------------------------1|1| |#include <iostream> 2|2| |using namespace std;3| |-|4| |-|int main() { |3|+|void hello() {5|4| cout << "hello world" << endl;6|5|}7|6| |7|+|int main() { |8|+| hello(); |9|+|}------------------------------------------

使用上述標記表示，即

其編輯距離為 6，2 次刪除，2 次插入（其中一次同時插入 3 行 ）。同時，既然編輯動作中，無論 還是 的下標都是最初的序號，那麼這些編輯動作發生的順序無關緊要，將其作為一個集合。再將文本和編輯動作符號化後，接下來再來看一個被為『編輯圖』的『二維網格』，或者說一個『有向無環圖』

這個『二維網格』的橫坐標 ，其中 是文本 的長度；縱坐標 ，其中 是文本 的長度。對於所有 ，若沒超過邊界，都有一條垂直有向邊 和一條水平有向邊 ；若對於文本 和 存在 ，則存在一條對角有向邊 。

在上圖中，畫出了一條從 的路徑，它對應著一個滿足最小編輯距離的動作序列。其垂直段 對應 ;其中連續水平段 ， 對應 。事實上，我們可以證明從 的所有路徑和所有編輯動作序列是一一對應的。

1) 轉換 的某一路徑 到某一個編輯動作序列

設 是其順序途徑的對角有向邊結束點的排列，比如上例中這個順序排列為 。由圖中對邊的定義，只有 ，才存在一條對角有向邊 ， 對於文本 和 有 ；且除了對角有向邊，圖中只有向右和向下的有向邊，很容易發現對於 ，滿足 且 ，則 對應著文本 和 的公共子序列 （注 4），比如上列中這個公共子序列就是 。

A|B|--------------------------------------1|1| |#include <iostream> 2|2| |using namespace std;5|4| cout << "hello world" << endl;6|5|}7|6|------------------------------------------

對 的路徑 ，其在 的增長只能由對角有向邊和向下有向邊貢獻，則路徑 中必然存在邊 ，其中 且 ，對應編輯動作中的 ，其會刪除文本 中的一些行然後得到公共子序列 ;同樣，路徑 在 的增長只能由對角有向邊和向右有向邊貢獻，則路徑 中必然存在邊 ，其中 且 ，對應編輯動作中的 （同樣的 可以進行合併，比如 、 可以合併為 ），其會在合適的位置在文本 中插入一些來自文本 中行。這裡可以反向思考將其當成刪除動作，其會刪除文本 中的一些行得到公共子序列 ，這個操作反轉也就是將 擴展成 。最後轉換出的動作序列的編輯距離

2) 轉換某一個編輯動作序列 到 的某一路徑

將編輯動作集合中的動作 和 按照 下標從小到大排序，然後依次轉換，設當前坐標為 ，初始 。如果當前編輯動作是 ，則沿著對角邊前進 步，再沿向下邊前進一步，設當前坐標為 ；如果當前編輯動作是 ，則沿著對角邊前進 步，再沿向右邊前進 步，設當前坐標為 ；在遍歷轉換所有編輯動作後，如果 或 ，則繼續沿對角線前進直到 ，此時可得到一條 的路徑，且其對角邊的長度為 。轉換過程中的正確性參考 1）很容易得到，略

從上面 1）2）中不僅可以得知文本 和 的編輯動作序列可以一一對應到相應編輯圖上從 的路徑，且可以知道編輯距離 。比較直觀的，可以通過以下 3 種方式來求解最小編輯距離問題

• 直接窮舉所有 可能路徑，找出 ，漸進時間為指數級
• 和 已知，找到 即可得 ， 為文本 和 對應行的公共子序列長度。可將問題轉化為尋找最長公共子序列問題，該問題在『演算法導論』的『15.4 最長公共子序列』有一個樸素的動態規劃解法，時間複雜度為
• 從 的路徑長度為 。可以使用圖的單源最短路演算法來求解該問題，如 Dijkstra』s algorithm，在此問題中其漸進時間可以認為是 。更多圖的單源最短路演算法參考 『演算法導論』的 『第24章 單源最短路徑』

不過在實踐中，以上 3 種方法都不會被使用，更常見的演算法被稱為 Myers Diff Algorithm，它也是 git diff 的默認文本比較演算法

3 git diff 的多種演算法選擇和底層實現介紹

如果看下關於 git diff 的文檔說明，會發現 git diff 使用的文本比較演算法有 4 個選項

--diff-algorithm={patience|minimal|histogram|myers}

• myers。即 Myers Diff Algorithm，其是在第 2 節中的『編輯圖』上衍生出的演算法，時間複雜度為 ，其中 是最小編輯距離。對於差異相對較小的文本表現非常良好，且只需要 的空間，它是 git diff 的默認實現。這有兩個鏈接，一個是關於演算法的論文，一個是關於演算法的 Python 實現和計算在線演示

An O(ND) Difference Algorithm and Its Variations?

neil.fraser.name

Myers Diff Algorithm - Code & Interactive Visualization?

blog.robertelder.org

• minimal。它也是 Myers Diff Algorithm，只是 git diff 在使用默認或者 myers 選項時，出於效率的考慮，做了一些簡化。比如當有連續多個對角邊時，並滿足一個關於迭代次數的函數時，就不繼續搜索了，這樣雖然找到不一定滿足最小編輯距離的文本差異，但是表現也足夠良好。minimal 選項關閉所有的簡化，嚴格按照 Myers Diff Algorithm 搜索最小編輯距離。這裡有一個鏈接，是 git 的源碼，minial 的具體實現通過一個參數的 0 / 1 值來開關。當然也有其他 3 種的，都在 xdiff 目錄下，就是基本無注釋

git/git?

github.com

• patience。這個演算法的輸出可讀性更高，其不像 Myers Diff Algorithm 採用『編輯圖』模型，而是直接求最長公共子序列。但這個演算法一般找不到最小編輯距離，因為其在匹配最長公共子序列的時候，先過濾了一些輸入文本，只考慮在文本 和 同時出現且各自只出現一次的行，對於一個代碼文件，空行或者大括弧大概率出現多次從而被直接過濾。下面是一個例子，對比 myers 和 patience 的區別

文本 A 文本 B |------------------------------------|------------------------------------ 1|.foo1 { |.bar { 2| margin: 0; | margin: 0;3|} |}4| |5|.bar { |.foo1 { 6| margin: 0; | margin: 0;7|} | color: green;8|------------------------------------|} |------------------------------------//git diff --diff-algorithm=myers 輸出-.foo1 {+.bar { margin: 0; } -.bar {+.foo1 { margin: 0;+ color: green; }//git diff --diff-algorithm=patience 輸出-.foo1 {- margin: 0;-}- .bar { margin: 0; }++.foo1 {+ margin: 0;+ color: green;+}

• 雖然 patience 選項沒有得到最小編輯距離，但其可讀性更強，結果一目了然。另外值得一提的是，patience diff 在過濾輸入文本後，求解最長公共子序列並沒有使用『演算法導論』中描述的演算法。而是利用輸入文本出現在雙方各一次的特性，使用基於 patience sort 排序的貪心演算法，時間複雜度是 ，其中 是過濾後的文本單元個數， 是最長公共子序列長度。這有 4 個鏈接，一個關於 patience diff 的簡述，兩個是關於 patience sort 和最長公共子序列的演算法描述，一個是 patience diff 的作者關於該演算法的一些介紹

Patience Diff, a brief summary?

alfedenzo.livejournal.comPatience sort and the Longest increasing subsequence?

wordaligned.org

Longest increasing subsequence?

www.cs.princeton.edu

Patience Diff Advantages?

bramcohen.livejournal.com

• histogram。該演算法是在 patience 上進行的改進。比如在 patience 演算法，最長子序列匹配只考慮在兩個文件各出現一次的基本單元，histogram 適當的放開了這個限制。這個鏈接是指向 jgit 的，其有很詳細關於 histogram 的描述。當然，git 本身源碼也有 histogram 實現，就是缺乏注釋

src/org/eclipse/jgit/diff/HistogramDiff.java?

github.com

4 結語

這篇文章寫著寫著，越寫越多，本來是想把提及的演算法和證明過程都詳細寫出來，後來發現還是直接看論文最靠譜，於是把刪了一堆。最後只留了基本模型描述，其是最樸素的想法，很適合作為基礎知識。至於 git diff 的底層實現演算法，有興趣仔細研究下，沒興趣大概了解下即可，相關鏈接有一個在線演示，對理解 myers 演算法很有幫助。另外不得不說，patience diff 的實現非常有趣，而且實現起來也比較簡單，其內在演算法應用還挺廣泛的，有興趣可以多了解下

如有疏漏，歡迎指正

注 1：編輯動作本身可以擴展，比如增加新的動作；或者對不同動作賦予不同權值，編輯距離 ， 是不同動作的權值。一般認為

注 2：單元的不同大小，可以簡單理解成單元的值集合大小和分割符的不同。比如，如果基本單元是單字母，其取值集合為 ，分隔符為空；如果基本單元是詞，其取值集合為所有字母序列，分隔符為空格，如果加上標點，更為複雜；文中的基本單元是行，其分隔符是換行，取值集合是一行上所有可能序列；對於不同的單元大小，演算法實現對特定細節有不同實現

注 3：下面動作序列也滿足最小編輯距離

編輯序列, - 代表刪除 / + 代表插入(注意空行）------------------------------------------ |#include <iostream> |using namespace std;+|void hello() {+| cout << "hello world" << endl;+|} | |int main() { -| cout << "hello world" << endl;+| hello(); |}-|------------------------------------------

注 4：對於兩個串 和 ，其公共子序列 。其中 ，對任意 有 且