Git の diff アルゴリズム比較：myers / minimal / patience / histogram の違い
git diff の出力が「なぜそこを差分とみなした？」と疑問になったことはありませんか。Git は内部で 4 種類の diff アルゴリズムを切り替えられ、選んだアルゴリズムで「最小編集距離」「読みやすい差分」のどちらを優先するかが変わります。本記事では各アルゴリズムの特徴と、--diff-algorithm 設定の使い分けを整理します。
4 つのアルゴリズム
git diff --diff-algorithm=myers # デフォルト
git diff --diff-algorithm=minimal
git diff --diff-algorithm=patience
git diff --diff-algorithm=histogram| アルゴリズム | 出力の特徴 | 速度 | 適性 |
|---|---|---|---|
| myers | 最初の一致を貪欲に選ぶ | 速い | 汎用、デフォルト |
| minimal | 最小の編集距離を求める | 遅い（O(ND²) 程度） | 短い差分が要る |
| patience | 一意な行を起点にブロック比較 | 中 | 関数の入れ替え |
| histogram | patience の高速化版 | 速い | 大規模な差分に推奨 |
myers：デフォルト
Eugene Myers の 1986 年論文に基づく動的計画法。「追加と削除の合計を最小化」する系列を貪欲に探索します。
特徴：
- 最も古典的で実装が単純
- 多くの場合「直感的な差分」を出す
- ただし、似た行が複数ある場合に間違った行同士を対応付けることがある
例：
- void func_a() {
- }
- void func_b() {
- }
+ void func_c() {
+ }
+ void func_a() {
+ }
+ void func_b() {
+ }func_a と func_b を残して func_c を先頭に追加しただけのつもりでも、myers は単純に「上から順に」マッチングするため、全行が変更されたかのように見える出力になりがち。
minimal：最小編集距離
myers の貪欲性をやめ、真の最小の編集距離を求めます。計算量が大きく、実用上は myers で十分なケースが多い。
git diff --diff-algorithm=minimal短いコード片の正確な差分を取りたい、小さなテキストファイルを比較するときに使う。大規模リポジトリには遅すぎる。
patience：関数の入れ替えに強い
Bram Cohen（BitTorrent の作者）が考案した Patience Diff。
考え方：
- 両側のテキストで一意に出現する行（unique line）を探す
- それらを「アンカー」として両側で対応させる
- アンカー間の領域を再帰的に diff する
「ユニークな行」とは「両ファイルでそれぞれ 1 回しか出現しない行」。たとえばコードでは関数定義行、空行ではない区切り、import 文などがアンカーになります。
例（前述の関数追加）：
func_c() の定義行は左側になく、右側に 1 回 → アンカーにならない
func_a() の定義行は左右に 1 回ずつ → アンカー
func_b() の定義行は左右に 1 回ずつ → アンカーfunc_a と func_b のアンカーを手掛かりに、func_c の定義だけが追加された行として正しく検出される。
弱点：
- 全行が重複している（同じ行が大量にある）ファイルでは通常の diff に劣化
myersより計算量が大きいことがある
histogram：patience を改良
patience のアイデアを保ちつつ、ヒストグラム（行の出現回数）を使って一意行候補を高速に見つける。git（Linux 系列）の xdiff/xhistogram.c で実装。
git diff --diff-algorithm=histogramGit の文書では「myers より大きな差分・関数移動・refactor で読みやすい結果になる」とされています。実測でも patience より早く、myers と互角の速度で、より人間的な差分を出すことが多い。
どれを使うか
個別の比較
# 関数の移動・大きなリファクタリング
git diff --diff-algorithm=histogram HEAD~5 HEAD
# 短いテキストファイルの厳密な比較
git diff --diff-algorithm=minimal a.txt b.txt永続設定
# プロジェクト全体で histogram を使う
git config diff.algorithm histogram
# グローバルに設定
git config --global diff.algorithm histogramgit log -p、git show、git rebase --interactive での diff 表示にも適用。
実例：関数の入れ替え
実際に myers と histogram で出力が変わるケース。コードベースで helperA と helperB の順序を入れ替えただけ：
変更前：
function helperA() {
return 1;
}
function helperB() {
return 2;
}
function main() {
helperA();
}変更後：
function helperB() {
return 2;
}
function helperA() {
return 1;
}
function main() {
helperA();
}myers の出力（典型的）：
- function helperA() {
- return 1;
- }
-
function helperB() {
return 2;
}
+
+ function helperA() {
+ return 1;
+ }
function main() {
helperA();
}histogram の出力：
+ function helperB() {
+ return 2;
+ }
+
function helperA() {
return 1;
}
-
- function helperB() {
- return 2;
- }
function main() {
helperA();
}どちらも「正しい」差分ですが、histogram のほうが「helperB が上に移動した」というイメージに近い出力になります。
周辺機能：--word-diff と --color-moved
diff アルゴリズム自体ではないが、関連機能として：
--word-diff
git diff --word-diff行単位ではなく単語単位で diff。文章ファイル（CHANGELOG、README、Markdown）の差分を読みやすく表示。
--color-moved
git diff --color-moved=zebra行が移動されただけの場合、追加・削除を別の色（緑・赤ではなく青）で表示。リファクタリングの確認に有効。
color-moved は diff アルゴリズムと独立で、histogram + --color-moved=zebra を組み合わせると「移動した部分だけ青色、本当の変更だけ赤緑」という見やすい表示になります：
git diff --diff-algorithm=histogram --color-moved=zebra HEAD~5 HEADGitHub / GitLab での挙動
GitHub / GitLab の Web UI でも diff アルゴリズムは使われていますが、選択肢は限定的：
- GitHub：内部的に myers ベース（部分的に histogram を併用）
- GitLab：histogram
Web UI で「不自然な diff」が出ているときは、ローカルで git diff --diff-algorithm=histogram を試すと違う結果が見られる場合があります。
まとめ
Git の diff は myers がデフォルトだが、関数の入れ替えやリファクタリングを読みやすく表示したいなら histogram への変更が効きます。git config --global diff.algorithm histogram を一度設定すれば、git log -p・git show・git rebase でも常に適用され、副作用なく差分の質が向上します。Patience は histogram に置き換えてよく、minimal は短い厳密な比較が要るときの限定用途、というのが 2026 年の標準的な使い分けです。
複数のテキスト同士の差分は テキスト差分ツール で確認できます。