はじめに
私と同様に大量の文章を書く人なら、Microsoft Wordの変更履歴機能のことはよくご存じでしょう。この機能を利用すると、バージョンの異なるWordファイル間でどの箇所が変更されたかを簡単に見分けることができます。
しかし、プレーンテキストファイルで変更箇所を知りたいときはどうすればよいでしょうか。バージョンの異なるデータファイルどうしを比較したい場合はどうでしょうか。また、プロジェクトが単体テストを通過しなくなった場合に、前の週にソースコードファイルのどの箇所が変更されたかを調べるにはどうすればよいでしょうか。
ファイルの変更管理を実施していれば話は簡単です。きちんとした変更管理システムなら、バージョンの異なるファイル間の変更箇所を強調表示してくれるからです。ファイルの変更管理を実施していない場合や、変更管理の仕組みを理解したいと考えている場合は、変更箇所を調べるためのツールを自分で作成してみましょう。
本稿では、2つのドキュメントや2つの文字列を比較して変更箇所を調べる方法を紹介します。相違点を見つけるためのアルゴリズムについて説明し、C#とVisual Basicで書かれたサンプルを示します（いずれもダウンロード可能です）。
編集距離
本稿の最終的な目標は、2つのドキュメントがどの程度相違しているかを調べることですが、これから説明するアルゴリズムは2つの文字列を使って考えた方が理解しやすいので、そこから始めることにします。2つの文字列の相違点を見つける方法が分かれば、それを応用して、2つのドキュメントの相違点を見つけることや、文字、段落などで構成される2つのファイルの相違点を見つけることもできるようになります。
2つの文字列の相違点を調べる場合に、実際に必要なのは最小差分を得ることです。もちろん、元の文字列の文字をすべて削除し、別の文字列の文字をすべて挿入して新しい文字列にすることも可能です。これで新しい文字列ができますが、この方法は2つの文字列の関係を把握するにはあまり役に立ちません。2つの文字列の中に共通する文字が多く含まれていた場合、この方法では、変換によって文字列のどの箇所が「変更された」かが分かりません。
例えば、「cat」を「cart」に変換する場合、c、a、tを削除してから、c、a、r、tを挿入することも可能ですが、この操作には7つの変更が必要です。この場合は、単純に「cat」に「r」を挿入し、1つの変更で「cart」に変換する方がはるかに簡単です。こうすれば、2つの文字列のどの箇所が変更されたかをより正確に判別できます。
編集距離は、2つの文字列が相違している度合い（相違度）を示す尺度です。編集距離を定義する方法はいくつかありますが、本稿では、単に文字列の変換に必要な削除操作と追加操作の最小回数として考えます。例えば、「cat」と「cart」の間の編集距離は1になります。
catからcartへの変換のような単純なケースでは、編集距離を推測するのは簡単です。しかし類似点が少ない文字列どうしでは、最良解を見つけることが少し難しくなります。例えば、「parsnip」を「turnip」に変換する1つの方法は次のとおりです。
- arsnip（「p」を削除）
- rsnip（「a」を削除）
- trsnip（「t」を挿入）
- tursnip（「u」を挿入）
- turnip（「s」を削除）
ここから5という編集距離が得られますが、これは最良解なのでしょうか。文字を見ても、どのように変更すれば最良の結果が得られるかがすぐに分かるとは限りません。
編集距離を簡単に調べる1つの方法は、編集グラフを使うことです。編集グラフには、文字列を変換する際に取り得る手順が示されます。図1に、parsnipをturnipに変換する場合の編集グラフを示します。
このグラフを作成するには、図1に示すようにノードの配列を作成します。元の文字列の文字を最上部に横方向に記述し、変換後の文字列の文字を左側に縦方向に記述します。それぞれの丸（ポイント）について、すぐ下とすぐ右のポイントに接続するリンクを描きます。
グラフ内で、両方の文字列内で同じ文字に対応しているポイントを一致ポイントと呼びます。例えば、「parsnip」と「turnip」にはどちらも「r」という文字が含まれるので、「parsnip」の「r」の下にあり、「turnip」の「r」の右にあるノードが一致ポイントになります。図1では、一致ポイントがピンク色で示されています。
編集グラフを仕上げるには、図1に示すように、左上にあるノードからそれぞれの一致ポイントに到達するリンクを追加します。
最初は分かりにくく見えますが、実際にはこのグラフは極めて単純です。目標は左上から右下隅に向かって経路をたどることです。右方向への移動は、それぞれ元の文字列から文字を1つ削除する操作に対応します。図1で、青色の経路の開始点から右方向に2つ移動していますが、これは「parsnip」から「p」と「a」を削除する操作に対応しています。
下方向への移動は、それぞれ新しい文字列に文字を1つ挿入する操作に対応します。図1では、引き続き青色の経路に沿って下方向に2つ移動していますが、これは文字列に「t」と「u」を挿入する操作に対応しています。
斜め方向への移動は、文字をそのまま残す操作に対応します。図1では、引き続き青色の経路に沿って斜め方向に移動していますが、これは「r」をそのまま残す操作に対応しています。
これらの規則を使うと、文字列を変換するための編集距離と変更の最小回数を簡単に調べることができます。右および下へのリンクはコスト1、斜めのリンクはコスト0と考えて、編集グラフをたどる最短経路を見つけます。見方を変えると、これは斜めのリンクを最も多く使う経路を見つける必要があるということです。
この観点で見ると、青色の経路が最良解を表していることがすぐに分かります（最短距離が同じになる経路がグラフに複数存在する場合がありますが、この場合は文字列を同じコストで変換する手順が複数あるということです）。
