二つのファイルを比較する

「Diff」は変更の共通言語です。それらは、物事の2つのバージョン間で何が動いたかを伝えるコンパクトな物語です—ソースコード、散文、データセット—すべてを再読することを強制することなく。それらのいくつかのシンボル（+、 -、@@）の背後には、最適性、速度、および人間の理解をバランスさせるアルゴリズム、ヒューリスティック、およびフォーマットの深いスタックがあります。この記事は、diffの実用的で、アルゴリズムからワークフローへのツアーです：それらがどのように計算されるか、どのようにフォーマットされるか、マージツールがそれらをどのように使用するか、そしてより良いレビューのためにそれらを調整する方法。途中で、私たちは主張を一次資料と公式ドキュメントに根拠を置きます—なぜなら、空白がカウントされるかどうかのような細部が本当に重要だからです。

「diff」とは実際に何か

正式には、diffは、挿入と削除を使用して「古い」シーケンスを「新しい」シーケンスに変換するための最短編集スクリプト（SES）を記述します（そして、削除+挿入としてモデル化できる置換も時々あります）。実際には、ほとんどのプログラマー向けのdiffは行指向であり、読みやすさのためにオプションで単語や文字に洗練されます。正規の出力は コンテキスト と ユニファイド フォーマットです。後者—コードレビューで通常目にするもの—は、簡潔なヘッダーと「ハンク」で出力を圧縮し、それぞれが変更の周りのコンテキストの近隣を示します。ユニファイドフォーマットは-u/--unifiedを介して選択され、パッチ適用のための事実上の標準です。 patchは一般的にコンテキスト行から恩恵を受けます 変更を堅牢に適用するために。

GNU diffマニュアルは、ノイズを減らして信号を増やしたいときに使用するスイッチをカタログ化しています—空白を無視する、整列のためにタブを展開する、またはそれが遅くても「最小」編集スクリプトを要求する (オプションリファレンス)。これらのオプションは、2つのファイルが異なることの意味を変えるものではありません。アルゴリズムがより小さなスクリプトをどれだけ積極的に検索するか、そして結果が人間にどのように提示されるかを変えるものです。

LCSからマイヤーズへ：diffはどのように計算されるか

ほとんどのテキストdiffは、 最長共通部分列（LCS） の抽象化に基づいています。古典的な動的計画法はLCSをO(mn)の時間と空間で解決しますが、大きなファイルには遅すぎてメモリを消費しすぎます。 ヒルシュバーグのアルゴリズム は、分割統治法を使用して線形空間（まだO(mn)時間）で最適なアライメントを計算する方法を示しました。これは、実用的なdiff実装に影響を与えた基本的な省スペース技術です。

速度と品質のためのブレークスルーは、 ユージン・W・マイヤーズの1986年のアルゴリズムでした。これは、O(ND)時間（N ≈ 総行数、D ≈ 編集距離）とほぼ線形の空間でSESを見つけます。マイヤーズは、「編集グラフ」で編集をモデル化し、最も遠くまで届くフロンティアに沿って進み、行diff設定で高速かつ最小に近い結果をもたらします。そのため、「マイヤーズ」は多くのツールでデフォルトのままです。

また、 ハント-シマンスキー ファミリーもあります。これは、一致する位置が少ない場合にLCSを高速化し（一致を事前にインデックス付けし、増加する部分列を追跡することによって）、歴史的に初期のdiffバリアントに関連付けられています。これらのアルゴリズムはトレードオフを明らかにします：まばらな一致を持つ入力では、それらは準二次的に実行できます。理論と実装を橋渡しする実践者の概要については、 ニール・フレイザーのメモを参照してください。

「最適」が読みにくいとき：ペイシェンスとヒストグラム戦略

マイヤーズは最小の編集スクリプトを目指しますが、「最小」≠「最も読みやすい」。並べ替えられたり複製されたりした大きなブロックは、純粋なSESアルゴリズムを不自然なアライメントに陥れる可能性があります。ブラム・コーエンに帰せられる ペイシェンスdiffを入力してください：それは、アライメントを安定させるためにユニークで低頻度の行に固定し、人間がよりきれいに感じるdiffをしばしば生成します—特に関数が移動したりブロックが再編成されたりしたコードで。多くのツールは、これを「ペイシェンス」オプション（例：diff.algorithm）を介して公開しています。

ヒストグラムdiff は、ペイシェンスを頻度ヒストグラムで拡張し、低発生要素をより良く処理しながら高速を維持します（ JGitで普及）。もし--histogramがノイズの多いファイルに対してより明確なハンクを生成することを発見したことがあるなら、それは設計によるものです。現代のGitでは、アルゴリズムをグローバルに、または呼び出しごとに選択できます：git config diff.algorithm myers|patience|histogramまたは git diff --patience。

単語レベルの明瞭さ、空白の制御、移動したコードのハイライト

行diffは簡潔ですが、小さな編集を隠すことがあります。 単語レベルのdiff （--word-diff）は、レビューを行全体の挿入/削除で溢れさせることなく、行内の変更を色付けします—散文、長い文字列、またはワンライナーに最適です。

