Gitはどのように変更を見つけるのか？（Diffアルゴリズム）

git diff は、すべての開発者が毎日使用するコマンドです。

何千行ものコードの中から、どの行が追加または削除されたかを瞬時に正確に見つけるのは驚くべきことではありませんか？

単に2つのファイルを1行ずつ比較しているだけでしょうか？もしそうなら、途中に1行挿入するだけで、それ以降のすべての行が「変更された」とマークされてしまいます。

Gitは、Myers Diffアルゴリズム と呼ばれる賢い方法を使用して、「最小限の変更セット」を見つけます。

1. 編集距離

2つの文字列（またはファイル）間の違いを計算する問題は、「AをBに変換するために必要な最小の編集回数」を見つけることに帰着します。これを 編集距離 と呼びます。

例えば、ABC を ABD に変更する場合：

Gitはこの計算を文字ごとではなく、行ごと に行います。

Myersアルゴリズムの核心は、2つのファイル間の 最長共通部分列 (LCS) を見つけることです。

LCSが見つかれば、残りは簡単です。

例えば：

ここで、LCSは 1 3 4 です。
したがって、2 が削除され、5 が追加されたと推測できます。

1986年にEugene W. Myersによって発表されたこのアルゴリズムは、LCS問題をグラフ探索問題（最短経路を見つける）に変換し、非常に効率的に解決します。

Gitはデフォルトでこのアルゴリズムを使用しますが、オプションとして histogram や patience などの他のアルゴリズムも提供しています。

私たちが当たり前のように思っている + と - の記号の背後には、30年以上にわたって証明されてきたエレガントな数学的アルゴリズムがあります。

git diff の出力が混乱していたり乱雑だと感じる場合は、git diff --algorithm=histogram を試してみてください。多くの場合、コードの構造をよりよく反映した結果が得られます。