Git Diffの仕組み：Myers diffアルゴリズムとテキスト変更追跡の数理

Gitのgit diffやコードレビューツールの根幹にあるのは、2つのテキスト間の変更点を最も簡潔に特定する数理問題です。元の文字列シーケンスA（長さN）を、変更後のシーケンスB（長さM）へ変換するために必要な最小限の挿入（Insertion）と削除（Deletion）の操作リストを求める問題を最短編集スクリプト（SES, Shortest Edit Script）と呼びます。

この問題は、両方のシーケンスに共通して順序通り含まれる最長の部分列を求める最長共通部分列（LCS, Longest Common Subsequence）問題と完全な双対（Dual）関係にあります。

1986年にユージーン・マイヤーズ（Eugene W. Myers）が発表した論文*"An O(ND) Difference Algorithm and Its Variations"*は、GNU diffやGitのデフォルト差分比較エンジンとして採用されています。マイヤーズは比較問題を2次元の編集グラフ（Edit Graph）上の最短経路問題としてモデル化しました：

• X軸方向への移動はシーケンスAからの削除を表します。
• Y軸方向への移動はシーケンスBへの挿入を表します。
• A[x]とB[y]の内容が一致するポイントでは斜め方向への移動が許され、斜め移動のコストは0です。

マイヤーズは対角線k = x - yを軸に幅優先探索を展開し、差分の数Dが小さい場合にO((N+M)D)という圧倒的な高速性で最短経路を特定するアルゴリズムを完成させました。

• 行単位Diff: ソースコード比較の標準です。極めて高速に計算されますが、長いコード行の中の変数名が1文字変わっただけでも行全体が「削除されて再追加された」と判定されます。
• 単語単位Diff: 行単位で差分が検出された箇所に対し、2次処理として単語単位でマイヤーズアルゴリズムを再実行し、行内部の具体的な変更箇所をハイライトします。
• AST構文木Diff: ソースコードの構文木同士を比較します。単に関数の宣言位置をファイルの別位置へ移動しただけの場合などに、無意味な差分ノイズを完全に除外できます。

// 標準Unified Diffフォーマット例:
--- a/calculator.js
+++ b/calculator.js
@@ -10,4 +10,4 @@
 function calculatePrice(basePrice, taxRate) {
-    const shipping = 200;
+    const shipping = 250; // 配送料金の改定
     return basePrice + (basePrice * taxRate) + shipping;
 }

2人の開発者が共通のコミット（Base）から別々にブランチを切って変更を加えた場合、Gitは単純な2者比較ではなく3-Way Mergeを実行します：

1. 共通の祖先（Base）とブランチAの差分（diff(Base, A)）を追跡します。
2. 共通の祖先（Base）とブランチBの差分（diff(Base, B)）を追跡します。
3. Aが10〜20行目を変更し、Bが50〜60行目を変更している場合、変更領域が重ならないためGitは自動的に両者の変更を統合します。

しかし、両者が同じ行番号や隣接する行を互いに異なって変更した場合、Gitは自動統合を中断して競合マーカー（<<<<<<< HEAD, =======, >>>>>>>）を挿入し、人間の判断に委ねます。

ブラウザのJavaScript上で数千行のテキストを比較する際、文字列同士をそのまま比較するとパフォーマンスが低下します。各行のテキストを整数IDへマッピング（String Interning）し、マイヤーズ探索を軽量な整数配列の比較として実行することで、メモリ消費を大幅に削減し数十倍の高速化を達成できます。DevUtils Diff Checkerを使えば、ブラウザ上で安全に高速な差分比較を行えます。

// 高速マイヤーズアルゴリズムのための行単位の整数トークン化
export function tokenizeTextToIntegers(rawText) {
    const lines = rawText.split(/\r?\n/);
    const pool = new Map();
    const tokenIds = [];
    
    for (const line of lines) {
        if (!pool.has(line)) {
            pool.set(line, pool.size);
        }
        tokenIds.push(pool.get(line)); // 重い文字列ではなく軽量な整数IDを使用
    }
    return { tokenIds, lineCount: lines.length, lines };
}