← 全部文章
更新于 May 29, 20269 min read

如何比较两份 JSON 文件:算法与工具

纯文本 diff 会漏掉键重排序与空白噪声。学习真正的 JSON diff 怎么工作:LCS 行 diff、语义树比较、键规范化,以及各方案的取舍。

两份 JSON 响应看着几乎一样，但发版之间有什么变了，你的测试就开始失败。或者你正在 review 一个改动了大配置文件的 PR，需要知道究竟哪些值变了。比较 JSON 文件听上去简单 —— 直到你发现朴素的文本 diff 会把键顺序变化也当成改动，深度嵌套的结构需要更聪明的方法。这篇文章解释让 JSON diff 真正可用的那些算法。

为什么纯文本 diff 不够

比较两个文件最简单的方法是跑 diff 或者一行一行比对。对纯文本这工作得很好。对 JSON 至少在两个地方崩掉。

问题 1：键顺序

按规范，JSON 对象是无序的。下面两份文档在语义上完全一样：

// 文档 A
{ "name": "Ada", "plan": "pro", "active": true }

// 文档 B
{ "active": true, "name": "Ada", "plan": "pro" }

逐行文本 diff 会把每一行都报成改动。真正的 JSON diff 会报告零差异。

问题 2：格式化噪声

缩进、空白，以及一个长数组到底是写在一行还是多行，对数据本身都无关。文本 diff 会把每个空白差别都当成改动。

两个问题的解决办法是同一个：先解析，再 diff 结构，而不是 diff 文本。

第一步 —— 解析并归一化

做任何比较之前，先用 JSON.parse() 把两份文档解析成 JavaScript 对象，再用排序后的键和统一缩进重新序列化：

function normalise(json) {
  const value = JSON.parse(json);
  return JSON.stringify(sortKeys(value), null, 2);
}

function sortKeys(value) {
  if (Array.isArray(value)) return value.map(sortKeys);
  if (value !== null && typeof value === 'object') {
    return Object.keys(value)
      .sort((a, b) => a.localeCompare(b))
      .reduce((acc, key) => {
        acc[key] = sortKeys(value[key]);
        return acc;
      }, {});
  }
  return value;
}

归一化之后，上面文档 A 和 B 都会产生同一串文本：

{
  "active": true,
  "name": "Ada",
  "plan": "pro"
}

现在对这两段归一化后的字符串做文本 diff，只会高亮真正的数据差异，不会带上格式或键顺序的噪声。

第二步 —— 用 LCS 做行级 diff

归一化后，问题就变成：给定两段行序列，找出把一个变成另一个所需的最小改动集合（插入和删除）。这是经典的最长公共子序列（LCS）问题。

什么是 LCS？

两段序列的 LCS，是同时出现在两边、顺序相同、但不一定连续的最长子序列。比如：

Before: ["  active: true", "  name: Ada",   "  plan: pro" ]
After:  ["  active: true", "  name: Ada",   "  plan: team"]

LCS:    ["  active: true", "  name: Ada"]   // 共有 2 行

// 结果：
//   same:    "  active: true"
//   same:    "  name: Ada"
//   deleted: "  plan: pro"
//   added:   "  plan: team"

LCS 正好给了我们想要的 diff：保留不变的行、被删除的行、被添加的行。

DP 算法

LCS 用动态规划求解。对长度为 m 和 n 的两个数组，我们建一个二维表，让 dp[i][j] 表示「前数组前 i 个元素」和「后数组前 j 个元素」的 LCS 长度：

// 自底向上填 DP 表
for (let i = m - 1; i >= 0; i--) {
  for (let j = n - 1; j >= 0; j--) {
    dp[i][j] = before[i] === after[j]
      ? dp[i + 1][j + 1] + 1                    // 行相同
      : Math.max(dp[i + 1][j], dp[i][j + 1]);   // 取更优的分支
  }
}

// 沿着表回溯，还原 diff 操作
let i = 0, j = 0;
while (i < m && j < n) {
  if (before[i] === after[j]) {
    ops.push({ type: 'same', line: before[i++] }); j++;
  } else if (dp[i + 1][j] >= dp[i][j + 1]) {
    ops.push({ type: 'del', line: before[i++] });
  } else {
    ops.push({ type: 'add', line: after[j++] });
  }
}

