Myers差分演演算法的理解、實現、視覺化

作者：Oto_G

QQ: 421739728

簡介

本文章對Myers差分演演算法(Myers Diff Algorithm)進行了細緻講解，適合對Myers差分演演算法完全不瞭解的小白進行學習。

• 本文所使用的Myers工具在Myers View (myer-view.vercel.app)
• 原始碼在GitHub - G-haoyu/MyerView: Myers Diff Algorithm HTML Visual Version

Myers差分演演算法或者稱為 Myers Diff Algorithm，其中的Myers是指發表該演演算法的作者；差分是英文Diff的直譯，也可以理解為差別、區別；演演算法即為Algorithm。

該演演算法解決了LCS的等價問題SES，其在git diff、DNA序列比較等場景中都被廣泛使用。

基礎

首先Myers差分演演算法所解決的問題，用不那麼嚴謹的話來說，就是解決了比較兩個字串之間的差異的問題。但就算如此，還是不夠直觀，我們先來看個例子。

差異的描述

兩個字串ABC和CBAB，找到兩個字串之間差異的問題可以具體化為：用刪減、不變、增加這三個詞描述字串ABC變化到字串CBAB的過程這樣一個具體的問題。如上圖，我列舉出了兩種從字串ABC變化到字串CBAB的方法（當然不止兩種）。

• 左邊那種的變化過程就可以描述為：增加CB，保持AB不變，刪減C

• 右邊那種的變化過程可以描述為：刪減AB，保持C不變，增加BAB

注：一定要牢記，不管是目前理解還是在Myers演演算法中，比較字串差異的過程都抽象為了字串A變化到字串B的過程，即可以理解為字串A為原字串，字串B為新字串。

比較差異的過程就是描述原字串是如何變化到新字串的過程。

為了後文方便描述，在本文中，我們將這些操作附上不同顏色：綠色表示增加、紅色表示刪減、白色表示不變。

好的差異比較

當然，通過剛剛的例子，我們也能發現，比較兩個字串的差異的結果有非常多種，那麼接下來我們就需要定義什麼是好的差異比較結果，也就是我們應該遵循什麼標準來比較差異。

我們這次使用Myers在論文中所使用的字串來進行演示，我在圖中列舉了對於從字串A變化到字串B的三種方式（當然還有許多方法），其中「比較1」是最佳的差異比較結果，即刪減AB，保持C不變，增加B，保持AB不變，刪減B保持A不變，增加C。

可以對照著圖中這三個結果在草稿紙上過一遍變化過程，我們這裡先看」比較1「和」比較2「，它們倆得出的結果非常相似，都刪減了三個字元，增加了兩個字元，同時有4個字元不變，但為什麼「比較1」更好呢，可以仔細觀察在第二個字元上，「比較1」選擇了和前一個字元同樣的操作即刪減，而「比較2」則選擇了和前一個字元不同的操作即「增加」。在直觀感受上呢，「比較1」也比「比較2」更加清晰。再看「比較1」和「比較3」，雖然感官上「比較3」比「比較1」更加直觀，但是完全失去了比較意義，所以我們依據這些優劣，確定好的差異比較的規則

• 差異應該表現為更連續的增加或者刪減

• 相同內容應該儘可能多，即差異儘可能少

• 同時約定：當刪減和增加都可選時，優先選擇刪減

注：對於第三條的約定，可以根據具體的應用場景進行修改，預設為優先刪減

演演算法介紹

在瞭解完這些後，我們終於可以進入Myers差分演演算法的學習了。

首先來看看Myers在論文中是怎麼描述自己設計的演演算法的，這段話截自《An O(ND) Difference Algorithm and Its Variations》

In this paper an O(ND) time algorithm is presented. Our algorithm is simple and based on an intuitive edit graph formalism.

翻譯為：在論文中提出了一個時間複雜度為O(ND)的演演算法，我們的演演算法很簡單，它基於一個直觀的編輯圖形式主義。

也就是Myers差分演演算法是通過構造一個名為編輯圖的東西來解決差異比較問題，同時這個解決方法的速度也很快。

名詞解釋

下面先了解下在Myers的論文中出現的一些詞的含義。圖中有介紹的名詞就不再介紹了。

• LCS

• SES

• N

• D

• k：

  • 可以理解為截距，它是通過x - y算出來的，看右邊折線圖中x軸（上方橫軸）被原字串覆蓋，y軸（左側縱軸）被新字串覆蓋，k = x - y，比如(3, 1)點所在的k = 3 - 1，即k = 2

• snake

  • 指代兩黃色端點間的線段，如(1, 0)到(2, 2)的線段就稱為一個snake

• D-path

  • 從(0, 0)出發，到達D的線路，如2-path，就表示從(0, 0)出發到(2, 4) (2, 2) (3, 1)的三條路線

• edit graph

  • 編輯圖，就是Myers演演算法的核心，其形式就是圖右的折線圖

對於k, snake, edit graph可能瞭解了是什麼，但仍然無法對應到Myers差分演演算法本身，那麼下面我們就來將這些名詞聯絡起來，首先是論文中Myers推匯出的兩個定理。

