2つの文章を比較するプログラムは、人間のように文章を読んで「何が変わったか」を判断しているわけではありません。代わりに、2つのリストの間で、できるだけ少ない削除と追加で一方をもう一方に変える方法を探します。この記事では、diff がその答えをどのように計算するのか、そして結果がときどき人の期待と違って見える理由を説明します。
比較の単位：行・単語・文字
diff はまずテキストをトークンのリストに分けます。従来の diff や git は1行を1つのトークンとして扱います。そのため、1行の中で1文字だけ変わっても、その行全体が「1行削除＋1行追加」として表示されます。
行単位の比較は高速でコードレビューに向いていますが、長い段落が1行に続いている文書では、どこが変わったのかを見つけにくくなります。そこで多くのツールは2段階で比較します。
- 行単位で比較し、変更された行を見つける。
- 変更された行どうしをペアにして、その中を単語や文字の単位でもう一度比較する。
このサイトも同じ方式を使っています。行内比較の単位は、単語・空白区切り・文字から選べます。
最長共通部分列（LCS）
diff の数学的な核心は最長共通部分列（Longest Common Subsequence、LCS）です。部分列とは、順序を保ったまま一部の要素を取り出したものです。たとえば ABCABBA と CBABAC の共通部分列のうち最も長いものは長さ4で、CABA や BABA がその例です。
LCS に含まれる要素は「そのまま残ったもの」で、それ以外は「削除されたもの」（左側にだけある）か「追加されたもの」（右側にだけある）です。LCS が長いほど、削除と追加は少なくなります。2つのリストの長さを N、M、LCS の長さを L とすると、必要な削除と追加の合計 D は次のとおりです。
D = (N - L) + (M - L)上の例では N=7、M=6、L=4 なので、D = 3 + 2 = 5 です。この D を（挿入と削除だけを許した場合の）編集距離と呼び、削除・追加のリストを編集スクリプトと呼びます。
編集グラフと Myers アルゴリズム
LCS を教科書どおりの方法（動的計画法）で求めると、N×M の大きさの表が必要です。1万行どうしを比較すると1億マスになり、遅いうえにメモリも多く使います。1986年、Eugene W. Myers は論文「An O(ND) Difference Algorithm and Its Variations」でより高速な方法を示し、これが今日の GNU diff や git の標準アルゴリズムの土台になりました。
Myers は比較を格子上の最短経路探索に置き換えます。
- 左上 (0,0) から右下 (N,M) まで進みます。
- 右へ1マス＝左のテキストの要素を1つ削除、下へ1マス＝右のテキストの要素を1つ追加。コストはそれぞれ1です。
- 2つの要素が等しいマスでは、斜めにコストなしで進めます。このように続く斜めの区間を snake と呼びます。
コストが最も小さい経路が、すなわち最も短い編集スクリプトです。Myers アルゴリズムは「コスト0で行ける最も遠い地点」「コスト1で行ける最も遠い地点」…と順に範囲を広げていき、終点に届いたところで止まります。各段階では対角線ごとに最も遠くまで進んだ位置を1つ覚えておけばよいので、かかる時間はおおよそ (N+M)×D に比例します。2つのテキストがほとんど同じなら D が小さいため非常に速く、まったく違えば遅くなります。
線形メモリと middle snake
経路をたどり直すには段階ごとに記録を残す必要があるため、メモリが D² に比例して増えることがあります。Myers は同じ論文で、先頭から進む探索と末尾から逆向きに進む探索を同時に行い、両者が出会う斜めの区間（middle snake）を見つける変形も示しました。その地点を境に問題を2つの小さな問題に分けて繰り返せば、メモリは入力の大きさに比例する分だけで済みます。
コストが大きすぎるとき：近似ヒューリスティック
2つの入力が数万行あり、互いに大きく異なると D も大きくなり、(N+M)×D が数十億に達することもあります。GNU diff はこうした場合に備え、探索の段数が一定の上限を超えると、それまでに最も遠くまで進んだ対角線で問題を切り分けるヒューリスティックを備えています。結果は正しい編集スクリプトのままですが、最短である保証はありません。GNU diff や git の --minimal オプションを使うと、時間がかかっても最小の結果を探します。
最小が常に読みやすいとは限らない
編集距離が同じ経路が複数あることもあります。たとえばコードに関数を1つ追加すると、閉じ波かっこ } や空行があちこちにあるため、アルゴリズムが「新しい関数の }」を「既存の関数の }」とペアにしてしまうことがあります。結果は最小でも、人が見ると不自然です。git がインデントを手がかりに境界をずらすヒューリスティックを標準で使い、patience や histogram といった別のアルゴリズムを用意しているのはこのためです。詳しい比較は diff アルゴリズムの比較で扱います。
このツールでは
このサイトの比較エンジンは、Myers アルゴリズムの線形メモリ版を JavaScript で実装しており、入力が大きいと GNU diff と同じ方式の近似分割に切り替わります。計算は Web Worker で実行されるため、大きなファイルを入れても画面が固まりません。行単位の結果が出ると、変更された行どうしで内容が似ているものをペアにして「変更」と表示し、その中を選んだ単位（単語・空白区切り・文字）でもう一度比較して強調します。
実際に2つのテキストを入れ、行内比較の単位を切り替えながら結果がどう変わるかを テキスト比較ツールで確かめてみてください。結果を git 形式で読む方法は unified diff の読み方を参照してください。