diff アルゴリズム徹底解説 - Myers・patience・histogram は何が違うのか

5万行のファイルの約3割を書き換え、その差分を Git の4種類の diff アルゴリズムで出してみました。結果は次のとおりです(Git 2.52.0、Apple M3 Max、5回計測したときの幅)。

同じ2つのファイルなのに、出てくる差分の行数がアルゴリズムごとに違います。既定の myers は「最小の差分」を求めるアルゴリズムとして知られていますが、minimal のほうがさらに10行ずつ少なく、その代わり10倍以上の時間がかかっています。patience と histogram は最小ですらないのに、速いうえ、人間には読みやすい差分を出すことが多いとされます。

この記事では、diff が解いている問題(LCS と編集距離)から始めて、Eugene W. Myers の O(ND) アルゴリズムを Python で実装して動かし、patience diff と histogram diff が何を変えたのかを、Git のソースコードと原論文を見ながら整理します。Git がファイルを差分ではなくスナップショットで保存していることはGit の内部構造で扱いました。この記事は、そのスナップショット同士を比べて差分を作る側の話です。

diff が解いている問題: LCS と最短編集スクリプト

diff の仕事を形式的に書くと、「系列 A を系列 B に変える、最も短い編集操作の列を求める」ことです。Git や Unix の diff では系列の要素は行で、操作は行の削除と行の挿入の2種類だけです。

この問題は、最長共通部分列(LCS: Longest Common Subsequence)を求める問題と表裏一体です。両方に共通して、順序を保ったまま残せる行をできるだけ多く選べば、残りは「消す行」と「足す行」になるからです。A の長さを N、B の長さを M、LCS の長さを L とすると、削除と挿入だけの最短編集スクリプトの長さ D は次の式で決まります。

D = N + M - 2L

Myers の論文も冒頭で「LCS を求める問題と最短編集スクリプトを求める問題は、双対な問題として古くから知られている」と書いています。

教科書的な解法: 動的計画法

LCS は動的計画法の定番問題です。表の各マスに「A の先頭 i 文字と B の先頭 j 文字の LCS 長」を入れていけば、表の右下が答えになります。論文と同じ例 ABCABBA と CBABAC で確かめます。

def lcs_length(a, b):
    """教科書どおりの DP。表のサイズは (N+1) x (M+1)"""
    n, m = len(a), len(b)
    prev = [0] * (m + 1)
    for i in range(1, n + 1):
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                cur[j] = prev[j - 1] + 1
            else:
                cur[j] = max(prev[j], cur[j - 1])
        prev = cur
    return prev[m]
 
 