时间复杂度：O(m × n)。空间复杂度：O(m × n)。对一般 JSON 文档够快。对超大文档（比如各 2000 行以上），这张表会吃掉不少内存 —— 到那个量级就值得换 Myers diff 算法，它的时间复杂度是 O(n + d²)，其中 d 是差异的数量。

内存优化：类型化数组

普通 JavaScript 二维数字数组每个元素都有不小的开销。改成一维 Int32Array 大致能省 8 倍内存，对缓存也更友好：

const W  = n + 1;
const dp = new Int32Array((m + 1) * W); // 一维 buffer

// 访问 dp[i][j] 写成 dp[i * W + j]
dp[i * W + j] = before[i] === after[j]
  ? dp[(i + 1) * W + (j + 1)] + 1
  : Math.max(dp[(i + 1) * W + j], dp[i * W + (j + 1)]);

对一个 500 行的文档，这能把这张表从 ~2 MB 的堆对象降到 ~1 MB 的连续类型化内存。

第三步 —— 把相邻改动配成「修改」行

原始的 LCS 输出只知道删除和添加。但在并排 diff 视图里，把一个删除行和替代它的添加行配在一起显示成「修改」行，看起来好多了：

// LCS 给出的原始操作：
del  "  plan: pro"
add  "  plan: team"

// 配对之后：
modified  left: "  plan: pro"   right: "  plan: team"

配对算法把连续的 del 和 add 操作块收集起来，对位拉链。没配上的删除右侧留空占位；没配上的添加左侧留空占位：

// 收集连续的 del/add 块
const dels = [], adds = [];
while (ops[i].type !== 'same') {
  if (ops[i].type === 'del') dels.push(ops[i].line);
  else                        adds.push(ops[i].line);
  i++;
}

// 拉链配对成 modified
const pairs = Math.min(dels.length, adds.length);
for (let k = 0; k < pairs; k++)
  rows.push({ type: 'modified', left: dels[k], right: adds[k] });

// 剩下没配对的删除
for (let k = pairs; k < dels.length; k++)
  rows.push({ type: 'deleted', left: dels[k] });

// 剩下没配对的添加
for (let k = pairs; k < adds.length; k++)
  rows.push({ type: 'added', right: adds[k] });

第四步 —— 用于汇总计数的语义 diff

行 diff 告诉你什么文本变了。语义 diff 告诉你哪些字段变了、怎么变 —— 这对「新增 3 个，删除 1 个，修改 2 个」这种摘要很有用。

语义 diff 递归地同时走两边解析后的对象：

function diffValue(key, path, before, after) {
  if (before === undefined) return { status: 'added',   after  };
  if (after  === undefined) return { status: 'removed', before };

  if (isObject(before) && isObject(after)) {
    const keys     = union(Object.keys(before), Object.keys(after)).sort();
    const children = keys.map(k =>
      diffValue(k, path + '.' + k, before[k], after[k])
    );
    return {
      status: children.every(c => c.status === 'unchanged') ? 'unchanged' : 'changed',
      children,
    };
  }

  if (Array.isArray(before) && Array.isArray(after)) {
    const len      = Math.max(before.length, after.length);
    const children = Array.from({ length: len }, (_, i) =>
      diffValue(i, path + '[' + i + ']', before[i], after[i])
    );
    return {
      status: children.every(c => c.status === 'unchanged') ? 'unchanged' : 'changed',
      children,
    };
  }

  return deepEqual(before, after)
    ? { status: 'unchanged', before, after }
    : { status: 'changed',   before, after };
}

走一遍生成的这棵树，按状态数叶子节点，就拿到了汇总数字。和行 diff 不同，语义 diff 天生就和键顺序无关 —— 它比较的是同一键路径下的值，不管它们在 JSON 里出现的顺序。

拼到一起

完整的 JSON diff 工具把这些步骤串起来：

