Compare JSON

文档博客更新日志Compare XML
技术

JSON Diff 的底层原理：树、路径，和几个经典算法的组合

2026年10月3日 · 约 7 分钟

对两个 JSON 文档点击 Compare，差异瞬间就全部高亮出来。但中间到底发生了什么？简短的回答是「把两份文档解析成树，然后遍历」——但有意思的是，这次遍历里藏着好几个经典算法。

为什么不直接 diff 文本？

最直觉的方案是用 JSON.stringify 把两份文档格式化，然后像 Git 那样做逐行 diff。但它立刻就会出问题。第一个问题是空白符和换行：

{"a":1,"b":2}
{
  "a": 1,
  "b": 2
}

数据完全等价，但文本 diff 会把每一行都标记为不同。就算先统一格式化，key 顺序也会破坏这个方案：

{"a":1,"b":2}
{"b":2,"a":1}

同一份文档，序列化结果不同——JSON.stringify 会产出两个不同的字符串，每一行都「变了」。而且逐行 diff 根本不懂 JSON 语法：把 "b": 2 挪到最前面，行尾逗号会跟着挪，于是文本 diff 把 "a": 1 报告成「修改」，尽管变化的只是逗号：

  {
-     "a": 1
+     "b": 2,
+     "a": 1
-     "b": 2
  }

JSON 是数据，不是文本。所以 diff 必须发生在数据上。

核心思路：比较树，报告路径

两边解析完成后，问题就变成了树的比较。我们使用的引擎（@compare-json/core）产出的不是变更的行，而是一张扁平的变更路径列表：

interface JSONValueDifference {
  pathSegments: string[];              // ['users', '[3]', 'email']
  pathString: string;                  // 'users[3].email'
  pathBelongsTo: 'base' | 'contrast' | 'both';
  diffType: 'added' | 'deleted' | 'valueChanged' | 'typeChanged';
}

这个输出结构决定了一切。遍历本身是一次按值类型的分发：

  • 类型不同 → 在当前路径报告 typeChanged，不需要递归——数字变成对象是一个事实，而不是一坨噪声。
  • 相同的原始类型 → 直接比较，不等就是 valueChanged。
  • 都是对象 → 比较 key 集合（见下文）。
  • 都是数组 → 用三种策略之一比较（见下文）。

剩下的全是递归。

对象：匹配 key，而不是匹配行

因为我们报告的是路径而不是渲染对齐的文本，对象比较根本不需要排序或双指针合并——key 的顺序从头到尾都不会被读取。算法更接近集合求交：

  1. 遍历 base 对象的每个 key。如果这个 key 在 contrast 侧也存在，递归比较两个值；不存在，则该路径为 deleted。
  2. 遍历 contrast 对象的 key。从未被匹配到的就是 added。

key 大小写不敏感匹配只是匹配阶段的细节：在 contrast 侧建一个「小写 key → 真实 key」的 Map，每个 base key 通过它解析。递归本身并不关心这些。

数组：三种策略对应三种「相同」的定义

数组是 JSON diff 真正有趣的地方，因为「这两个数组不同」这句话有歧义。引擎提供三种方法，各自背后是一个不同的经典算法：

By Index —— 位置假设

把 a[i] 和 b[i] 配对，逐对递归，多出来的尾部报告为新增或删除。当位置本身有意义时（表格行、坐标、时间序列），这是正确的选择。

LCS —— 最小编辑假设

当数组是「偶尔增删几个元素」的列表时，按索引配对会产生垃圾结果：在头部插入一个元素会让所有索引偏移，于是每一对都「变了」。解法是经典的最长公共子序列动态规划：

// dp[i][j] = a[0..i) 和 b[0..j) 的最长公共子序列长度
if (deepEqual(a[i - 1], b[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]);

有两个细节值得注意。第一，这里的相等不是 ===——元素可以是对象，所以 DP 的每个格子会递归调用整个比较器，把「产生了零个差异」当作相等。第二，从 dp[m][n] 开始的回溯路径会直接告诉你哪些索引配上了：配上的对相等，没配上的 base 索引是 deleted，没配上的 contrast 索引是 added。一趟走完，插入一个元素就被准确地报告为一次插入。

Unordered —— 成员资格假设

有时候顺序完全没有意义（标签列表、权限集合）。这时比较就是多重集合匹配：对 base 的每个元素，在 contrast 侧找一个尚未匹配的、深度相等的元素。两边各自剩下的就是 diff。最坏情况是 O(n²)，但对真实世界的配置数组来说足够快——而且结果正是人类说的「同一个列表，只是顺序不同」。

小选项，大影响

有几个归一化选项位于值比较层，悄悄地改变着「什么算差异」：

  • keyCaseInsensitive / valueCaseInsensitive —— 字符串先转小写再比，"Name" 和 "name"、"TRUE" 和 "true" 不再是噪声。
  • numericStringEqualsNumber —— 把 "8080" 和 8080 视为相等。API 总喜欢把数字塞进字符串里，这个选项就是用来吸收这种情况的。

每个选项只有几行代码，但它们决定了 diff 是「技术上正确」还是「实际上有用」。你可以在对比选项里开关它们。

从路径列表到可读的界面

一张扁平的、按路径寻址的差异列表是很好的解耦接口：引擎对渲染一无所知，UI 对比较一无所知。

  • 结果侧边栏按路径和类型分组差异——点击条目，直接跳转。
  • Monaco 双栏视图把每条差异映射回编辑器的文本范围做高亮。
  • **git-diff 视图**把同一张列表渲染成统一的逐行摘要，照顾习惯看 +/- 的人。

一次计算，三种呈现。

两个只有踩过坑才知道的生产细节

大整数。 JSON.parse 会静默损坏超过 Number.MAX_SAFE_INTEGER 的整数——而 JSON 里到处都是 64 位 ID。我们用 bigint 安全的解析器，保证 9007199254740993 不会在比较开始前就变成 9007199254740992。一个会篡改输入的 diff 引擎不是 diff 引擎。

天然本地化。 因为整条流水线——解析、比较、渲染——都是对解析后值的纯计算，它可以完全在浏览器里运行。从来就没有需要服务器的理由，所以没有服务器。

总结

语义化 JSON diff 不是某一个聪明的算法，而是一堆无聊算法的组合：

  • 在值树上递归，
  • 对象用集合式 key 匹配，
  • 数组按「相同」的定义选用索引配对、LCS 回溯或成员匹配，
  • 再在叶子节点做几个有针对性的归一化。

回报是一个用 key 路径说话的 diff（users[3].email 变了），而不是行号——这才是你真正想知道的。

拿你自己的数据试试：立即对比两个 JSON 文件。