def levenshtein(a, b):
    """置換も1手と数える編集距離"""
    prev = list(range(len(b) + 1))
    for i in range(1, len(a) + 1):
        cur = [i] + [0] * len(b)
        for j in range(1, len(b) + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            cur[j] = min(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + cost)
        prev = cur
    return prev[len(b)]
 
 
if __name__ == "__main__":
    a, b = "ABCABBA", "CBABAC"
    L = lcs_length(a, b)
    print("LCS 長 L =", L)
    print("挿入と削除だけの編集距離 D = N + M - 2L =", len(a) + len(b) - 2 * L)
    print("Levenshtein 距離(置換あり) =", levenshtein(a, b))

LCS 長 L = 4
挿入と削除だけの編集距離 D = N + M - 2L = 5
Levenshtein 距離(置換あり) = 4

「編集距離」には流儀が2つあることに注意してください。置換を1手と数える Levenshtein 距離は 4 ですが、diff が使うのは置換を「削除1回+挿入1回」と数える流儀で、こちらは 5 です。diff の出力で書き換えた行が - と + のペアで出てくるのはこのためです。

この DP は正確ですが、計算量は O(NM) です。1万行同士なら1億マスを埋めることになり、差分がたった1行でも表全体を計算します。計算量の考え方でいえば、入力サイズの2乗に比例します。

Unix diff の系譜

Unix の diff コマンドのアルゴリズムを説明した古典が、J. W. Hunt と M. D. McIlroy による「An Algorithm for Differential File Comparison」(Bell Laboratories Computing Science Technical Report #41)です。McIlroy 氏が公開しているスキャン版の注記では、このレポートは1976年7月付です。要旨には、diff は2つのファイルの差を最小の行変更の列として報告するプログラムであり、実データでは時間と空間がファイル長の和に比例する程度に収まるが、最悪の場合は積に比例する、と書かれています。LCS を壊すと短くなってしまう「候補」の一致だけに注目することで、実用上の速さを得る設計でした。

この「実データでは速いが、最悪ケースの保証がない」状況に対して、差分の大きさ D に比例するという別の軸で速さを保証したのが Myers のアルゴリズムです。

編集グラフ: diff を最短経路問題として見る

Myers の論文の出発点は、LCS 問題をグラフ上の経路探索に置き換えることです。

A を横軸、B を縦軸に並べた格子を考えます。点 (x, y) は「A の先頭 x 行と B の先頭 y 行まで処理した状態」です。

• 右へ1歩(横の辺): A の行を1つ削除する。コスト1
• 下へ1歩(縦の辺): B の行を1つ挿入する。コスト1
• 斜めに1歩(対角の辺): A の x+1 行目と B の y+1 行目が等しいときだけ使える。コスト0

  横軸 = A (ABCABBA)、縦軸 = B (CBABAC)
  \ は行が一致するマス = 斜めにタダで進める場所
 
        A   B   C   A   B   B   A
    C   .   .   \   .   .   .   .
    B   .   \   .   .   \   \   .
    A   \   .   .   \   .   .   \
    B   .   \   .   .   \   \   .
    A   \   .   .   \   .   .   \
    C   .   .   \   .   .   .   .
 
  左上 (0,0) から右下 (7,6) へ進む。右 = 削除、下 = 挿入、\ = 一致

(0,0) から (N,M) までの経路のうち、横と縦の辺の数(コスト)が最小の経路が最短編集スクリプトであり、そのとき通った斜めの辺が LCS です。diff は「重みが0か1のグラフの最短経路問題」になります。重み0と1の辺だけを持つグラフなので、グラフアルゴリズムで扱った BFS やダイクストラ法と同じく「近いところから順に広げる」発想が通用します。

論文はこの格子に2つの用語を導入します。

• 対角線 k: x - y = k を満たす点の集まり。斜めに進んでも k は変わらず、右へ進むと k が1増え、下へ進むと k が1減る
• snake(スネーク): 横か縦の辺を1本進んだあと、斜めの辺をできるだけ続けて進む一連の移動

コスト D の経路(D-path)は、必ず対角線 -D から D の範囲に収まります。そして論文の補題2が、このアルゴリズムの核心です。

対角線 k 上で最も遠くまで届く D-path は、対角線 k-1 上で最も遠くまで届く (D-1)-path から横に1歩進むか、対角線 k+1 上で最も遠くまで届く (D-1)-path から縦に1歩進むかしたあと、できるだけ長い snake をたどったものとして得られる(論文 Lemma 2 の要旨)

つまり、コスト D-1 の段階で「各対角線でどこまで行けたか」だけを覚えておけば、コスト D の段階の最遠点を計算できるのです。途中の経路をすべて覚えておく必要はありません。

Myers の O(ND) アルゴリズム

論文の書誌は、Eugene W. Myers, "An O(ND) Difference Algorithm and Its Variations", Algorithmica 1巻(1986年)251-266ページです。要旨の主張を整理すると次のとおりです。

• N を2つの系列の長さの和、D を最小編集スクリプトの長さとして、O(ND) 時間・O(ND) 空間の単純なアルゴリズムを示す
• 差分が小さい(系列が似ている)ときに速く、典型的な用途では高速である
• 基本的な確率モデルのもとで、期待計算量は O(N + D²) になる
• 改良版は O(N) の空間しか必要としない
• 接尾辞木を使うと、最悪でも O(N lg N + D²) 時間の変種が作れる

アルゴリズム自体は驚くほど短く書けます。配列 V を用意し、V[k] に「対角線 k 上で届いた最遠の x 座標」を入れます。D = 0, 1, 2, ... の順に、対角線 k = -D, -D+2, ..., D のそれぞれについて、隣の対角線から1歩進んで snake をたどり、V[k] を更新します。(N, M) に届いた時点の D が最短編集距離です。

計算量の議論も論文の中で完結しています。snake をたどる while ループ以外の部分は O(D²) で、while ループが対角線を進む回数は、幅 2D+1 の帯の中の点の数で抑えられるので O((M+N)D) になります。差分が小さいほど速い、という性質はここから来ています。

論文の序論によれば、この基本アルゴリズムは Miller と Myers による新しい Unix diff 実装(Software: Practice and Experience、1985年)の土台になり、Hunt と Szymanski のアルゴリズムに基づく System V の実装より「通常2倍から4倍速い」とされています。ただし論文自身が、2つのファイルがまったく異なる場合のように D が大きいときは、Hunt と Szymanski のアルゴリズムのほうが優れる場合があると認めています。

ミニ実装を書いて動かす

言葉だけでは掴みにくいので、論文の貪欲法(greedy algorithm)をそのまま Python で書きます。後で編集スクリプトを復元するために、D ごとの V 配列を保存しておきます。論文でいう O(D²) 空間の方法です。

def myers_trace(a, b):
    """Myers の greedy アルゴリズム。D ごとの V 配列のスナップショットを返す"""
    n, m = len(a), len(b)
    max_d = n + m
    offset = max_d                       # k は負になるので添字をずらす
    v = [0] * (2 * max_d + 2)            # v[k] = 対角線 k 上で到達した最遠の x
    trace = []
    for d in range(max_d + 1):
        trace.append(v[:])               # 後で経路を復元するために保存
        for k in range(-d, d + 1, 2):
            # 下へ進む(挿入)か、右へ進む(削除)かを選ぶ
            if k == -d or (k != d and v[offset + k - 1] < v[offset + k + 1]):
                x = v[offset + k + 1]            # k+1 から下へ: 挿入
            else:
                x = v[offset + k - 1] + 1        # k-1 から右へ: 削除
            y = x - k
            while x < n and y < m and a[x] == b[y]:
                x, y = x + 1, y + 1              # snake: 一致する限り斜めに進む
            v[offset + k] = x
            if x >= n and y >= m:
                return d, trace
    raise AssertionError("unreachable")
 
 
def myers_diff(a, b):
    d, trace = myers_trace(a, b)
    offset = len(a) + len(b)
    x, y = len(a), len(b)
    script = []
    for dd in range(d, 0, -1):           # 終点から始点へ逆向きにたどる
        v = trace[dd]
        k = x - y
        if k == -dd or (k != dd and v[offset + k - 1] < v[offset + k + 1]):
            prev_k = k + 1
        else:
            prev_k = k - 1
        prev_x = v[offset + prev_k]
        prev_y = prev_x - prev_k
        while x > prev_x and y > prev_y:  # snake 部分は一致行
            x, y = x - 1, y - 1
            script.append("  " + a[x])
        if x == prev_x:
            y -= 1
            script.append("+ " + b[y])
        else:
            x -= 1
            script.append("- " + a[x])
    while x > 0 and y > 0:               # D=0 の snake
        x, y = x - 1, y - 1
        script.append("  " + a[x])
    return d, list(reversed(script))
 
 
if __name__ == "__main__":
    import sys
    if len(sys.argv) == 3:
        a = open(sys.argv[1], encoding="utf-8").read().splitlines()
        b = open(sys.argv[2], encoding="utf-8").read().splitlines()
    else:
        a, b = list("ABCABBA"), list("CBABAC")   # 論文の例
    d, script = myers_diff(a, b)
    print("D =", d)
    for line in script:
        print(line)

D = 5
- A
- B
  C
+ B
  A
  B
- B
  A
+ C

D = 5 は、先ほどの DP で求めた N + M - 2L = 5 と一致します。編集スクリプトは「1行目と2行目を削除、3行目の後に B を挿入、6行目を削除、7行目の後に C を挿入」で、論文の Figure 1 に載っている編集スクリプト 1D, 2D, 3IB, 6D 7IC とも一致しました。

V 配列の動きを見る

各 D の探索が終わった時点で、V 配列がどうなっているかを表示してみます。

from myers import myers_trace
 
a, b = "ABCABBA", "CBABAC"
d, trace = myers_trace(list(a), list(b))
offset = len(a) + len(b)
for dd in range(1, d + 1):
    v = trace[dd]  # D=dd を始める直前 = D=dd-1 の探索結果
    ks = range(-(dd - 1), dd, 2)
    row = "  ".join("k=%+d:x=%d" % (k, v[offset + k]) for k in ks)
    print("D=%d 終了時  %s" % (dd - 1, row))
print("D=%d で終点 (%d,%d) に到達" % (d, len(a), len(b)))

D=0 終了時  k=+0:x=0
D=1 終了時  k=-1:x=0  k=+1:x=1
D=2 終了時  k=-2:x=2  k=+0:x=2  k=+2:x=3
D=3 終了時  k=-3:x=3  k=-1:x=4  k=+1:x=5  k=+3:x=5
D=4 終了時  k=-4:x=3  k=-2:x=4  k=+0:x=5  k=+2:x=7  k=+4:x=7
D=5 で終点 (7,6) に到達

D が1増えるごとに、調べる対角線が1本ずつ両側へ広がっていくのが分かります。1段ごとに持っているのは「対角線ごとの最遠点」だけで、DP のように N × M の表を作ってはいません。終点 (7,6) は対角線 k = 7 - 6 = 1 上にあり、D = 5 の段でそこへ届きました。

最短経路は1本とは限らない

ここで実験をひとつ。実装中の比較 v[offset + k - 1] < v[offset + k + 1] を <= に変えて(両方の箇所)、同じ例を実行するとこうなります。

D = 5
- A
- B
  C
- A
  B
+ A
  B
  A
+ C

D は同じ5ですが、編集スクリプトは別物です。最短の編集スクリプトは一般に複数あり、どれが選ばれるかは同点時の選び方という実装の都合で決まります。この事実が、後で見る「最小なのに読みにくい差分」の根っこにあります。

DP と速度を比べる

3000行のファイルの一部を書き換え、Myers と DP の所要時間を比べます。

import random, time
from myers import myers_trace
from lcs_dp import lcs_length
 
random.seed(0)
N = 3000
a = ["line %d" % random.randrange(1_000_000) for _ in range(N)]
for changes in (10, 100, 1000):
    b = a[:]
    for _ in range(changes):
        i = random.randrange(len(b))
        b[i] = "changed %d" % random.randrange(1_000_000)
    t0 = time.perf_counter(); d, _ = myers_trace(a, b); t1 = time.perf_counter()
    L = lcs_length(a, b); t2 = time.perf_counter()
    print("書き換え %4d 行 | Myers: D=%4d  %.3f 秒 | DP: D=%4d  %.3f 秒"
          % (changes, d, t1 - t0, 2 * N - 2 * L, t2 - t1))

書き換え   10 行 | Myers: D=  20  0.002 秒 | DP: D=  20  2.937 秒
書き換え  100 行 | Myers: D= 194  0.027 秒 | DP: D= 194  2.984 秒
書き換え 1000 行 | Myers: D=1684  1.164 秒 | DP: D=1684  3.270 秒

DP は差分の量にかかわらず約3秒で一定です。Myers は差分が10行なら2ミリ秒で終わり、差分が増えるにつれて遅くなります(D が1000行を超える段階では、V 配列を D ごとに丸ごとコピーしている分のコストも効いています)。O(NM) と O(ND) の違いが、そのまま数字に出ています。現実の diff は「大きなファイルのごく一部だけが変わった」ケースがほとんどなので、この性質は非常に都合がよいわけです。

最小なのに読みにくい: 中括弧が揃ってしまう問題

では Myers で万事解決かというと、そうではありません。次のような変更を考えます。先頭に関数 date を追加し、getUser から1行消し、末尾の関数 price を削除した例です。中括弧を独立した行に置くスタイルで書いています。

import { db } from "./db.js";
 
// ユーザーを取得する
function getUser(id)
{
    const row = db.find(id);
    if (row)
    {
        log("found");
        return row;
    }
}
 
function price(n)
{
    if (n < 0)
    {
        return "-";
    }
    return String(n);
}
 
main(getUser(1), price(100));

import { db } from "./db.js";
 
function date(d)
{
    if (!d)
    {
        return "-";
    }
    return d.toISOString();
}
 
// ユーザーを取得する
function getUser(id)
{
    const row = db.find(id);
    if (row)
    {
        return row;
    }
}
 
main(getUser(1), date(new Date()));

Git の既定(myers)で差分を取ると、こうなります。

@@ -1,23 +1,22 @@
 import { db } from "./db.js";
 
-// ユーザーを取得する
-function getUser(id)
+function date(d)
 {
-    const row = db.find(id);
-    if (row)
+    if (!d)
     {
-        log("found");
-        return row;
+        return "-";
     }
+    return d.toISOString();
 }
 
-function price(n)
+// ユーザーを取得する
+function getUser(id)
 {
-    if (n < 0)
+    const row = db.find(id);
+    if (row)
     {
-        return "-";
+        return row;
     }
-    return String(n);
 }
 
-main(getUser(1), price(100));
+main(getUser(1), date(new Date()));

getUser はほとんど変わっていないのに、丸ごと消えて別の場所に書き直されたように見えます。一方、patience と histogram では次のようになります(この例では両者の出力は同一でした)。

@@ -1,23 +1,22 @@
 import { db } from "./db.js";
 
+function date(d)
+{
+    if (!d)
+    {
+        return "-";
+    }
+    return d.toISOString();
+}
+
 // ユーザーを取得する
 function getUser(id)
 {
     const row = db.find(id);
     if (row)
     {
-        log("found");
         return row;
     }
 }
 
-function price(n)
-{
-    if (n < 0)
-    {
-        return "-";
-    }
-    return String(n);
-}
-
-main(getUser(1), price(100));
+main(getUser(1), date(new Date()));

こちらは変更の意図どおりです。ところが --numstat で行数を数えると、どちらも削除10行・追加11行で、編集距離はまったく同じです。

myers      10  11  old.js => new.js
patience   10  11  old.js => new.js
histogram  10  11  old.js => new.js

最短経路が複数あるとき、Myers のアルゴリズムは「人間にとって意味のある一致」を区別しません。単独の { や }、空行といったどこにでも現れる行同士を一致させても、関数名のような固有の行同士を一致させても、コストが同じなら等価に扱います。Git の myers は中括弧と空行を一致させる経路を選び、その結果、関数の境界をまたいだ不自然な差分になりました。

なお、先ほどの Python 実装に同じファイルを渡すと、D = 21 のまま patience と同じ見た目の編集スクリプトが出てきます。Git の実装は後述のとおり両端から探索して中央で分割する方式なので、選ばれる経路が今回の素朴な実装とは異なります。ここから言えるのは「Myers だから必ず汚い」ではなく、Myers は読みやすさを最適化の対象にしていないので、どの最短経路に当たるかは運次第ということです。

この問題を真正面から扱ったのが Bram Cohen です。2010年3月30日のブログ記事「Patience Diff Advantages」で、彼はこう説明しています。ファイルの末尾から関数を消し、先頭に関数を足すと、LCS ベースの diff は関数ではなく中括弧を一致させがちで、F1 F2 F3 を F4 F1 F2 に対応付けるとき、F1 の中括弧を F4 に、F2 の中括弧を F1 に…と合わせてしまう。そしてこれは見苦しいだけでなく、本来きれいに解決できたはずのマージで競合を起こしうる、と。中括弧を単独の行に置くスタイルや、関数の間に空行を多く入れるスタイルで特に起きやすい、とも書かれています。

patience diff: ユニークな行を錨にする

Bram Cohen の同じ記事は、patience diff の手順を4つにまとめています。

1. 両方のファイルの先頭行が同じなら一致させ、2行目、3行目…と一致しなくなるまで続ける
2. 末尾についても同様に、最終行から一致しなくなるまで一致させる
3. 両方のファイルにちょうど1回ずつしか現れない行をすべて見つけ、それらの行だけで LCS を取って一致させる
4. 一致した行と行の間の区間それぞれに、手順1と2を適用する

肝は手順3です。} や空行は何度も出てくるので候補から外れ、関数のシグネチャやコメントのような1回しか出てこない行だけが「錨(アンカー)」として使われます。先ほどの例なら // ユーザーを取得する や function getUser(id) がそれに当たり、これらが先に固定されるので、中括弧がよそと一致する余地がなくなります。

Git の実装(xdiff/xpatience.c)の冒頭コメントも同じ考え方を述べています。両方のファイルでユニークな行を見つけ、両方での順序を保つ最大の列を取り出して最初の共通行とし、その間を再帰的に処理する。ユニークな行の組が見つからなくなった区間は、よく知られた Myers のアルゴリズムで処理する、というものです。patience diff は Myers を置き換えるのではなく、Myers の前段で区間を切り分ける仕組みだと言えます。「順序を保つ最大の列」を求める部分は、最長増加部分列を二分探索で求める実装になっています。

由来と実装の経緯で確認できたのは次の点です。

• アルゴリズムは Bram Cohen が考案・紹介したもの。PyPI の patiencediff パッケージは「Bram Cohen が最初に記述した patiencediff アルゴリズムの実装」であり、「コードは Bazaar のコードベースから切り出されたもの」と説明している
• Git には Johannes Schindelin のコミット「Implement the patience diff algorithm」(2009年1月)で入り、Git 1.6.2 から含まれている。コミットメッセージは「最初に +/- 行の数を最小化しようとせず、ユニークな行を保存しようとするので、古典的な Myers のアルゴリズムより少し直感的な出力になる」と説明している

patience diff は最小性を保証しません。冒頭の5万行の実験で patience だけ差分が1割近く多かったのは、ユニークな行を優先した結果、一致させられたはずの行を一致させなかったためです。

histogram diff: 出現回数の少ない行を錨にする

patience diff には弱点があります。ユニークな行が1つもない区間では錨が取れず、結局 Myers に丸投げになることです。定型的なコードやデータファイルでは、そういう区間がよく現れます。

histogram diff はここを改良したもので、Java 製の Git 実装 JGit で書かれました。JGit の HistogramDiff クラスの説明は次のとおりです(要約)。

• Bram Cohen の patience diff を拡張したもの。ブログの4つのルールをもとに実装し、さらに出現回数の少ない共通要素(low-occurrence common elements)を扱えるよう拡張した
• 系列 A の各要素の出現回数のヒストグラムを作り、B の要素を順に見ていく。A にも存在して出現回数が少なければ LCS の候補とし、最も出現回数の少ない LCS を分割点に選んで、その前後に再帰的に適用する
• ユニークな共通要素があるときは patience diff とまったく同じように振る舞い、ない場合は出現回数が最少の要素を選ぶ。これにより、標準の Myers にフォールバックするより読みやすい差分になる
• O(N²) を避けるため、同じハッシュバケットに入る要素数に上限(maxChainLength、既定64)を設け、超えた区間はフォールバックのアルゴリズム(既定は Myers)に回す
• maxChainLength が64のような小さな定数である限り、計算量は O(ND) で、理論上は同じでも MyersDiff より速いことが多い

Git へは Tay Ray Chuan のコミット「teach --histogram to diff」(2011年7月)で移植され、Git 1.7.7 から含まれています。コミットメッセージには「JGit の HistogramDiff アルゴリズムを C に移植した」「構造体とポインタを使うよう書き直し、JGit の2の28乗行という制限をなくした」とあります。Git 側の xdiff/xhistogram.c でも、チェーン長の上限は64で、上限を超えたときは fall_back_to_classic_diff で従来の diff に戻す作りになっています。

冒頭の実験で histogram が「myers に近い行数」を「patience 並みの速さ」で出していたのは、この設計の反映と見られます。ユニークな行がない区間でも出現回数の少ない行を錨にできるので、patience ほど一致を取りこぼさず、それでいて錨で区間を細かく切るので探索が軽く済みます。

Git の myers は本当に最小か

冒頭の表で、myers(14,175行)と minimal(14,165行)の結果が違っていました。Git の既定アルゴリズムは、必ずしも最小の差分を返さないということです。

Git の xdiff/xdiffi.c の中核関数 xdl_split のコメントには、こう書かれています。Myers の論文に基づき、箱の左上から前向きに、右下から後ろ向きに対角線を走査し、同じ対角線上で両者が交差したら最遠点を返す。ただし高コストなケースに遭遇しうるので、探索を打ち切って最適でない点を返すヒューリスティックが少し必要だ、と。両端から探索して中央の snake(middle snake)で分割統治するこの方式は、論文の4b節「A Linear Space Refinement」で示された線形空間版に相当します。論文自身も、この線形空間版は基本版のおよそ2倍遅いが、他のアルゴリズムでは扱えない大きな比較ができると述べています。

打ち切りの具体的な条件もソースから読めます。

• 編集コストが XDL_HEUR_MIN_COST(256)を超え、かつ長い snake(XDL_SNAKE_CNT = 20 行超)が見つかっているとき、「有望な」対角線があればそこで分割する
• 編集コストが mxcost(2つのファイルの行数の和に3を足した値の平方根。ただし最低256)に達したら、コメントいわく「Enough is enough」で、その時点で最も遠くまで届いた点を採用する
• --minimal を指定したとき(内部フラグ XDF_NEED_MINIMAL)は、これらのヒューリスティックをすべて飛ばす

冒頭の実験は約3割を書き換えたので D が非常に大きく、打ち切りが発動して10行ぶん最適から外れた、と考えると数字の辻褄が合います。minimal が10倍以上遅かったのは、打ち切らずに最後まで探索したコストです。普段の小さな差分ではコストが256に届かないので、myers と minimal の結果はまず変わりません。

GNU diff も事情は同じです。GNU diff が使う gnulib の diffseq.h は、冒頭コメントで基本アルゴリズムを Myers の論文(Algorithmica Vol. 1, 1986)と明記し、Esko Ukkonen が1985年に独立に同じアルゴリズムを発見していたことにも触れています。そのうえで、find_minimal フラグが立っていない限り、Paul Eggert による TOO_EXPENSIVE ヒューリスティックでコストを N の1.5乗 × log N のオーダーに抑える代わりに、差分の多い大きな入力では最適でない出力を返す、と書かれています。GNU diff のヘルプでは -d, --minimal が「より小さな変更の集合を見つけるよう努力する」オプションとして説明されています。

Git で使い分ける

Git のドキュメントに書かれているアルゴリズムは次の4つです。

使い方は3通りあります。

# その場で切り替える
git diff --diff-algorithm=histogram
git diff --histogram            # 同じ意味の短縮形
git diff --patience
git diff --minimal
 
# 既定を変える
git config --global diff.algorithm histogram
 
# 既定を変えたうえで、一時的に myers に戻す
git diff --diff-algorithm=default

ドキュメントには、diff.algorithm を既定以外に設定していて既定のアルゴリズムを使いたいときは --diff-algorithm=default を指定する、と書かれています。

マージはすでに histogram

見落とされがちですが、マージでは既に histogram が既定です。git merge のマージ戦略のドキュメントは、ort 戦略のオプション diff-algorithm について「関係のない一致行(別の関数の中括弧など)による誤マージを避ける助けになる」と説明し、「ort の既定は diff-algorithm=histogram で、通常の diff は diff.algorithm の設定に従う」と明記しています。Bram Cohen が指摘した「中括弧の一致がマージ競合を生む」問題への、Git 自身の答えと言えます。マージと rebase の使い分けはmerge と rebase の違いを参照してください。

# マージ時に使う diff アルゴリズムを明示する例
git merge -X diff-algorithm=patience topic

関連オプション

• --anchored=<text>: 指定した文字列で始まり、両方のファイルに1回ずつ現れる行が削除・追加として表示されないようにする。内部では patience diff を使う(ドキュメントより)。関数を移動したときに、移動しなかった側を固定したい場面で使えます
• --indent-heuristic: ハンクの境界をずらして読みやすくするヒューリスティック。既定で有効で、--no-indent-heuristic で無効化できる

indent heuristic は「どの行を一致させるか」ではなく、「同じ内容の追加ブロックを上下どこに置くか」を調整する後処理です。Bram Cohen の記事にある、新しい関数を挿入したのに } と空行の位置がずれて見える例は、こちらの問題に当たります。