再フォーマット後、空白がdiffを圧倒することがあります。GitとGNU diffの両方で、 スペースの変更を無視する ことができ、 GNU diffの空白オプション （-b、-w、-B）は、フォーマッタが実行されるときに役立ちます。アライメントノイズの代わりに論理的な編集が表示されます。

コードがまとめて移動する場合、Gitは--color-movedで 移動したブロックをハイライト でき、視覚的に「移動」と「変更」を区別し、レビュアーが移動が意図しない編集を隠していないことを監査するのに役立ちます。 diff.colorMovedを介して永続化します。

マージのためのDiff：双方向対三方向とdiff3

双方向diffは正確に2つのバージョンを比較します。両サイドが同じベースラインを編集したかどうかを判断できないため、しばしば過剰に競合します。 三方向マージ（現代のVCSで使用）は、共通の祖先から各サイドへのdiffを計算し、2つの変更セットを調整します。これにより、偽の競合が劇的に減少し、より良いコンテキストが提供されます。ここでの古典的なアルゴリズムコアは diff3で、これは「O」（ベース）から「A」と「B」への変更をマージし、必要に応じて競合をマークします。

学術的および産業的な研究は、マージの正確性を形式化し、改善し続けています。例えば、検証済みの三方向マージは、競合のないセマンティックな概念を提案します。日常のGitでは、現代の ortマージ戦略 は、diffとリネーム検出に基づいて、より少ない驚きでマージを生成します。ユーザーにとっての重要なヒントは、 merge.conflictStyle=diff3で競合のベースラインを表示し、diffを小さく保つために頻繁に統合することです。

リネーム検出とそのしきい値

従来のdiffは、コンテンツアドレッシングがファイルをブロブとして扱うため、リネームを「見る」ことができません。削除と追加しか見えません。 リネーム検出ヒューリスティック は、追加/削除されたペア間の類似性を比較することでそのギャップを埋めます。Gitでは、-M/--find-renames[=<n>]（デフォルトは約50%の類似性）を介して有効化または調整します。ノイズの多い移動には値を下げます。 候補比較を制限 できます diff.renameLimit（およびマージ中の merge.renameLimit ）で。リネームを越えて履歴を追跡するには、 git log --follow -- <path>を使用します。最近のGitは、マージ中にフォルダの移動を伝播させるために ディレクトリリネーム検出 も実行します。

バイナリとデルタdiff：rsync、VCDIFF/xdelta、bsdiff

変更されるのはテキストだけではありません。バイナリの場合、通常はデルタエンコーディングが必要です—ソースからターゲットを再構築するためのコピー/追加命令を発行します。 rsyncアルゴリズム は、ネットワークを介してブロックを整列させるためにローリングチェックサムを使用して効率的なリモート差分計算を開拓し、帯域幅を最小限に抑えました。

IETFは、ADD、COPY、およびRUNのバイトコードを記述する汎用デルタフォーマット、 VCDIFF（RFC 3284）を標準化しました。 xdelta3 のような実装がバイナリパッチングに使用しています。実行可能ファイルのコンパクトなパッチには、 bsdiff がサフィックスアレイと圧縮を介して非常に小さなデルタを生成することがよくあります。パッチサイズが優先され、生成がオフラインで行える場合に選択してください。

ソースコードを超えたテキストdiff：ファジーマッチングとパッチ適用

同時編集やわずかにずれたコンテキストに直面したときに堅牢なパッチ適用が必要な場合—エディタや共同作業システムを考えてみてください— diff-match-patchを検討してください。これは、マイヤーズスタイルの差分計算と Bitap ファジーマッチングを組み合わせて、ほぼ一致するものを見つけて「最善の努力」としてパッチを適用し、さらにdiff前の高速化とdiff後のクリーンアップにより、最小性を少し犠牲にしてより良い人間向けの出力を提供します。連続同期ループでdiffとファジーパッチを組み合わせる方法については、フレイザーの 差分同期を参照してください。

構造化データdiff：テーブルとツリー

CSV/TSVの行diffは、1セルの変更が全行の編集のように見えるため、脆弱です。 テーブル対応diffツール（daff） は、データを 行/列として扱い、特定のセルを対象とするパッチを発行し、追加、削除、変更を明確にする視覚化をレンダリングします（ Rヴィネットを参照）。迅速なチェックのために、特殊なCSV差分ツールはセルごとの変更とタイプのシフトを強調表示できます。これらはアルゴリズム的にエキゾチックではありませんが、実際に気にかけている構造を比較することでレビューシグナルを増加させます。

実践的なGit diffチューニング：レビュアーのチェックリスト

