行単位でのファイルの比較
図3に示すサンプルプログラムのFileStringEditDistanceでは、同じアルゴリズムを使って2つのファイルを文字単位で比較しています。FileStringEditDistanceプログラムは、ファイルどうしを比較するうえでそれなりに役立ちます。図3を見ると、どの文字が追加または削除されたかを簡単に判別できます。
しかし困ったことに、FileStringEditDistanceプログラムには大きな欠点があります。それは、大量のメモリを消費することです。図3で使われているファイルのサイズは比較的小さいものの、2,500を超える文字数が含まれるため、編集グラフの配列には650万を超えるエントリが格納されます。私の著書では、1つの章に5万を優に超える文字数が含まれることがあります。そのようなファイルの2つのバージョンを表す編集グラフには、実に25億を超えるエントリが格納されることになります。これでは大量のメモリが消費されるだけでなく、グラフの作成に膨大な時間がかかってしまいます。
幸い、ファイルを行単位で比較するようにアルゴリズムを変更するのは簡単です。2つの文字列を2つの文字列の配列に置き換えるだけで済みます。2つの文字列内の文字を比較する代わりに、2つの文字列の配列内の文字列を比較します。図4に示すFileLineEditDistanceサンプルプログラムでは、この方法を使ってファイルを行単位で比較しています。
サンプルをダウンロードしてテキストファイルを参照し、相違点を確認してください。実際、図4に示すように、FileLineEditDistanceプログラムを使ってファイルどうしを比較できます。
差分比較のバリエーション
サンプルをダウンロードして実際に試してください。そしてもし余力があれば、サンプルに手を加えてみてください。さまざまなバリエーションを試す余地があります。
例えば、サンプルでは編集グラフを通る最短経路が1つだけ検出されますが、それは必ずしも最良の経路とは限りません。例として、文字列BBBBCとBCの相違点を見つけたいとします。StringEditDistanceプログラムでは、中間の一連のBが削除されてBBBBCという結果が得られますが、先頭の一連のBを削除して、BBBBCのように残りの2文字をまとめて残した方が望ましい場合があります。
FileLineEditDistanceプログラムのバリエーションとしては、行を比較して、行が相違している場合に、その行に含まれるテキストを比較するという処理が考えられます。結果はFileStringEditDistanceプログラムで得られる結果とほとんど変わりませんが、巨大な編集グラフを構築せずに済みます。
FileLineEditDistanceプログラムのよくあるもう1つのバリエーションは、2つのファイルを横に並べて表示し、対応する行を強調表示するという処理です（Visual Source Safeの差分比較ツールで行われている方法です）。
ファイルをすべてソース管理システムで保管している場合や、Microsoft Wordの変更履歴システムが気に入っている場合は、こうしたテクニックが必要になることはないでしょう。しかし、その範疇に入らないファイルでは、これらの手段が役に立ちます。アプリケーションにこの機能を追加すれば、ユーザーはバージョンの異なるスクリプト、メモ、その他のテキスト間の変更箇所を簡単に見つけることができるようになります。
