テキスト差分ツール

比較の計算方法

両方のテキストを行に分け、共通する行を最長共通部分列として求めます。Unixのdiffコマンドの土台になっているのと同じ考え方です。部分列に含まれる行はそのままの位置に残り、残りは左側から削除された行、または右側に追加された行として報告されます。削除と追加が隣り合った場合は、無関係な2つの出来事ではなく、1つの変更としてペアにして表示します。

変更されたペアはさらに単語単位でもう一度比較されるので、長い行の中で数字が1つだけ変わった場合は、行全体を赤くするのではなくその数字を強調表示します。これが読める差分と目を凝らさなければならない差分の違いであり、行単位のツールが文章や設定ファイルでは役に立たないと感じられる理由でもあります。

その前に、先頭と末尾の同じ行はあらかじめ取り除きます。そのため、1か所だけ異なる1,000行のファイル2つは、ほんの数行の比較として処理され、速く、しかもわかりやすくなります。

同じに見える2行が異なると判定されるとき

最もよくある驚きで、原因は常に目に見えない文字です。多いのは行末の空白で、これを無視する設定が既定でオンになっているのはそのためです。次が改行コードで、Windowsで書かれたファイルは行末がCR+LF、macOSやLinuxで書かれたファイルはLFだけなので、生のバイト列で比べる差分ではすべての行が変更されたことになります。

その次は、タブと連続したスペースの違い（空白を無視するオプションでまとめられます）。ワープロや一部のWebページが通常のスペースの代わりに入れるノーブレークスペース。自動修正で置き換えられた全角風の引用符やダッシュ。そして1行目の先頭に見えないまま居座るBOMです。どれも、画面上では同じに見える2行を、ファイルの中では本当に異なるものにしてしまいます。

サイズの上限

最長共通部分列の計算量は2乗です。m行とn行を比較すると、m×nの表を埋めることになります。数百行なら些細なものですが、1万行と1万行なら1億セルになり、表を埋めている間ページが応答しなくなります。

そのため、共通する先頭と末尾を取り除いた後の比較には400万セルという上限を設けており、それを超える比較は試みずにメッセージを表示して断ります。実際には、おおむね似ている限り数千行のファイルでも即座に比較でき、上限に達するのは本当に無関係な大きなドキュメント同士だけです。その場合は、ストリーム処理できるコマンドラインのdiffが適した道具です。

左右並べて表示と統合表示

左右並べて表示は2つのバージョンをそれぞれの列に置くので、文章や翻訳など、両方のテキストを文章として読みたいものに向いています。統合表示は記号を付けて交互に並べる、パッチやコードレビューで使われる形式で、長いファイルのあちこちに小さな変更が散らばっている場合に追いやすくなります。

どちらの表示でも計算結果は変わりません。同じ結果を2通りに見せているだけです。

差分アルゴリズムの中身

古典的な手法は1986年に Eugene Myers が発表したもので、2つの系列のあいだの最短編集スクリプト、つまり一方を他方に変えるのに必要な挿入と削除の最小の組を求めます。Unix の diff コマンドや Git の既定の実装が使っているのがこれで、変更点の数が最も少なくなるという意味では最適です。

ただし、変更が最少であることが最も読みやすいとは限りません。Myers 法は、たまたま一致しただけの無関係な行、たとえばここの閉じ括弧やあそこの空行を対応付けてしまい、片方の関数が削除されもう片方が追加されたと見せる代わりに、2つの関数が入り混じった差分を作ってしまうことがあります。Git の patience アルゴリズムはこれに対処するもので、両方のバージョンにちょうど1回だけ現れる行をアンカーにし、アンカーのあいだを再帰的に処理します。その結果はたいてい、読み手が本当の対応だと考えるものと一致します。

histogram アルゴリズムは現在 Git が推奨する代替手段で、patience に出現頻度のヒューリスティックを加えたものであり、大きなファイルではより高速です。コードレビューの差分がどうにも意味不明に見えるときは、diff.algorithm を histogram にすると、まったく同じ2つのファイルからより分かりやすい結果が得られることがよくあります。

2者間の差分と3方向マージ

