最近使用在线json对比工具的时候，对于这种对比的实现方式产生了好奇，我用脚指头想也知道这功能实现起来肯定不简单，于是小小地研究了一下

本文三种实现方式的可运行代码放这里了

<div id="input-box">
  <div class="input-item">
    <span>原字符：</span>
    <input type="text" name="src" autocomplete="off" />
    <span>目标字符：</span>
    <input type="text" name="dst" autocomplete="off" />
    <button onclick="diffByInput(this)">查看Diff</button>
  </div>
</div>
<div class="tip">
    <span class="red-tip">红色</span>代表删除，<span class="blue-tip">绿色</span>代表增加，<span class="black-tip">黑色</span>代表保持不变
  </div>
  <div id="min-distance-box">
    <h3>最短编辑距离</h4>
  </div>
  <div id="longest-common-subsequence-box">
    <h3>最长公共子序列</h4>
  </div>
  <div id="myers-box">
    <h3>Myers</h4>
  </div>

最短编辑距离

逐字符的对比和多行文本的对比，差别无非是最小单元的不同，所以先从字符对比说起

我首先就想到了最短编辑距离这个算法，虽然这个算法并没有直接给出一个字符串变成另一个字符串的具体过程，但既然它能得到这个过程的最短编辑距离，很显然，肯定也能拿到这个过程

最短编辑距离的教科书解法是动态规划，关于这个解法本文就不详细说了网上到处都是，核心是用一个数组来存细分粒度的编辑距离，这个数组最好是一个一维数组，但这里为了记录下具体的编辑过程，所以需要用二维数组

首先我们还是按照解决最短编辑距离的方法来写代码

function minDistance(word1: string, word2: string) {
  const m = word1.length
  const n = word2.length
  const dp = Array.from({ length: m + 1 }, () => Array.from({ length: n + 1 }, () => 0))
  for (let i = 1; i <= m; i++) {
    dp[i][0] = i
  }
  for (let i = 1; i <= n; i++) {
    dp[0][i] = i
  }
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]
      } else {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
      }
    }
  }
  console.log(dp)
}

对于 minDistance('horse', 'ros') 这个调用来说，dp的值格式化如下：

[
  [0, 1, 2, 3]
  [1, 1, 2, 3]
  [2, 2, 1, 2]
  [3, 2, 2, 2]
  [4, 3, 3, 2]
  [5, 4, 4, 3]
]

dp[5][3]的值就是最短编辑距离，数组中的其他值是转移过程产生的值，只需要回溯遍历这个转移过程，就可以还原字符串最短编辑的操作过程

要将一个字符串变成另一个字符串，需要经过三种操作方式，分别是删除、增加、保持不变，最短编辑距离的算法没有 保持不变 这个概念，但有个概念叫替换，其实就是 删除+增加

例如，dp[1][1]代表的是字符串 h 编辑为字符串 r 的最短编辑距离 1，那么就可以根据这个值及其周围值的情况来判断经过了什么操作，才使得 h 变成 r 的。dp[1][0] === dp[1][1]，说明这一步操作肯定不是增加；dp[0][1] === dp[1][1]，说这一步操作也不是删除；dp[0][0] !== dp[1][1]，说明肯定有操作，那么就不是保持不变啥也没做；既然不是上述三种操作，那么就只剩下 替换 了。所以我们可以得出从 h 编辑成 r 的操作是 替换

依次遍历 dp，执行上述判断逻辑，即可得到整个字符串的编辑过程

enum EMOpType {
  /** 后面追加 */
  Append,
  /** 删除 */
  Delete,
  /** 保持不变 */
  Hold
}
function minDistance(word1: string, word2: string) {
  // ...
  console.log(dp)
  const ops: { type: EMOpType; index: number, otherIndex?: number }[] = []
  let i = m
  let j = n
  while (i >= 0 || j >= 0) {
    if (j && dp[i][j] === dp[i][j - 1] + 1) {
      ops.push({ type: EMOpType.Append, index: j - 1 })
      j--
    } else if (i && dp[i][j] === dp[i - 1][j] + 1) {
      ops.push({ type: EMOpType.Delete, index: i - 1 })
      i--
    } else if (i && j && dp[i][j] === dp[i - 1][j - 1] + 1) {
      ops.push({ type: EMOpType.Delete, index: i - 1 })
      ops.push({ type: EMOpType.Append, index: j - 1 })
      i--
      j--
    } else if (i && j && dp[i][j] === dp[i - 1][j - 1]) {
      ops.push({ type: EMOpType.Hold, index: i - 1 })
      i--
      j--
    } else {
      i--
      j--
    }
  }
}

