UNIXの基本的なコマンドの1つであるdiff。

これに実装されているアルゴリズムは実に興味深い世界が広がっています。

本稿では，筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。

はじめに

diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。

ソフトウェア開発を行っている方であれば，SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。

差分の計算の際に重要な3つの要素

差分を計算するというのは次の3つを計算することに帰結します。

編集距離

2つの要素列の違いを数値化したもの

LCS（Longest Common Subsequence）

2つの要素列の最長共通部分列

SES（Shortest Edit Script）

ある要素列を別の要素列に変換するための最短手順

dtlを使って文字列の差分を計算する

本稿ではdtlというdiffライブラリとそのサンプルプログラムを利用して，これらの用語について具体的に解説します。dtlはdiff template libraryの略で，筆者が開発しているC++製のdiffライブラリです（注1⁠）⁠。

dtlのサンプルプログラムのビルドにはSCons（注2）を使用しているので，まずはSConsをインストールしてください。DebianやUbuntuであれば次のコマンドでインストールできます。

$ sudo aptitude install scons

また，C++プログラムをコンパイルするために，次のパッケージもインストールします。

$ sudo aptitude install build-essential

その後，次のコマンドを実行してください。

$ wget http://dtl-cpp.googlecode.com/files/dtl-1.12.tar.gz
$ tar zxvf dtl-1.12.tar.gz
$ cd dtl-1.12/examples
$ scons strdiff

これで準備が整いました。dtlのサンプルプログラムの1つであるstrdiffを使って2つの文字列の差分を計算してみます。

たとえば，「⁠abcdef」と「dacfea」という文字列があるとしましょう。strdiffにこの2つの文字列を引数として与えて実行すると，図1のようにeditDistance（編集距離⁠）⁠，LCS，SESを計算してその結果を出力してくれます。

$ ./strdiff abcdef dacfea
editDistance:6 --------①
LCS:acf --------②
SES  ---┓
+ d     ｜
  a     ｜
- b     ｜
  c     ｜③
- d     ｜
- e     ｜
  f     ｜
+ e     ｜
+ a  ---┛

まず，①のeditDistance（編集距離）の説明からいきたいところですが，これは③のSESと関連するため，先に②のLCSについて解説し，そのあとで残りの2つをまとめて解説します。

注1）

執筆時点での最新版は1.12です。

注2）

Python製のビルドツール。

LCS（Longest Common Subsequence）

LCSは最長共通部分列であると書きましたが，単に2つの要素列に共通して含まれる要素の列ではなく，2つの要素列の中で共通する部分で最も長い列を指します。つまり，LCSはつねに連続しているわけではありませんが，もとの要素列の順序どおりに並んでいる必要があります。これはどういうことかと言うと，「⁠abcdef」と「dacfea」に共通して含まれる文字は「a⁠」⁠，「⁠c⁠」⁠，「⁠d⁠」⁠，「⁠e⁠」⁠，「⁠f」の5つになります。これに対して，図1の結果を見ると，2つの文字列「abcdef」と「dacfea」のLCSは「acf」でした。

「d」と「e」がLCSに含まれていないのは，この2つの文字がLCSに含まれてしまうと，もとの文字列のどちらかの順序どおりに並ばなくなるからです。

たとえば，要素「d」は文字列「abcdef」では，LCSの要素である「a」と「c」よりも後ろに出現し，そのあとは出現しません。これに対して文字列「dacfea」では「a」と「c」よりも前にだけ出現します。

「e」と「f」についても，「⁠abcdef」と「dacfea」とでは順序が逆になってしまうため，両方がLCSに含まれることはあり得ません。逆に，片方だけが含まれるLCSは存在します。というのも，図1の結果ではLCSは「acf」になっていますが，「⁠ace」もまたLCSです。「⁠acf」も「ace」も長さは3で同じなので，どちらもLCSであると言えます。

このように，LCSはつねに1つとは限りません。また，LCSが変わると後述するSESも変わってしまうので，注意が必要です。

SES（Shortest Edit Script）

図1の結果からSESは③のようになりました。SESは先述したように「ある要素列を別の要素列に変換するための最短手順」を表します。つまり，③は「abcdef」という文字列を「dacfea」という文字列に変換するための最短手順を表しています。ふだんdiffを使っている人にとっては，これが一番なじみの深いものではないかと思います。③のSESをもう少し詳細にすると，表1のようになります。

編集距離

表1から読み取れるように編集距離とはSESにおける要素の「追加」と「削除」の合計を表しています。図1の①を見るとeditDistance（編集距離）は6ですので，計算どおりです。