2つのファイルを比べれば、何が変わったかは分かります。マージにはもう一つの入力、つまり共通の祖先が必要です。それがなければ、どちらの側が行を変更し、どちらが元のままなのかを判断する方法がないからです。バージョン管理がマージベースを保持しているのも、3方向マージツールがペインを3つ表示するのも、そのためです。

コンフリクトは、その祖先を基準にして両方の側が同じ箇所を変更したときに発生します。それ以外はすべて自動的にマージされます。隣接しているが重なってはいない変更も含まれます。だからこそ、2人が同じファイルを一日中編集していても衝突せず、そのあと1行だけでぶつかる、ということが起こります。

これが分かるとコンフリクトの解決の仕方が変わります。コンフリクトしたファイルのマーカーは自分の版と相手の版を示しますが、本当に役立つ問いは、ベースを基準にそれぞれの側が何をしようとしていたのかです。git checkout --conflict=diff3 を使うとマーカーにベースも加わり、2つの選択肢のどちらかを当てずっぽうで選ぶ作業が、たいていは自明な解決へと変わります。

テキストの行ではないものを比較する

行ベースの比較は、行の区切りに意味があることを前提にしています。minify された JavaScript、1行にまとめられた JSON ペイロード、長い散文の段落は、どれもその前提を壊します。1文字変わっただけで、行全体が違うと報告されるのです。両方を先に整形して出力すれば、差分に必要な構造が戻ります。JSON なら、キーをソートしインデントをそろえた正規形にすることで、比較がたまたまの結果ではなく意味のあるものになります。

CSV は逆の問題を抱えています。行ベースの差分は動きますが、列の並べ替えを全行の変更として報告してしまいます。先にキーとなる列でソートするか、CSV を理解するツールを使えば、気にすべき変更をノイズから切り分けられます。

バイナリやそれに近い形式には、それぞれ専用の変換が必要です。.docx は XML を集めた zip で、ノートブックは出力を埋め込んだ JSON、PDF はほぼ中身が見えません。Git には差分を取る前にファイルをテキストへ変換する textconv フィルターがあり、これのおかげでチームは、コピーをもう一つ保存しなくても文書やノートブックの読める差分を得られます。

他人が書いた差分を読む

レビューしやすい差分は、その中に何が入っていないかで決まる部分が大きいです。フォーマット由来のノイズ、たとえばファイル全体へのフォーマッタの適用、改行コードの変更、import の並べ替えは、重要な3行を、どうでもいい300行の下に埋めてしまいます。ふつうの対処法は、機械的なコミットと本質的なコミットを分けて、それぞれを適した速度で読めるようにすることです。

それでも混ざった差分を渡されたときは、空白を無視する比較が最短の抜け道です。git diff -w か、ここにある無視オプションを使います。ただし承認する前には必ず戻してください。ファイルによっては空白が内容そのものだからです。Python のインデント、YAML の構造、Makefile のタブ、そして出力の完全一致を検証するテストがそれにあたります。

もう一つ意識して扱う価値があるのが、大規模なリネームです。移動して編集されたファイルは、ツールがリネームを検出しない限り、削除と追加として現れます。Git の -M フラグや、リネームを理解するレビュー画面を使えば、1000行の差分が、実際に変わった10行に戻ります。

編集作業としてのテキスト比較

差分はコードのためだけのものではありません。契約書の2つのドラフト、2つの翻訳、あるいは編集前後の文書を比べるのはよくある用途で、左右に並べて表示するビューはそのためにあります。パッチとしてではなく、文章として両方を読みたいからです。

散文では、単語単位のハイライトが価値の大半を担います。書き直された文が、削除された1行と追加された1行ではなく、書き直された文として見えるからです。行の内側でこれをうまくやれるツールこそが、編集作業に使えると感じられるものです。ここでの比較が、変更のあった行の組ごとに単語単位の2回目のパスを走らせているのは、そのためです。

文書について実務的な注意が2つあります。ワープロからコピーした文章には、もう一方のコピーにはない丸い引用符、エヌダッシュ、ノーブレークスペースが紛れていることが多く、見た目は同じなのに差分が出ます。もう一つ、同じ原稿から2回書き出した文書が改行の入り方だけで違ってしまうこともあり、比較の前に改行コードを正規化しておくと、多くの混乱を避けられます。