可视化如下（绿色背景表示是增加的字符，红色背景表示是删除的字符，黑色表示保持不变的字符）

最长公共子序列

最长公共子序列同样也可以提取出具体的求解过程

先上教科书式的解法，同样是借助一个二维数组

function longestCommonSubsequence(word1: string, word2: string) {
  const len1 = word1.length
  const len2 = word2.length
  const dp = Array.from({ length: len1 + 1 }, () => Array.from({ length: len2 + 1 }, () => 0))
  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
      }
    }
  }
  console.log(dp)
}

一个字符串转成另外一个字符串，最简单的方式就是把原字符串全部删除，然后换上目标字符串即可，但这么做未免会存在很多不必要的操作，如果找出两个字符串的最长公共子序列，那么属于最长公共子序列的字符串一律不动，对原字符串剩下的字符串再经过一系列操作变成目标字符串，这样代价就会小很多了

对于 longestCommonSubsequence('horse', 'ros')这个调用来说， dp 值如下

[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 1, 1]
[0, 1, 1, 1]
[0, 1, 1, 2]
[0, 1, 1, 2]

因为只有回溯才能知道上一步是怎么过来的，所以还是从对 dp从内向外回溯

dp[len1][len2] 的值是 2(定义为 current)，由于 dp 存储的是状态转移过程，所以这个 2 肯定是从上一步转移过来的，也就是从 dp[len1 - 1][len2 - 1](定义为 leftTop)、dp[len1][len2 - 1](定义为 left)、dp[len1 - 1][len2](定义为 top) 这三个状态转移来的

根据 dp的计算过程，我们可以确定，current的值要么是 leftTop + 1得来的，要么等于top、left中的最大值。

如果current的上一步是 leftTop，那么必须满足 word1[len1 - 1] === word2[len2 - 1]，但是显然不满足；如果是 left转移来的，那么必须满足 left !== current 且 left === 2，这里不满足；如果是 top转移来的，那么必须满足 top !== current 且 top === 2，满足，所以可以认定 current 是从 top 得来的，也就是 current的上一步是 top，映射到原字符串，也就是 horse -> ros的上一步是 hors -> ros，原字符串少了一个字符串 e，那么可以确定这一步回溯是原字符串的删除字符操作

现在继续设定 current = top = dp[len1 - 1][len2]，leftTop = dp[len1 - 2][len2 - 1]，left = dp[len1 - 1][len2 - 1]，按照上面的流程继续推演，直到推演到 [0,0] 这个坐标，再回过头来把这个过程倒序，就是正确的字符串编辑过程了

回溯编辑过程如下：

type TBackTrace = { type: EOpType; index: number; str: string }

function backTraceLSC(dp: number[][], word1: string, word2: string) {
  const ses: TBackTrace[] = []
  let dpXIndex = dp.length - 1
  let dpYIndex = dp[0].length - 1
  let top = -1
  let left = -1
  let topLeft = -1
  let current = -1
  while (dpXIndex !== 0 || dpYIndex !== 0) {
    if (dpXIndex === 0) {
      // 只能向左，增加
      ses.push({ type: EOpType.InsertBefore, index: dpYIndex - 1, str: word2[dpYIndex - 1] })
      dpYIndex--
      continue
    }
    if (dpYIndex === 0) {
      // 只能向上，删除
      ses.push({ type: EOpType.Delete, index: dpXIndex - 1, str: word1[dpXIndex - 1] })
      dpXIndex--
      continue
    }
    top = dp[dpXIndex - 1][dpYIndex]
    left = dp[dpXIndex][dpYIndex - 1]
    topLeft = dp[dpXIndex - 1][dpYIndex - 1]
    current = dp[dpXIndex][dpYIndex]
    if (top === left && top === topLeft && current - 1 === topLeft) {
      ses.push({ type: EOpType.Hold, index: dpXIndex - 1, str: word1[dpXIndex - 1] })
      dpXIndex--
      dpYIndex--
      continue
    }
    if (left == current) {
      ses.push({ type: EOpType.InsertBefore, index: dpYIndex, str: word2[dpYIndex - 1] })
      dpYIndex--
      continue
    }
    if (top === current) {
      ses.push({ type: EOpType.Delete, index: dpXIndex - 1, str: word1[dpXIndex - 1] })
      dpXIndex--
      continue
    }
  }
  return ses.reverse()
}