どれを選ぶか

• 普段のコードレビューやログ閲覧: histogram を既定にしておくのが無難です。マージと同じアルゴリズムになるので、見ている差分とマージ時の一致の取り方が揃うという利点もあります
• 関数の移動や並べ替えが多い変更: patience か histogram。特定の行を固定したいなら --anchored
• パッチのサイズを最小にしたい、他ツールの出力と厳密に比べたい: --minimal。ただし大きな差分では時間がかかります
• 何も考えずに速さ優先: 既定の myers で十分です。小さな差分では打ち切りも発動しません

よく使う Git の設定やエイリアスはGit コマンドとエイリアスにまとめています。

まとめ

• diff が解いているのは削除と挿入だけの最短編集スクリプトで、これは LCS と双対な問題です。D = N + M - 2L の関係があり、置換を1手と数える Levenshtein 距離とは別物です
• 教科書的な DP は O(NM) で、差分の大小に関係なく表全体を埋めます。手元の3000行の実験では、差分10行でも約3秒かかりました
• Myers のアルゴリズム(Algorithmica, 1986)は、diff を編集グラフ上の最短経路として捉え、対角線ごとの最遠点だけを持つ貪欲法で O(ND) を達成します。同じ実験で Myers は2ミリ秒でした
• 最短編集スクリプトは一般に複数あり、Myers は読みやすさを区別しません。その結果、中括弧や空行を一致させた、最小なのに読みにくい差分が出ることがあります
• patience diff は両方に1回ずつしか現れない行を錨にし、histogram diff(JGit 由来)はそれを出現回数の少ない行にまで広げました。どちらも錨で区切った残りは Myers に任せる構造です
• Git の myers は大きな差分で探索を打ち切るヒューリスティックを持ち、必ずしも最小ではありません。最小が必要なら --minimal を使います
• git merge の ort 戦略は既に histogram が既定です。普段の git diff も diff.algorithm = histogram にしておくと、見る差分とマージの挙動が揃います

「diff は最小の差分を出すもの」という理解は、半分だけ正しいと言えます。実際のツールは、最小性・速さ・人間にとっての読みやすさの三つの間で、アルゴリズムとヒューリスティックを組み合わせて折り合いをつけています。--diff-algorithm を切り替えて同じ変更を見比べると、その折り合いの付け方の違いがよく分かります。

参考リンク

• An O(ND) Difference Algorithm and Its Variations - Eugene W. Myers (PDF)
• An O(ND) difference algorithm and its variations - Algorithmica 1, 1986 (DOI)
• An Algorithm for Differential File Comparison - J. W. Hunt, M. D. McIlroy (PDF)
• Patience Diff Advantages - Bram Cohen
• patiencediff - PyPI
• JGit HistogramDiff.java
• Git - git-diff Documentation
• Git - git-config Documentation
• Git - merge-strategies Documentation
• git/git: xdiff/xdiffi.c
• git/git: xdiff/xpatience.c
• git/git: xdiff/xhistogram.c
• git/git: Implement the patience diff algorithm (commit 92b7de9)
• git/git: teach --histogram to diff (commit 8c912ee)
• gnulib: lib/diffseq.h