同じ2つのファイルを比較しても、diff アルゴリズムによって結果が変わることがあります。どれも「正しい」diff ですが、どの行どうしを同じとみなしてペアにするかが違うため、読みやすさが変わります。git は --diff-algorithm オプションで4種類を提供しています。
| 値 | git ドキュメントの説明 | 特徴 |
|---|---|---|
myers (default) | 基本的な貪欲（greedy）アルゴリズム。現在の既定値 | 高速で、たいてい最小に近い |
minimal | 最も小さい diff を作るために時間を余分に使う | 常に最小。大きな入力では遅くなることがある |
patience | patience diff アルゴリズム | 一意な行を基準点にする |
histogram | patience を拡張し、出現回数の少ない共通要素にも対応 | まれな行を基準点にする |
git diff --patience、git diff --histogram のような短いオプションもあり、git config diff.algorithm histogram で既定値を変更できます。
Myers：最小の編集を探す既定値
Myers アルゴリズムは、削除と追加の数が最小になる経路を探します（仕組みは diff の仕組みを参照）。問題になるのは、どの行を同じとみなすかの選択肢が複数あるときです。コードには }、{、空行、return のようにごくありふれた行が多いため、アルゴリズムが意味的に関係のない行どうしをペアにしても、編集数は同じく最小になりえます。
同じ変更、2通りの結果
次のように、関数 f と g の間に関数 h を新しく挿入したとします。次の2つの diff はどちらも追加4行で、編集数は同じです。
@@ -1,6 +1,10 @@ int f() { return 1; }++int h() {+ return 3;+} int g() { return 2;@@ -1,5 +1,9 @@ int f() { return 1;+}++int h() {+ return 3; } int g() {1つ目は新しい関数がまるごと見えますが、2つ目は既存の関数 f の閉じかっこを新しい関数のかっことして扱ったため、追加部分が不自然な位置で切れています。こうした形は探索の順序によって生じます。最近の git は、インデントを見て変更区間の境界を読みやすい位置にずらすヒューリスティック（--indent-heuristic、既定で有効）で、その多くを補正します。
Patience：一意な行を先に合わせる
patience diff は Bram Cohen が提案した方式で、まず両方のファイルにそれぞれ1回ずつしか現れない行を探します。関数宣言 int h() { のような一意な行は、対応が確実だからです。これらの一意な行の中から順序が一致する最長のリスト（最長増加部分列）を選んで基準点とし、基準点の間の小さな区間だけをもう一度比較します。
- 長所：
}や空行のようなありふれた行に引きずられないため、関数や段落単位の変更がひとかたまりで見えます。 - 短所：一意な行がほとんどない入力（同じ行が繰り返されるデータ、ログ）では基準点が見つからず、通常の diff と変わらないか、かえって大きなかたまりにまとまって見えることがあります。
Histogram：出現回数の少ない行を優先する
histogram アルゴリズムは JGit（Java で書かれた git 実装）で開発され、git にも取り込まれました。patience が「ちょうど1回現れる行」だけを見るのに対し、histogram は各行の出現回数を数え、最も少ない行を基準点に選びます。そのため、一意な行がなくても比較的まれな行を基準にできます。git のドキュメントはこれを「patience アルゴリズムを拡張し、出現回数の少ない共通要素に対応したもの」と説明しています。実務では patience と同様に、コードの構造をうまく保った結果になることが多いです。
どれを使うか
- 日常的なコードレビュー：既定値で十分です。結果の切れ方がおかしいと感じたら
--histogramで見直してください。 - 関数を移動したり複数追加したりする大きなリファクタリング：
--histogramまたは--patienceのほうがかたまりをうまく保ちます。 - 変更行数を厳密に最小で数える必要があるとき：
--minimal。 - 繰り返しの多いデータファイル：アルゴリズムよりもソートや正規化のほうが重要なことがあります。JSON なら JSON の比較を参照してください。
どのアルゴリズムを使っても、結果から復元されるファイルは同じです。変わるのは人が読むときの見た目だけです。
このツールでは
このサイトは Myers 系のアルゴリズムで行を比較したあと、変更された行どうしの内容の類似度を見て「変更」としてペアにし、行の中をもう一度比較します。そのため、行単位の結果が少し不自然に切れていても、どの単語が変わったかはすぐにわかります。テキスト比較ツールに上の例を入れて、統合表示と分割表示でどう見えるかを比べてみてください。結果の読み方は unified diff の読み方にまとめています。