兩個定理

圖中給出了定理的理解，論文中用數學歸納法對這兩個定理進行了證明，有興趣可以閱讀原論文An O(ND) Difference Algorithm and Its Variations，這兩個定理對下文理解編輯圖繪製步驟非常重要，請理解後再向下閱讀。

繪製編輯圖

聯絡這些名詞就要通過繪製編輯圖的方式來進行。下面給出繪製編輯圖的方法。

請仔細閱讀繪製方法，可以結合下方給出的編輯圖配合理解，繪製方法並沒有給出繪製步驟，繪製步驟在兩圖片後。

瞭解完繪製方法，接下來就是最核心的繪製步驟，首先我們明確我們繪製的終止情況是到達右下角那個點，圖中即為(3, 4)點，選取它作為終點的原因在瞭解完繪製步驟後就能體會到。

繪製步驟用流程圖給出

整個繪製編輯圖的過程就是以內外兩層迴圈為主進行的，外層以差異數量的不斷增加來回圈，最終得到的差異數量即為兩字串的差異數量；內層迴圈則是在每一輪差異下對k ∈ [-d, d]這樣一個區域進行搜尋（結合定理1就實現步長為2的跳躍搜尋）。目的就是走到終點，走的策略則被設計為嚴格符合好的差異比較的標準。可以通過我設計的Myers視覺化工具Myers View (myer-view.vercel.app)來幫助理解。

理解了編輯圖的繪製過程，我想，你已經對Myers演演算法瞭解了大半了，可以進行一些「大跨步」了，我們直接來看程式碼，這裡借用簡析Myers - 小雨心情給出的JavaScript版程式碼，非常感謝，我在其程式碼之上加入了詳細的註釋，同時對程式碼進行了細微的調整，可以在TODO中看到。