可视化如下（绿色背景表示是增加的字符，红色背景表示是删除的字符，黑色表示保持不变的字符）

可以看到，对相同的两个字符串 horse -> ros 之间的编辑过程进行回溯，这种方式与第一种方式都用了相同的编辑距离，但却给出了两种不同的编辑方式，这表明两个字符串之间的编辑过程依据算法的不同是可以有多种的

Myers 算法

上面的两种方式虽然也能给出简单字符串的编辑过程，但很明显是有缺陷的，无论是最短编辑距离还是最长公共子序列，它们原本的目的都不是为了呈现编辑过程，编辑过程只是这两个算法在计算过程中的副产品，而且为了得到这个副产品，算法都没有使用最优解，也就是它们的时间复杂度和空间复杂度都非常大，在实际场景中是不可用的，由此引出了 Myers 算法

此算法除了在复杂度上有更好的表现外，还具备路径最短和 diff 直观 两个优点，关于这个算法的基本原理我就不在此重复了，这篇文章 已经说得很详细了，我这里参照此文的 go 版本，给出 ts 版本

enum Operation {
	INSERT = 1,
	DELETE = 2,
	MOVE = 3
}
function reverse(s: Operation[]) {
  const result: Operation[] = []
  const len = s.length
  for (let index = 0; index < s.length; index++) {
    result[len - 1 - index] = s[index]
  }
  return result
}
function shortestEditScript(src: string, dst: string) {
  const n = src.length
  const m = dst.length
  const max = n + m
  const trace: Record<number, number>[] = []
  let x: number
  let y: number
  let isDone = false

  for (let d = 0; d <= max; d++) {
    // 最多只有 d+1 个 k
    const v: Record<number, number> = {}
    trace.push(v)
    if (d === 0) {
      let t = 0
      while (n > t && m > t && src[t] === dst[t]) {
        t++
      }
      v[0] = t
      if (t === n && t === m) {
        break
      }
      continue
    }
    const lastV = trace[d - 1]
    for (let k = -d; k <= d; k += 2) {
      // 向下
      if (k === -d || (k !== d && (lastV?.[k-1] || 0) < (lastV?.[k + 1] || 0))) {
        x = lastV?.[k + 1] || 0
      } else {
        // 向右
        x = (lastV?.[k - 1] || 0) + 1
      }

      y = x - k

      // 处理对角线
      while (x < n && y < m && src[x] === dst[y]) {
        x++
        y++
      }
      v[k] = x
      if (x === n && y === m) {
        isDone = true
        break
      }
    }
    if (isDone) break
  }

  // 反向回溯
  const script: Operation[] = []
  x = n
  y = m
  let k: number
  let prevK: number
  let prevX: number
  let prevY: number

  for (let d = trace.length - 1; d > 0; d--) {
    k = x - y
    const lastV = trace[d - 1]
    if (k === -d || (k !== -d && lastV[k - 1] < lastV[k + 1])) {
      prevK = k + 1
    } else {
      prevK = k - 1
    }

    prevX = lastV[prevK]
    prevY = prevX - prevK

    while(x > prevX && y > prevY) {
      script.push(Operation.MOVE)
      x--
      y--
    }

    if (x === prevX) {
      script.push(Operation.INSERT)
    } else {
      script.push(Operation.DELETE)
    }

    x = prevX
    y = prevY
  }

  if (trace[0][0] !== 0) {
    for (let i = 0; i < trace[0][0]; i++) {
      script.push(Operation.MOVE)
    }
  }
  return reverse(script)
}

可视化如下（绿色背景表示是增加的字符，红色背景表示是删除的字符，黑色表示保持不变的字符）

小结

本文只是简单探索了一下 diff 的基本原理，想要应用到实际场景肯定还需要大量的工作，很多开源的编辑器，例如 monaco-editor，codemirror 等都自带了 diff 能力，实际场景最好还是借助这些成熟的开源库

原文链接：https://juejin.cn/post/7282752001900707874