function jsonDiff(leftText, rightText) {
  // 1. 解析
  const leftVal  = JSON.parse(leftText);
  const rightVal = JSON.parse(rightText);

  // 2. 语义 diff → 汇总计数
  const summary = summarise(diffValue('root', '
#x27;, leftVal, rightVal));

  // 3. 归一化（排序键、统一缩进）
  const leftNorm  = JSON.stringify(sortKeys(leftVal),  null, 2);
  const rightNorm = JSON.stringify(sortKeys(rightVal), null, 2);

  // 4. LCS 行 diff
  const rows = buildLineDiff(leftNorm, rightNorm);

  return { summary, rows };
}

Deep-Equal 与结构化 diff

一个常见的偷懒办法是用 deepEqual 来比较两份 JSON（Node 的 assert.deepStrictEqual、Lodash 的 isEqual）—— 快，但只给一个布尔。它告诉你两份文档确实不一样；它不会告诉你在哪里、怎么不一样。

结构化 diff会走完两棵树，产出一份报告（计数、路径、前后值），还可以可选地给出一个 JSON Patch。要 yes/no 答案的时候用 deepEqual —— 比如测试、缓存失效。要让人来根据差异行动时，用结构化 diff。

从 diff 生成 JSON Patch

有了语义 diff 树以后，统计新增/删除/修改节点的同一次遍历可以顺手发出一个 JSON Patch（RFC 6902）—— 一份可移植的 add / remove / replace 操作列表，把「之前」的文档变成「之后」的。这就是怎么把 diff 当作 HTTP PATCH 请求的 body 发出去，或者稍后到别的地方再应用。

function toJsonPatch(node, pointer = '') {
  const ops = [];
  if (node.status === 'added')   ops.push({ op: 'add',     path: pointer, value: node.after });
  if (node.status === 'removed') ops.push({ op: 'remove',  path: pointer });
  if (node.status === 'changed' && !node.children) {
    ops.push({ op: 'replace', path: pointer, value: node.after });
  }
  for (const child of node.children ?? []) {
    const seg = String(child.key).replace(/~/g, '~0').replace(/\//g, '~1');
    ops.push(...toJsonPatch(child, pointer + '/' + seg));
  }
  return ops;
}

路径分段遵循 JSON Pointer (RFC 6901) 的规则 —— 注意键里的 ~ 和 / 要分别转义成 ~0 和 ~1。像 fast-json-patch 这样的库也能生成同样的结果，如果你不想自己写的话。Patch 通过 HTTP 发送时用 application/json-patch+json 这个 content type；要看更简单的「叠加」式替代方案，里面 null 表示删除，请见 JSON Patch 与 JSON Merge Patch。

值得了解的边界情况

  • 数组元素重新排序 —— 语义 diff 按位置比较数组（[0] 比 [0]），所以如果一个数组在两个版本里排序不同，即便数据一样，每个元素都可能显示为「变化」。要把这个处理好，得在数组层面也跑 LCS，复杂度会大幅增加。
  • 超大文档 —— O(m × n) 的 LCS 表对几万行的文档会吃光内存。实用启发式：如果 m × n 超过某个阈值（比如 200 万），就退化成把所有行都标成变化，而不去算完整的 diff。
  • 数值精度 —— JSON.parse() 把所有数字转成 IEEE 754 双精度。极大整数（超过 2⁵³）会静默失去精度，所以两份文档只在大整数末尾几位上不同时，解析后可能比出来是相等的。

常见问题

怎么比较两个 JSON 文件？

把两份都解析，归一化（排序键、统一缩进），然后跑结构化 diff，而不是普通文本 diff —— 或者把两份都贴到 JSON Diff，它就是这么做的，还会用颜色编码的并排视图展示。

为什么普通文本 diff 对 JSON 不行？

因为 JSON 对象是无序的，空白也是无意义的。文本 diff 会把重排后的键和重新格式化当成改动；JSON 感知的 diff 把这两者都忽略，只报告真正的数据差异。

什么是语义 JSON diff？

走完两份解析后的结构，在同一键路径下比较值（不管顺序），产出像「新增 3 个，删除 1 个，修改 2 个」这样的计数。从设计上就和键顺序无关。

比较 JSON 会丢失数值精度吗？

会 —— JSON.parse() 把数字转成 IEEE 754 双精度，所以超过 2⁵³ 的整数，即便末尾几位不同，也可能比出来是相等的。RFC 8785 里的规范化规则处理的就是相关问题。

试一下 JSON Diff 工具

JSON Diff 在 fixjson.org 上实现了上面描述的全部：解析两份文档，按排序后的键归一化，跑 LCS 行 diff，并以并排视图展示，新增、删除、修改各用颜色区分 —— 还附带一个汇总行展示新增、删除、修改和未变的字段数。它也支持 YAML 文档。一切都在你的浏览器里跑；没有数据被发送到任何服务器。