← 全部文章
更新於 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。要是非／否答案的時候用 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 文件。一切都在你的瀏覽器中執行；不會有資料被送到任何伺服器。