Myers Diff 那一兩件事情

Jast Lai

Published in

Jastzeonic

14 min readDec 24, 2022

前言

說來好久沒寫文章了，寫著寫著成了季更了。

我想說維持良好傳統，在聖誕夜這篇發一篇怨念文，好茲以紀念我那連續幾年散不去的怨念，但是實在想不到主題，不過這幾天又提起來 DiffUtil 的東西，我赫然發現之前有提到關於 Myers Diff 這東西，我想想，那不然我就深入來檢視檢視這套演算法吧。

不免其俗的，放首歌來給這個聖誕夜打打祭(?

說說那個 Diff

說 Myers Diff 可能大家都不知道是啥，但是只要是寫程式的人，只要有用到 Git 不是用 Zip 去做版控，可能都會在不知不覺使用這玩意。

Myers Diff 想要解決的問題很單純，就是拿兩個 Array，要把 Array1 變成Array2 。

最簡單最暴力的方法，當然是，把 Array1 全砍了，把 Array2 放上去，完美，不用燒腦。

但實務上這樣代價太大了。想像一下，你是古代一名抄書人，你抄了一本三國演義，然後發現你中間一行字把曹操寫成劉備了，不得了劉備成丞相了，這必須要修改，然後你必須要把你剛抄完的整版三國演義拋棄重抄，那代價有多大？

實務上，以上面那個抄書的例子，我們會希望可以把曹操那行字刪掉，新增劉備那行字。用這個簡單的例子我們可以知道，當我們把 array1 轉成 array2 時，我們會想要知道需要新增、刪除什麼？

這邊求簡單，我們把兩個 Array 用兩個 String 來表示，例如說我現在手上有兩個字串

string a = "abcdebef";

string b = "acfdbef";

string a 要變成 string b 要新增甚麼字元，刪除甚麼字元。單純上面的問題還蠻簡單的，把 string a 丟進一個 map 裏頭計數，然後把 string b 逐個拿去問 map 做對應的 consumed ，就可以從剩下的 map 中得到需要刪除甚麼，剩餘的 string b 字串得到需要新增的字元。

我們會需要刪除 “be” ，新增 “f”。

但問題來了，上面那個作法，新增和移除是無序的，咋知道要刪掉哪個 b 和 e，新增的 f 又該放哪啊？有此可知，我們若將 string a 轉成 string b 我們會需要符合另外一個條件：

我們需要知道新增和刪除的順序為何

因此目標變成：

找出步驟最少的新增和移除順序

那這狀況就很有趣了，因為有可能會是先刪除幾個字元再新增幾個字元會比較省步數，也有可能是先新增幾個字元再刪除幾個字元比較省步數，也有可能是新增一個字元刪除一個字元再新增一個字元再刪除一個字元比較省步數。簡而言之，用線性的思維去這樣想，會得到一個一步一步試的暴力解才求得出答案的想法，至少我一開始是這樣想的。

這樣一步一步試某些時候步是不比 string a 砍掉後再把 string b 放上去來得省事嗎？

還真是，所以暴力解在乘載著先人的智慧的情況下不是最終解決辦法。

但總之，我們先把暴力解的順序用樹把它給畫下來：

這個把樹，或者說圖(graph)實際畫下來也看不懂，那為了方便表示，我們把中間的省掉，只留下樹兩側的 node 再轉個方向，會變成這樣：

好我有點懶得寫 insert 和 remove 了，總之可以往右走是 remove，而往下走會是 insert，還有一個斜著走，意思是可以直接前往下一步，在這裡通常代表兩個字元一樣的時候。

為了方便表示，我把字元往上提一格，然後再它們底下標是一個步驟數

這些零代表甚麼都還沒做，就是個開始，那我們在來給第一步加上步驟次數，如果左邊對頂上的字元是一樣不用 +1，代表不需要異動，若是不一樣的，則需要 +1 ，代表要一次異動。

這應該不難理解，當從字串 “abcdebef” 轉換的字串是【空】的時候，要刪除 a 需要 1 個步驟，當在刪除 a 後要刪除 b 則需要 2 個步驟，以此類推。在從【空】要轉成 “acfdbef”，要插入一個 a 需要 1 個步驟，在插入一個 a 之後插入 c ，需要 2 個步驟。

再來我們來到的是 string a 和 string b 的第一個字元，string a 的字元 'a' 的字元要怎麼變成 string b 'a' 字元？很明顯，字元 'a' 要變成字元 'a' 是不需要轉換的，是故可以走斜角，直接來到這，那也因為不用異動，所以步驟數是 +0

下一步，來到了 string a 的字元 b 和 string b 的字元 a，我們若要把 ab 轉換為 a ，則需要移除 b 一步，若要把 abc 轉換為 a ，則需要移除 bc 兩步，若要把 abcd 轉換為 a ，則需要移除 bcd 三步，以此類推。

接著下一步。

到變成 ac 這一列，有趣的就來了。要從 a 變成 ac ，需要新增一個 c ，需要一步；那 ab 要變成 ac 只需要移除一個 b，然後新增一個 c ，需要兩步；那麼 abc 要變成 ac ，只需要移除一個 b ，ac 裡面已經有 c，則不需要新增 c，所以反而會比上一步 ab 變成 ac 少上一步。

依照上面的邏輯，若從 abc 要變成 acf ，則在 c 對上 f 時，他可以是移除 b、c 後再加入 c、f 後來的，也可以是加入 cf 後再刪除 bc 來的。那我們要求的是最少步驟的，所以我們要取上一步最短的步驟，有 3 步的(增加 c 和 f 後移除 b)和 1 步(移除 b)的，再加上一步(增加 f 或移除 f)，3 大於 1 ，所以我們取 1 步，那我們需要 f ，所以會增加 f ，是故 abc 變成 acf 需要兩步(移除 b ，增加 f)。

我們若要從 abcdebef 變成 acf ，那會需要五個步驟，移除 b、d、e、b、e 。

那把全部列出來 "abcdebef" 變成 "acfdbef" 需要三個步驟。移除 b、新增 f 、移除 e。

恩，那這數字怎麼來的。有經驗的人可能已經知道了，沒錯就是那個聽了摀耳、見了喊打，大名鼎鼎的 dynamic programming 動態規劃，也就是 DP，

這邊的 DP 是在這步驟取當兩個字元相同，則直接走斜的(跳過刪除或新增)，而兩個字元不同時，看是新增(往下走來的)、或者是刪除(往右走來的)，兩者取較小的。

這樣看似解決了很大一部分的問題，但是有個問題是，這的時間複雜度為 O(m*n)，空間複雜度同樣為 O(m*n)，看起來還可以，但是提到 Big O 總是會想往 O(1) 靠近。那這是否還有可能再簡化呢？

Myers Diff

恩， 1986 年的時候，Eugene Wimberly“ Gene” Myers 發表了一篇論文，標題為：An O(ND) Difference Algorithm and Its Variations ，講述了一個時間複雜度為 O(NlogN + D²) ，空間複雜度為 O(N) 的差分演算法，N 為兩個陣列數量相加的總和，D 為兩個陣列需要修改的最小值。這論文講述的東西即為後來俗稱的 Myers Diff。

Myers Diff 的核心概念是 K 線(不是股票那個)。意思是，以斜線傳過兩個陣列之間

另外還有所謂的 Snake ，也就是兩個陣列在當前這個 X Y 座標上的內容是相同的(上圖灰階部分)，在這個情況下，座標 X Y 軸可以直接各加一跳過。

延續方才 string a = “abcdebef”、string b = “acfdbef” 的例子，我們先定義一個 x 和 y ，也就是起始位置。(0,0);

int x = 0 , y = 0;

我們把 a 和 b 展開 m = a.size() ，n = b.size()

int m = a.size(), n = b.size();

那這裡會需要一個 m+n * 2 -1 的整數陣列，用來儲存移動結果，那我這邊為了方便顯示，我用 map 來紀錄：

map<int,int> v;

若要以 x 為基準，則初始化 v[+1] = 0;，若要以 y 為基準，則初始化 v[-1] = 0;

這裡以初始化 x 為準。

v[1] = 0;

此外需要一個外層迴圈，從 0 開始，至 m+n(最差情況兩個字串完全不同)：

for(int d=0 ; d<=m+n ; d++)

那這裡還會需要一個內層迴圈，用於表示 k 線，k 是從 -d 開始，那因為陣列的 index 無法用負數，所以我前面用 map 方便表示，用於儲存，一般文章表示通常會寫成 -d。

for(int k = -d ; k <= d ; k+=2)

至於迴圈為什麼每次會跳 2 待會會提到。

那當 k == -d 時，意味在內層迴圈中已經刪到沒東西，只能 insert (向下走)，反之，當 k == + d 時，意味著已經加到沒東西可以加了，只能 delete(向右走)。

//因為是以 x 為基準，所以只能 insert 時有 +1
//那沒東西可以加只能刪東西的時候，會動 Y ，所以不用 +1
if(k == -d){
  x = v[k+1];
else if(k == d){
  x = v[k-1]+1;
}

那還有一個情況是，那如果 k != d 或 k!= -d 時呢？記得 v 裡頭儲存的會是 x 座標上一步是 insert (v[k-1])或是 delete(v[k+1]) 的 x 座標，你要不從左邊來，要不就從上面來的，有 Snake 的地方下面計算會跳過。這也是之所以為何上面那個迴圈 +2 的關係，因為前後兩步都是上一步做的事情，比過了無需再比較，那我們的目標是往座標的最終點走，所以兩者看誰比較大，就選他做下一步動作。

if(v[k-1] > v[k+1]){
  x = v[k-1] + 1;
}else{
  x = v[k+1];
}

兩個判斷式合併一下會變成這樣

if(k == -d || (k != d && v[k-1] < v[k+1])){
  x = v[k+1];
}else{
  x = v[k-1]+1;
}

至於 y 我們可以利用 x 減掉 k 來計算出來

y = x-k;

那如果碰到 a[x] == b[y] 時，可以直接走 snake ，那可能會有連續的狀況，所以會用迴圈包起來，迴圈在跑可能會超過陣列長度，所以會加上長度判斷：

while(x<m && y < n && a[x] == b[y]){
  x++;
  y++;
}

最後要將走訪的 x 存入 v 中

v[k] = x;

那有可能在這一步就到達尾巴了，所以要有一個跳脫條件，當 x 和 y 真的走出了兩個陣列時，d 即為所需要的修改次數。

if(x ≥ m && y ≥ n){
  short_step = d;
  break;
}

那最後程式碼長相會是這樣

int x = 0 , y = 0;
int m = a.size(), n = b.size();
int sum = m+n;
map<int,int> v;
v[1] = 0;

int res = 0;
for(int d=0 ; d<=sum ; d++){
  for(int k = -d ; k <= d ; k+=2){
    if(k == -d || (k!= d && v[k-1] < v[k+1])){
      x = v[k+1];
    }else{
      x = v[k-1]+1;
    }

    y = x-k;

    while(x < m && y < n && a[x] == b[y]){
      x++;
      y++;
    }

    v[k] = x;
    if(x >= m && y >= n){
      res = d;
      goto end;
    }
  }
}
end:

好吧，寫到這，應該會滿滿的困惑。演算法和黑魔法基本上一個樣。

不過這邊可以看出來，推進 x 和 y 座標，主要靠的會是 snake，那若是沒有 snake ，則會依賴那個 +1 來跳脫迴圈，也就是說這個演算法的 worst case 會比用 DP 的 worst case 還要糟糕。

這情況還是挺常見的，但不是這裡要討論的東西。用 string a = “abcdebef”、string b = “acfdbef” 來跑會得到結果 :

當然陣列會大得多，不過這邊方便表示就寫這樣了。

而 d 會等於 3，代表 d 在算到第三次時，達到右下角底部，意思也就是上面那兩個字串需要三回修改。

只是這組陣列算什麼東西，我用它看不出修改的路徑為何？

有意思的地方是，我查閱大部分的資料，都從這一步開始有所分歧，畢竟每份實作的目的都不太一樣，分歧都是很合理的。但我覺得最有意思的地方是，大部分實作的演算法大概都是這形狀，包括 RecyclerView 的 DiffUtil

那我這邊的目標是把修改的路徑給印出來，只要有 (1,1) -> (1,2) -> (2,2)，便可以知道他具體是怎麼修改了。

我這邊先設計出一個結構，好方便我儲存 x 和 y 和他的上一個位置；

struct Node {
  int x;
  int y;
  Node *pre;
  Node() :  pre(nullptr) {}
  Node(int x ,int y, Node *pre) : x(x),y(y), pre(pre) {}
};

那按照剛才的邏輯，把 x 替換成 Node：

map<int,Node*> v;
v[1] = new Node(0,-1,NULL);
//y -1 是一個很單純的輔助

Node *res = NULL;
for(int d=0 ; d<=sum ; d++){
  for(int k = -d ; k <= d ; k+=2){
    Node *pre = new Node();
    if(k == -d || (k!= d && v[k-1]->x < v[k+1]->x)){
      x  = v[k+1] -> x;
      pre  = v[k+1];
    }else{
      x = v[k-1] -> x +1;
      pre  = v[k-1];
    }

    y = x - k;
                
    Node *newNode = new Node(x,y,pre);

    while(x < m && y < n && a[x] == b[y]){
      x++;
      y++;
      // 這裡會 Snack 移動的點
      newNode = new Node(x,y,newNode);
    }
    if(x > newNode -> x){
      newNode = new Node(x,y,newNode);
    }

    v[k] = newNode;
    if(x >= m && y >= n){
      res = v[k];
      goto end;
    }
  }
}
end:

那這個會是一個 LinkedList ，這可以用一點技巧反轉，我這邊先不管空間複雜度用 stack 把它反過來就行：

        stack<Node*> st;
        Node *cur = res;
        while(cur != NULL){
            st.push(cur);
            cur = cur->pre;
        }
        
        while(!st.empty()){
            cur = st.top();
            st.pop();
            cout << "(" << cur->x <<"," << cur ->y  << ")" << " -> ";
        }
        cout << "end" << "\n";

最終印出來的結果會是這樣：

(0,-1) -> (0,0) -> (1,1) -> (2,1) -> (3,2) -> (3,3) -> (4,4) -> (5,4) -> (6,5) -> (7,6) -> (8,7) -> end

結語

It just works。

上面的算法可以看出來，最糟的情況，也就是字串 a 和字串 b 完全不一樣的時候，所需要的時間複雜度會遠比 DP 來得多。但是反過來說，如果需要修改的步驟接近 0 的話，所需要的時間複雜度就會比 DP 方法來的簡易多。

之前本想說大致上看懂這東西在幹嘛了，想說可以講解講解，但實際要我講解他具體在幹什麼，還是有很大的難度在，所以其實花了不少時間在研究和實驗。

上面的 Code 我原則上都直接在 LeetCode 上跑的，手賤就用 C++ 去寫了，寫起來倒是也很好玩，我沒搞錯在一些環境下直接複製貼上應該是跑不了的。

如果有任何問題，或是看到寫錯字，請不要吝嗇對我發問或對我糾正，您的回覆和迴響會是我寫文章最大的動力。

參考資料

Myers Diff Algorithm - Code & Interactive Visualization

Below you will find example source code and interactive visualizations that are intended to complement the paper 'An…

blog.robertelder.org

https://blog.jcoglan.com/2017/02/17/the-myers-diff-algorithm-part-3/