function myers(stra, strb) {
    // 字串 a 的長度為 n
    let n = stra.length
    // 字串 b 的長度為 m
    let m = strb.length

    /*
    動態規劃回溯前輪計算結果用，結構為 k: x ，
    儲存的是該截距（k）目前能到達的最遠端 x ，
    且 k 滿足公式 k = x - y
    */
    let v = {
      '1': 0
    }
    /*
    儲存的是每一步差異（d）中的所有截距（k）
    能到達的最遠端 x 值，用於計算差異路徑（d-path）
    結構為 d: {k : x}
    */
    let vs = {
      '0': { '1': 0 }
    }
    // 宣告差異 d ，該值記錄兩字串差異的大小
    let d

    loop:
    // 差異d，最壞情況 n+m 即兩字串完全不同
    for (d = 0; d <= n + m; d++) {
      let tmp = {}
      /*
      斜線不計入迴圈，只有兩個方向 → || ↓
      這裡使用剪枝思想，使k不用遍歷全表
      */
      for (let k = -d; k <= d; k += 2) {
        /*
        判斷是否是通過 + 到達的待測點，+ 的情況為：
        當前截距等於負差異（首次迴圈，也就是左邊界）或者
        當前截距不等於正差異（末次迴圈，也就是上邊界）且
        上一截距的x大於下一截距的x（體現優先刪除）
        */
        let down = ((k == -d) || ((k != d) && v[k + 1] > v[k - 1]))
        /*
        如果是 + 方式到的該截距，
        則說明該截距的前一步是從上截距過來的，否則是下截距下來的
        */
        let kPrev = down ? k + 1 : k - 1
        // 獲取前一步的座標 xStart yStart
        let xStart = v[kPrev]
        let yStart = xStart - kPrev
        // 獲取可能的當前點座標，如果是 + 方式則x軸座標不變，否則橫座標加一
        let xMid = down ? xStart : xStart + 1
        // y軸通過 k = x - y 計算得出
        let yMid = xMid - k
        // 宣告當前可能的座標（還未考慮走斜線）
        let xEnd = xMid
        let yEnd = yMid

        /*
        考慮走斜線（對字串a、b進行比較，
        如果當前x、y所在字串相同則走斜線）
        */
        while(xEnd < n && yEnd < m && stra[xEnd] === strb[yEnd]) {
          xEnd++
          yEnd++
        }

        // 更新截距k所能到的最遠端xEnd，yEnd不必記錄可以計算得到
        // 動態規劃回溯子問題的實現
        v[k] = xEnd
        // 記錄當前截距的最新端點
        tmp[k] = xEnd

        /*
        如果 xEnd 和 yEnd 到達了各自字串的末端，
        說明路徑尋找到了終點，可以結束尋找
        */
        if (xEnd == n && yEnd == m) {
          // 形成完整 d - k 端點表
          vs[d] = tmp
          // 生成 diff 路徑
          let snakes = solution(vs, n, m, d)
          // 列印兩字串 diff
          printRes(snakes, stra, strb)
          // 完成 Myers diff
          break loop
        }
      }

      // 重新整理當前差異下能到達的最遠端
      vs[d] = tmp
    }
  }

  // 由後向前回溯
  function solution(vs, n, m, d) {
    // snakes存 + - 步驟
    let snakes = []
    // 存放當前搜尋的位置
    let p = { x: n, y: m }

    // 兩文字的差異數量已知，往前倒推步驟
    for (; d > 0; d--) {
      // 取出最後一步的差異所有能到達的點 v[k], k∈[-d, d]
      let v = vs[d]
      // 取出前一步的差異所有能到達的點
      let vPrev = vs[d-1]
      // 計算當前位置的截距，首次迴圈是終點所在截距k
      let k = p.x - p.y

      // 獲取當前截距的座標
      let xEnd = v[k]
      let yEnd = xEnd - k

      /*
      判斷該步是通過 + 還是 - 操作得到的，分兩類：
      1、當前截距與負差異相同
        1.1 這種情況說明當前差異除了走斜線以外，其餘都是走 + 完成的（TODO: 可優化）
      2、當前截距不等於正差異 且 前一步差異所到達的點中，
      當前截距的上側截距能到達的最遠點的x值比下策截距能到達的最遠點的x值大
        2.1 該判斷的後半部分保證了刪除先於增加的設計要求
      */
      let down = ((k == -d) || ((k != d) && (vPrev[k + 1] > vPrev[k - 1])))
      // 如果是通過 + 到達的該點，則前一步的截距在上側，即 k + 1 ，反之則 k - 1
      let kPrev = down ? k + 1 : k - 1
      // 獲得真正的前驅點（已包含走斜線情況）
      let xStart = vPrev[kPrev]
      let yStart = xStart - kPrev
      // 獲得走斜線的開始點，形象的稱為mid，（對於沒有走斜線的情況，得到的就是當前點）
      let xMid = down ? xStart : xStart + 1
      let yMid = xMid - k

      // 將當前前驅點、斜線開始點（LCS）、當前點的 x 值壓棧入 snakes
      snakes.unshift([xStart, xMid, xEnd])

      // 更新當前計算的位置
      p.x = xStart
      p.y = yStart
    }

    return snakes
  }

  function printRes(snakes, stra, strb) {
    let grayColor = '^'
    let redColor = '-'
    let greenColor = '+'
    let consoleStr = ''
    let args = []
    let yOffset = 0

    snakes.forEach((snake, index) => {
      // 獲取步驟的前驅（開始） x
      let s = snake[0]
      // 獲取步驟的LCS開始x
      let m = snake[1]
      // 獲取步驟的終點 x
      let e = snake[2]
      // LCS的起點（TODO: 可以不新增large變數，snake中記錄的m已經記錄了LCS的開始位置）
      // let large = s

      // 如果是第一個差異，並且差異的開始點不是字串頭（即兩字串在開始部分有相同子字串）
      // 只會在snakes的forEach中的一個出現
      if (index === 0 && s !== 0) {
        // 用灰色列印所有相同字元，直到s
        for (let j = 0; j < s; j++) {
          consoleStr += `%c${grayColor+stra[j]}`
          args.push(grayColor)
          // 記錄b字串的當前位置（yOffset類似遊標）
          yOffset++
        }
      }

      // 如果該子串的差異是 - 操作
      // 刪除
      if (m - s == 1) {
        // 用紅色列印刪除的字元
        consoleStr += `%c${stra[s]}`
        args.push(redColor)
        // TODO: 此處large可以省略
        // large = m
      // 如果該子串的差異是 + 操作
      // 新增
      } else {
        consoleStr += `%c${strb[yOffset]}`
        args.push(greenColor)
        // b字串當前位置繼續右移
        yOffset++
      }

      // LCS部分，當前終點位置 e 減去 LCS的開始位置，即為相同字串的長度
      // 不變
      // for (let i = 0; i < e - large; i++) {
      for (let i = 0; i < e - m; i++) {
        // TODO: 此處large可以使用m代替
        consoleStr += `%c${stra[m+i]}`
        args.push(grayColor)
        // b字串當前位置繼續右移
        yOffset++
      }
    })

    conole.log(consoleStr, ...args)
  }

  // test部分
  let s1 = 'ABCABBA'
  let s2 = 'CBABAC'
  myers(s1, s2)

讀完程式碼後應該能夠對Myers差分演演算法的實現方法有了一個系統的認識，當然其實Myers不僅僅給出了這一版本的演演算法思路，而且對它進行了優化，在這裡就不細說了，大致給一個優化思路：編輯圖的起點和終點是已知的，那麼從終點向起點繪製編輯圖是否也可行呢，那同時從起點和終點繪製編輯圖是否也可行呢？

感謝

• 簡析Myers - 小雨心情

• Git 是怎樣生成 diff 的：Myers 演演算法 - CJ Ting's Blog

• 從DiffUtil到Myers'差分演演算法 - Kevin老師不遲到

• diff-match-patch - google

• Myers, E.W. AnO(ND) difference algorithm and its variations. Algorithmica 1, 251–266 (1986). https://doi.org/10.1007/BF01840446