从 LCS 到 Myers Diff：Git 与代码对比工具算法演进史

一、问题概述：文本差异对比的本质与编辑距离模型

给定源文本 A（包含 N 行）与目标文本 B（包含 M 行），差异对比的目标是寻找一条将 A 转换为 B 的最少编辑指令步骤（插入与删除）。这一问题在数学上等价于寻找最长公共子序列 (LCS, Longest Common Subsequence) 或在二维网格编辑图 (Edit Graph) 中求解起点 (0,0) 到终点 (N,M) 的最短路径。

二、最小复现：Myers 算法编辑图 (Edit Graph) 最短路径构建

下面的对比展示了经典的序列对比如何映射为二维网格图搜索与编辑指令生成：

/* 源文本 A: ["A", "B", "C"]

   目标文本 B: ["A", "C", "D"] */

/* 二维编辑图网格搜索 (x 表示 A 索引, y 表示 B 索引):
   - 向右移动 (+x): 表示删除 A 中的第 x 行 (Delete)
   - 向下移动 (+y): 表示插入 B 中的第 y 行 (Insert)
   - 对角线移动 (+x, +y): 当 A[x] === B[y] 时免费对角线行走 (Keep) */

interface DiffOp {
  type: "keep" | "add" | "delete";
  value: string;
}

// 最短编辑路径: (0,0) -> 对角线(1,1) [保留 A] -> 向右(2,1) [删除 B] -> 向下/对角线(3,2) [保留 C] -> 向下(3,3) [插入 D]
const expectedDiff: DiffOp[] = [
  { type: "keep", value: "A" },
  { type: "delete", value: "B" },
  { type: "keep", value: "C" },
  { type: "add", value: "D" }
];
console.log("编辑脚本路径操作数:", expectedDiff.length);

三、根因分析：LCS 动态规划、O((N+M)D) Myers 算法与 Patience 改进

1. LCS 动态规划算法：传统 LCS 采用 O(N imes M) 空间与时间的二维矩阵填表法。面对千行级别的长文件时，内存开销呈二次方爆炸，性能无法接受。2. Myers 贪婪 Diff 算法：Eugene Myers 在 1986 年提出基于 D-path 的贪婪搜索算法，时间复杂度优化为 O((N+M)D)，空间复杂度经线段中点分割后降为 O(N+M)（其中 D 为差异编辑距离）。由于实际代码修改中 D ll N+M，Myers 算法在绝大多数场景下近乎达到线性时间！3. Patience Diff 算法：Myers 算法在面对多处重复空行或大括号时，容易产生“语意错位”（将删除/新增断在括号中间）。Patience 算法优先匹配文件里独一无二的锚点行（如唯一的函数声明），大幅提升了对比结果的人类可读性。

四、推荐方案：不同场景下的对比算法选择策略

1. 默认常规对比：使用 Myers 算法作为通用引擎（git diff 的默认算法），保障极佳的求解速度。2. 代码重构与代码评审：对包含大量大括号与函数重排的代码库开启 Patience 算法（git diff --patience）或 Histogram 算法（git diff --histogram），获得人类直觉更友好的差异快照。

五、完整代码：基于 Myers 编辑图算法的简易 TypeScript 实现

下面的 TypeScript 代码示范如何通过 Myers D-path 算法在二维网格中求解文本序列的最小编辑脚本。

interface DiffResult {

  operation: "keep" | "insert" | "delete";
  line: string;
}

function computeMyersDiff(src: string[], dst: string[]): DiffResult[] {
  const N = src.length;
  const M = dst.length;
  const maxD = N + M;
  const V: Record<number, number> = { 1: 0 };
  const trace: Record<number, number>[] = [];

  // 1. 寻找从 D = 0 到 maxD 的最短路径
  for (let D = 0; D <= maxD; D++) {
    const vCopy = { ...V };
    trace.push(vCopy);

    for (let k = -D; k <= D; k += 2) {
      let x: number;
      if (k === -D || (k !== D && V[k - 1] < V[k + 1])) {
        x = V[k + 1]; // 向下移动 (Insert)
      } else {
        x = V[k - 1] + 1; // 向右移动 (Delete)
      }

      let y = x - k;

      // 沿对角线免费滑行 (匹配相同行)
      while (x < N && y < M && src[x] === dst[y]) {
        x++;
        y++;
      }

      V[k] = x;

      if (x >= N && y >= M) {
        // 达到终点 (N, M)
        return backtrackMyersPath(trace, src, dst, N, M);
      }
    }
  }

  return [];
}

function backtrackMyersPath(
  trace: Record<number, number>[],
  src: string[],
  dst: string[],
  N: number,
  M: number
): DiffResult[] {
  const result: DiffResult[] = [];
  let x = N;
  let y = M;

  for (let D = trace.length - 1; D >= 0; D--) {
    const V = trace[D];
    const k = x - y;

    let prevK: number;
    if (k === -D || (k !== D && V[k - 1] < V[k + 1])) {
      prevK = k + 1;
    } else {
      prevK = k - 1;
    }

    const prevX = V[prevK];
    const prevY = prevX - prevK;

    while (x > prevX && y > prevY) {
      result.unshift({ operation: "keep", line: src[x - 1] });
      x--;
      y--;
    }

    if (D > 0) {
      if (x === prevX) {
        result.unshift({ operation: "insert", line: dst[y - 1] });
      } else {
        result.unshift({ operation: "delete", line: src[x - 1] });
      }
    }

    x = prevX;
    y = prevY;
  }

  return result;
}

const fileA = ["function hello() {", "  console.log('hi');", "}"];
const fileB = ["function hello() {", "  console.log('world');", "}"];
console.log("Myers Diff 计算结果:", computeMyersDiff(fileA, fileB));

六、常见错误方案

在长文本对比中误用 O(N^2) 的暴力字符串矩阵匹配；混淆文本行级别对比 (Line Diff) 与抽象语法树级别对比 (AST Diff)；盲目假设 Myers 算法在所有包含海量重复代码的边缘场景下都能输出最自然的可读分段。

七、边界条件：二阶段预处理优化 (Common Prefix/Suffix Stripping)

在执行 Myers 算法主循环前，必须先进行快速预处理：扫描并剔除两端完全相同的公共前缀 (Common Prefix) 与公共后缀 (Common Suffix)。这一步可以将算法的物理处理规模 N+M 缩减一个数量级。

八、如何评估代码对比算法的准确性与耗时

对千行级文件进行基准测试，衡量算法计算耗时与内存使用峰值；检查算法输出的 Diff 增删块是否满足 A \xrightarrow{Diff} B 的绝对转换正确性。

九、FAQ

问：为什么 Git 默认选择 Myers 算法？答：因为 Myers 算法利用编辑距离 D 的分布特性，将时间复杂度优化到了 O((N+M)D)，且在绝大多数代码提交（修改行数 D 很小）中表现出极佳的性能。

问：Patience Diff 和 Myers Diff 有什么区别？答：Myers 追求数学意义上的绝对最小编辑距离；而 Patience 优先寻找文本中唯一的锚点行，以牺牲少量路径长度为代价，换取人类阅读更加自然的差异块划分。

问：字符级 Diff 和行级 Diff 的算法是一样的吗？答：核心 Myers 算法逻辑完全一致，唯一的区别在于序列中的最小元素单位是字符 (Character) 还是行 (Line)。

十、总结

代码对比算法经历了从 LCS 动态规划到 Myers D-path 算法与 Patience 改进的演进。理解编辑图原理与预处理切割，是设计高效文本 Diff 工具的技术基石。