Git の diff の中身：Myers アルゴリズム入門
git diff や diff コマンドが返す「2 つのファイルの差分」は、見た目はシンプルですが、内部では「最も少ない編集操作で A から B にする手順」を計算する非自明なアルゴリズムが動いています。本記事では事実上の標準である Myers アルゴリズム（1986）と、その派生について整理します。
問題設定：最短編集距離
2 つの文字列（または行の列）A と B が与えられたとき：
- A から B に変換するために必要な「挿入」と「削除」の合計回数の最小値を求めたい
- その最小操作の具体的な内容（どの行を消し、どの行を足すか）も知りたい
これは 最短編集スクリプト（SES：Shortest Edit Script） と呼ばれ、長さ N の文字列 A、長さ M の文字列 B に対して D = N + M − 2L（L は最長共通部分列の長さ）の操作で達成できます。
つまり「最短 SES を求めること」と「最長共通部分列（LCS）を求めること」は等価な問題です。
ナイーブ解：DP で O(NM)
最も素直な解は動的計画法。LCS のサイズを 2 次元 DP テーブルで埋める方式で、時間・空間ともに O(NM)。
B[0] B[1] B[2] ...
A[0] . . .
A[1] . . .
A[2] . . .各セル (i, j) に「A[0..i] と B[0..j] の LCS の長さ」を入れていく。
問題点：
- N = M = 1000 なら 100 万セル → 余裕
- N = M = 100,000（大きいファイル）なら 10^10 → メモリ・時間ともに非現実的
実用ファイルサイズで動かすには、より効率的なアルゴリズムが必要でした。
Myers アルゴリズム：O((N+M)D)
Eugene Myers が 1986 年の論文「An O(ND) Difference Algorithm and Its Variations」で発表した方式で、差分の大きさ D に依存する計算量 O((N+M)D) が革新的でした。実用ではほとんどのファイル比較で D が小さいので、結果として非常に高速です。
編集グラフによる定式化
A と B を 2 次元グリッド上に展開して考えます：
- 横軸：A の文字（左から右に進む = A から削除）
- 縦軸：B の文字（上から下に進む = B から挿入）
- 対角線：A[i] == B[j] のとき斜めに進める（一致＝コピー）
目標：左上 (0, 0) から右下 (N, M) に、斜め移動はゼロコスト、横・縦移動はコスト 1 として、最小コストで到達する経路を求める。
A: A B C
B: .─.─.─.
A . │ ↘ ← 右下に進むほど A を消費
B . ↘
C . ↘ ← 斜めは「一致してコピー」これは 0-1 BFS（または bidirectional BFS） で解けます。Myers の論文ではさらに「中点を見つけて再帰分割する」最適化を加え、空間計算量を O(N+M) に抑えています。
D-path：D 回の編集で到達できる地点群
Myers の核心アイデアは「D 回の編集（横+縦移動）で到達できる地点群」を D = 0, 1, 2, … と順に広げていくこと。
- D = 0：対角線だけで到達できる範囲（A と B が完全一致なら一発で右下）
- D = 1：1 回の挿入または削除で到達できる範囲
- D = 2：2 回の編集で到達できる範囲
- … 最終的に右下 (N, M) を含む D が見つかれば終了
D は SES の長さに直結するので、差分が小さければ早期に終了する性質を持ちます。
なぜ Git は素の Myers を使わないのか
Git の diff は実は素の Myers ではなく、派生アルゴリズムを選択肢として持っています。
| アルゴリズム | 特徴 |
|---|---|
myers（デフォルト） | 標準 Myers。最短 SES を保証 |
minimal | Myers + より最小化を試す。やや遅い |
patience | 「ユニークな行をアンカーにする」発想。リファクタリングで読みやすい diff |
histogram | patience 改良版。Git 2.7 以降で利用可能。重複ヒストグラムでアンカーを見つける |
最短 SES と「人間にとって読みやすい diff」は必ずしも一致しません。例えば関数の入れ替えが起きた場合、Myers は「全体を消して挿入し直す」と等価な手順を返すことがあります。これに対し patience は「ユニークな共通行（関数定義など）をアンカーにする」ため、より構造的な diff を返します。
git config diff.algorithm patience で切り替えられます。リファクタリング多めのプロジェクトでは patience または histogram にすると体感が良くなります。
ハンク表示：差分の文脈表示
diff -u で得られる「ユニファイド形式」は、Myers が出した編集スクリプトを ハンク（hunk） にまとめて表示します。
@@ -10,7 +10,9 @@
unchanged line
unchanged line
-removed line
+added line A
+added line B
unchanged line@@ -10,7 +10,9 @@ の意味：A の 10 行目から 7 行、B の 10 行目から 9 行を表示。前後 3 行（デフォルト）の変更されない行も含めて表示することで、文脈が分かるようになっています。
ハンクは「変更行の連続」を 1 つの単位にまとめたもので、変更が離れていれば複数のハンクに分かれます。git diff -U10 のように -U オプションで前後の文脈行数を増やせます。
行単位 vs 文字単位
git diff はデフォルトで行単位の diff です。文字単位の差分が見たいときは：
git diff --word-diff— 単語単位（空白区切り）git diff --color-words— 単語単位 + 色付きgit diff --word-diff-regex='.'— 文字単位
文字単位は計算量が増えるので、長いファイルでは遅くなります。実用的には行単位 + 単語単位の併用がバランスが良いです。
実装で遭遇する罠
1. 改行コードの扱い
CRLF と LF が混在すると、すべての行が「変更された」と認識されます。.gitattributes で改行コードを正規化するか、ローカルの core.autocrlf を設定して防ぎます。
2. 末尾改行の有無
ファイル末尾に改行がない場合、diff は \ No newline at end of file というメタ情報を出力します。エディタや CI で意図せず末尾改行が消えると、無関係な diff が大量に発生します。
3. インデント変更だけの巨大 diff
タブ → スペース変換のように見た目が変わらない変更が、Myers では「全行削除＋全行挿入」と判定されてしまいます。git diff -w（空白を無視）で前後比較すれば、本質的な変更だけ確認できます。
まとめ
- diff の本質は「最短編集スクリプトを求める = 最長共通部分列を求める」問題
- 1986 年の Myers アルゴリズムは差分サイズ D に依存する O((N+M)D) で実用化を達成
- 「読みやすさ」を狙った派生として patience / histogram があり、Git は切り替え可能
- ユニファイド形式のハンクは Myers の出力を文脈付きで人間向けに整形したもの
実際に 2 つのテキストの差分を視覚的に確認したい場面では、本サイトの diff チェッカーで貼り付けるのが一番早いです。Myers アルゴリズム相当の挙動でハイライト表示します。