テキスト差分とパッチ実践：Diff アルゴリズムの原理とオン…

Diff：あらゆる場面で使われる差分計算

Git のバージョン管理からコードレビュー、設定変更からデータ同期まで、Diff はソフトウェア開発の基本操作です。

シーン	Diff の種類	ツール
コード変更	行レベル Diff	Git
設定の比較	キー値 Diff	オンライン比較ツール
JSON データ	構造化 Diff	json-diff
法的文書	意味 Diff	専用ツール
翻訳校正	文字レベル Diff	オンライン比較ツール

一、Myers Diff アルゴリズムの原理

核心となる考え方

Myers アルゴリズムは、元のテキストを目的のテキストへ変換する最短編集スクリプト（SES）——最小限の挿入・削除操作——を見つけます。

元: ABCABBA
目的: CBABAC

編集スクリプト:
- A    (A を削除)
  B    (B を保持)
- C    (C を削除)
  C    (C を保持 → 前に C を挿入)
  A    (A を保持)
  B    (B を保持)
- B    (B を削除)
  A    (A を保持)
+ C    (C を挿入)

アルゴリズムの図解

      0   1   2   3   4   5   6   7
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
0 │ → │ ↘ │   │   │   │   │   │   │  A
  ├───┼───┼───┼───┼───┼───┼───┼───┤
1 │ ↓ │   │ ↘ │   │ → │ ↘ │   │   │  B
  ├───┼───┼───┼───┼───┼───┼───┼───┤
2 │   │ ↓ │   │ ↘ │ ↓ │   │ ↘ │   │  C
  ├───┼───┼───┼───┼───┼───┼───┼───┤
3 │   │   │ ↓ │   │   │ ↓ │   │ ↘ │  A
  ├───┼───┼───┼───┼───┼───┼───┼───┤
4 │   │   │   │ ↓ │ ↘ │   │ ↓ │   │  B
  ├───┼───┼───┼───┼───┼───┼───┼───┤
5 │   │   │   │   │ ↓ │   │   │ ↓ │  B
  ├───┼───┼───┼───┼───┼───┼───┼───┤
6 │   │   │   │   │   │ ↓ │ ↘ │   │  A
  └───┴───┴───┴───┴───┴───┴───┴───┘
    C   B   A   B   A   C   B   A

→ = 右移動（削除）  ↓ = 下移動（挿入）  ↘ = 対角（保持）

時間計算量

ケース	計算量	説明
最良	O(ND)	N=テキスト長、D=差分数
最悪	O((N+M)D)	完全に異なるテキスト
典型的	O(N+D²)	差分が少ない場合

二、ツールボックスでテキストを比較する

操作手順

テキスト比較ツールを開く
左側に元のテキストを貼り付ける
右側に変更後のテキストを貼り付ける
差分結果を確認：
- 赤：削除された行
- 緑：追加された行
- 黄：変更された行
文字レベル差分のハイライトに対応し、1 文字単位の変化まで正確に表示

比較モード

モード	粒度	適用シーン
行レベル	行ごとに比較	コード変更
単語レベル	単語ごとに比較	ドキュメント修正
文字レベル	文字ごとに比較	精密な校正

三、JSON Diff の特殊テクニック

JSON Diff ツールを使う

JSON Diff ツールを開く
2 つの JSON データを貼り付ける
構造化された差分を確認：
- 追加／削除／変更されたキー
- 値の変化（型の変化を含む）
- ネストされたパス

JSON Diff vs テキスト Diff

// 元
{ "name": "张三", "age": 25, "tags": ["a", "b"] }

// 変更後
{ "name": "张三", "age": 26, "tags": ["a", "c"], "email": "z@test.com" }

比較方法	結果
テキスト Diff	行単位で差分を表示、理解しにくい
JSON Diff	`age: 25→26`、`tags[1]: "b"→"c"`、`+email: "z@test.com"`

四、Unified Diff フォーマット

フォーマット仕様

--- a/config.json
+++ b/config.json
@@ -1,5 +1,6 @@
 {
   "name": "my-project",
-  "version": "1.0.0",
+  "version": "2.0.0",
   "description": "A tool",
-  "private": true
+  "private": true,
+  "license": "MIT"
 }

記号	意味
`---`	元のファイル
`+++`	変更後のファイル
`@@ -a,b +c,d @@`	差分位置（元ファイルの a 行目から b 行、変更後の c 行目から d 行）
`-`	削除された行
`+`	追加された行
（スペース）	コンテキスト行

五、パッチの生成と適用

パッチを生成する

import * as Diff from 'diff';

const oldText = 'Hello World\nGoodbye World';
const newText = 'Hello World\nGoodbye Cruel World';

// パッチを生成
const patch = Diff.createPatch('file.txt', oldText, newText, 'old', 'new');
console.log(patch);

出力：

--- old/file.txt
+++ new/file.txt
@@ -1,2 +1,2 @@
 Hello World
-Goodbye World
+Goodbye Cruel World

パッチを適用する

// 順方向に適用
const result = Diff.applyPatch(oldText, patch);

// 逆方向に適用（ロールバック）
const reversed = Diff.applyPatch(newText, Diff.reversePatch(patch));

3 方向マージ

const base = '元のテキスト';
const branchA = 'A の変更';
const branchB = 'B の変更';

const merged = Diff.mergeDiff3(base, branchA, branchB);
// 自動マージ。コンフリクト時は <<<<<<< / ======= / >>>>>>> でマーク

六、実際の応用シーン

設定ファイルの変更検出

const oldConfig = JSON.parse(fs.readFileSync('config.old.json', 'utf-8'));
const newConfig = JSON.parse(fs.readFileSync('config.new.json', 'utf-8'));

const diff = Diff.diffJson(oldConfig, newConfig);
diff.forEach(part => {
  if (part.added) console.log('追加:', JSON.stringify(part.value, null, 2));
  if (part.removed) console.log('削除:', JSON.stringify(part.value, null, 2));
});

翻訳ファイルの校正

// 中国語と英語の翻訳キーの一貫性を比較
const zhKeys = Object.keys(flatten(zhTranslation));
const enKeys = Object.keys(flatten(enTranslation));

const missingInEn = zhKeys.filter(k => !enKeys.includes(k));
const missingInZh = enKeys.filter(k => !zhKeys.includes(k));

API レスポンスの回帰テスト

const expected = await fs.readFile('fixtures/expected.json', 'utf-8');
const actual = await fetch('/api/data').then(r => r.json());

const diff = Diff.diffJson(JSON.parse(expected), actual);
if (diff.some(d => d.added || d.removed)) {
  throw new Error('API レスポンスが期待と一致しません');
}

七、パフォーマンス最適化

最適化戦略	効果	適用
コンテキスト行数を制限	出力サイズを削減	大きなファイル
ハッシュ前処理	同一行をスキップ	超大きなファイル
チャンク比較	並列処理	非常に長いテキスト
文字レベルより先に行レベル	計算量を削減	コードファイル

// コンテキスト行数を制限
const patch = Diff.createPatch('file', old, new, '', '', { context: 3 });