Myers 算法用于 JSON 数组 Diff 的边界与实现

一、问题概述：数组不是无序对象

当 ["a","b"] 变为 ["a","x","b"] 时，用户通常需要看到插入 x，而非把后两个索引都标成替换。Myers 的目标是构造由插入、删除和保留组成的最短编辑脚本；它不判断 JSON 对象字段本身是否相等，也不自动知道数组元素的业务身份。

二、最小复现：同一个值在不同位置代表不同序列

下面两个数组包含相同的三个字符串，但顺序改变。仅比较集合会误判为没有变化；序列 diff 必须保留位置。

const before = ["a", "b", "c"];
const after = ["a", "c", "b"];

console.log(new Set(before).size === new Set(after).size); // true
console.log(JSON.stringify(before) === JSON.stringify(after)); // false

三、根因：最短编辑脚本在编辑图中前进

将 before 和 after 放在二维编辑图的两个轴上，沿对角线前进表示元素相等，水平或垂直前进表示删除或插入。Myers 按编辑距离逐层扩展可达对角线，首次到达末端时得到最短编辑距离。替换通常表示为相邻的一次删除和一次插入，是否在展示层合并为 replace 是 patch 格式的选择。

四、推荐方案：先定义元素相等，再生成数组 patch

标量数组可以使用 Object.is。对象数组应由调用方提供稳定身份或比较函数，例如按 id 比较；对整个对象使用 JSON.stringify 会把键顺序重新带入相等判断。生成的操作应保留原值、目标值和数组路径，应用 patch 时则必须约定索引相对的是当前数组还是原始数组。

五、完整代码：生成序列编辑操作并映射到数组路径

下面的 TypeScript 是一个小型 Myers 实现，适合学习和小型数组。它返回最短编辑脚本；toArrayPatch 只演示如何给操作增加 JSON 路径，不负责在原数组上原地应用。

type Edit<T> = { kind: "equal" | "insert" | "delete"; value: T };
type ArrayPatch<T> = Edit<T> & { path: string };

function myers<T>(before: readonly T[], after: readonly T[], same: (a: T, b: T) => boolean = Object.is): Edit<T>[] {
  const max = before.length + after.length;
  const trace: Map<number, number>[] = [];
  let frontier = new Map<number, number>([[1, 0]]);

  for (let distance = 0; distance <= max; distance += 1) {
    trace.push(new Map(frontier));
    for (let diagonal = -distance; diagonal <= distance; diagonal += 2) {
      const down = frontier.get(diagonal + 1) ?? Number.NEGATIVE_INFINITY;
      const right = (frontier.get(diagonal - 1) ?? Number.NEGATIVE_INFINITY) + 1;
      let x = diagonal === -distance || (diagonal !== distance && down > right) ? down : right;
      let y = x - diagonal;
      while (x < before.length && y < after.length && same(before[x], after[y])) { x += 1; y += 1; }
      frontier.set(diagonal, x);
      if (x >= before.length && y >= after.length) {
        const edits: Edit<T>[] = [];
        let endX = before.length;
        let endY = after.length;
        for (let d = trace.length - 1; d > 0; d -= 1) {
          const previous = trace[d];
          const k = endX - endY;
          const previousK = k === -d || (k !== d && (previous.get(k - 1) ?? -1) < (previous.get(k + 1) ?? -1)) ? k + 1 : k - 1;
          const previousX = previous.get(previousK) ?? 0;
          const previousY = previousX - previousK;
          while (endX > previousX && endY > previousY) {
            endX -= 1;
            endY -= 1;
            edits.push({ kind: "equal", value: before[endX] });
          }
          if (endX === previousX) edits.push({ kind: "insert", value: after[--endY] });
          else edits.push({ kind: "delete", value: before[--endX] });
          endX = previousX;
          endY = previousY;
        }
        while (endX > 0 && endY > 0) edits.push({ kind: "equal", value: before[--endX] });
        return edits.reverse();
      }
    }
  }
  return [];
}

function toArrayPatch<T>(path: string, edits: Edit<T>[]): ArrayPatch<T>[] {
  return edits.map((edit) => ({ ...edit, path }));
}

console.log(toArrayPatch("/items", myers(["a", "b"], ["a", "x", "b"])));

六、常见错误方案

把对象递归 diff 说成 Myers 算法会掩盖两类问题：对象要比较键集合，数组才需要序列编辑。为对象数组按当前位置比较会让一次开头插入显示为大量替换；应提供稳定 id 或明确对象相等函数。把 delete 和 insert 自动展示为 replace 也可能错误，因为两个操作并不一定是一对一替换。

七、边界条件：重复值、大数组和相等函数

存在重复元素时，多个最短编辑脚本都可能成立；算法返回其中一个，不代表唯一业务解释。相等函数若只比较 id，会忽略同 id 对象内部字段的变化，应在后续对象 diff 中处理。数组很大或差异很多时需要评估内存和交互需求；本文不提供未经测量的性能阈值。

八、如何验证 patch 语义

对空数组、仅插入、仅删除、交换位置、重复值和对象 id 六类输入检查操作序列。验证时先把 equal/insert/delete 重放为目标序列，再检查路径是否始终为预期数组。若需要原地应用 patch，额外测试删除和插入的索引基准，不要直接复用展示用操作。

九、FAQ

问：Myers 能比较 JSON 对象吗？答：它比较序列；对象可先按键路径拆解，再在其中的数组节点使用 Myers。

问：replace 是 Myers 的原生操作吗？答：不是，最短编辑脚本的基本操作是插入、删除和相等；replace 是展示或协议层约定。

问：对象数组如何比较？答：优先提供稳定身份；同 id 的内容变化再交给对象字段 diff。

十、总结

Myers 为有序 JSON 数组提供最短插入/删除脚本，而不是通用对象递归算法。可靠的实现先定义元素相等，再保留操作和路径语义，并针对重复值、对象身份及索引应用规则编写验证用例。