• 適切なアルゴリズムを選択する：マイヤーズ（デフォルト）から始め、並べ替えやノイズの多いブロックが出力を混乱させる場合は --patience を試し、反復的なテキストで高速で読みやすいdiffが必要な場合は --histogram を試してください。 git config diff.algorithm …でデフォルトを設定します。
• ノイズを減らす：スタイルのみの編集には、空白フラグ（-b、 -w、 --ignore-blank-lines）を使用して、実質的な変更に集中します。Git以外では、 GNU diffの空白コントロールを参照してください。
• 行内を見る： --word-diff は長い行や散文に役立ちます。
• 移動したコードを監査する： --color-moved （または diff.colorMoved）は、「移動」と「変更」を区別します。
• リネームを処理する：リファクタリングをレビューするときは、 -M を追加するか、類似性のしきい値（-M90%、-M30%）を調整してリネームをキャッチします。デフォルトは約50%であることを忘れないでください。深いツリーの場合は、 diff.renameLimitを設定します。
• リネームを越えて履歴を追跡する： git log --follow -- <path>。

マージが実際にdiffをどのように消費するか（そしてそうでない場合の対処法）

マージは2つのdiff（BASE→OURS、BASE→THEIRS）を計算し、両方をBASEに適用しようとします。 ort のような戦略は、リネーム検出（ディレクトリ規模の移動を含む）とヒューリスティックを組み込んで、競合を最小限に抑えるためにこれを大規模に調整します。競合が発生した場合、 --conflict=diff3 は、意図を理解するために非常に貴重なベースコンテキストでマーカーを豊かにします。Pro Gitの 高度なマージ の章では、解決パターンを順を追って説明し、Gitのドキュメントには -X oursや-X theirsのようなノブがリストされています。繰り返される競合で時間を節約するには、 rerere を有効にして、解決策を記録および再生します。

ファイルを超えて：リモートおよび増分シナリオ

ネットワーク経由で大きなアセットを同期している場合、ローカルのdiffよりも rsync の世界に近いです。Rsyncは、リモートで一致するブロックを発見するためにローリングチェックサムを計算し、必要なものだけを転送します。パッケージ化されたデルタの場合、 VCDIFF/xdelta は標準のバイトコードと成熟したツールを提供します。エンコーダとデコーダの両方を制御できる場合に選択してください。そして、パッチサイズが最優先される場合（例：無線ファームウェア）、 bsdiff は、ビルド時にCPU/メモリを非常に小さなパッチと交換します。

「ファジー」と「フレンドリー」についての簡単な言葉

diff-match-patch のようなライブラリは、現実の世界では、パッチを適用しているファイルがずれている可能性があることを受け入れます。堅実なdiff（多くの場合マイヤーズ）とファジーマッチング (Bitap)および構成可能なクリーンアップルールを組み合わせることで、パッチを適用する適切な場所を見つけ、diffをより読みやすくすることができます—共同編集と同期に不可欠です。

あなたが内面化すべき「テーブルステークス」

1. フォーマットを知る。ユニファイドdiff（-u/-U<n>）はコンパクトでパッチフレンドリーです。コードレビューとCIが期待するものです (リファレンス)。
2. アルゴリズムを知る。マイヤーズは高速な最小編集用 (論文); ペイシェンス/ヒストグラムは並べ替えやノイズの多いブロックでの読みやすさのため (ペイシェンス、 ヒストグラム); ヒルシュバーグは線形空間のトリックのため (論文); ハント-シマンスキーはまばらな一致の高速化のため (論文)。
3. スイッチを知る。空白コントロール、単語diff、および色付き移動はレビューの乗数です (git diffドキュメント; GNU空白オプション)。
4. マージを知る。 diff3 スタイルの三方向は混乱が少ないです。 ort とリネーム検出はチャーンを減らします。 rerere は時間を節約します。
5. データに適したツールを選択する。CSV/テーブルには daffを使用します。バイナリには VCDIFF/xdelta または bsdiffを使用します。

付録：小さなコマンドクックブック

筋肉の記憶が重要だからです：

# 追加のコンテキストを持つ標準のユニファイドdiffを表示する
  git diff -U5
  diff -u -U5 a b
  
  # 長い行や散文の単語レベルの明瞭さを得る
  git diff --word-diff
  
  # 再フォーマット後の空白ノイズを無視する
  git diff -b -w --ignore-blank-lines
  diff -b -w -B a b
  
  # レビュー中に移動したコードをハイライトする
  git diff --color-moved
  git config --global diff.colorMoved default
  
  # リネーム検出でリファクタリングを飼いならし、リネームを越えて履歴を追跡する
  git diff -M
  git log --follow -- <file>
  
  # 読みやすさのためにアルゴリズムを優先する
  git diff --patience
  git diff --histogram
  git config --global diff.algorithm patience
  
  # 競合マーカーのベースラインを見る
  git config --global merge.conflictStyle diff3

結びの言葉

優れたdiffは、最小性を証明することよりも、最小の認知コストでレビュアーの理解を最大化することに関するものです。だからこそ、エコシステムは複数のアルゴリズム（マイヤーズ、ペイシェンス、ヒストグラム）、複数のプレゼンテーション（ユニファイド、単語diff、色付き移動）、およびドメイン対応ツール（テーブル用のdaff、バイナリ用のxdelta/bsdiff）を進化させました。トレードオフを学び、ノブを調整すれば、意図について推論する時間が増え、赤と緑の線からコンテキストを再構築する時間が減ります。