UNIXの基本的なコマンドの1つであるdiff。
これに実装されているアルゴリズムは実に興味深い世界が広がっています。
本稿では,
本記事は,
はじめに
diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。
ソフトウェア開発を行っている方であれば,
差分の計算の際に重要な3つの要素
差分を計算するというのは次の3つを計算することに帰結します。
- 編集距離
- 2つの要素列の違いを数値化したもの
- LCS
(Longest Common Subsequence) - 2つの要素列の最長共通部分列
- SES
(Shortest Edit Script) - ある要素列を別の要素列に変換するための最短手順
dtlを使って文字列の差分を計算する
本稿ではdtlというdiffライブラリとそのサンプルプログラムを利用して,
dtlのサンプルプログラムのビルドにはSCons
$ sudo aptitude install scons
また,
$ 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つの文字列の差分を計算してみます。
たとえば,
図1 strdiffの実行結果
$ ./strdiff abcdef dacfea editDistance:6 --------① LCS:acf --------② SES ---┓ + d | a | - b | c |③ - d | - e | f | + e | + a ---┛
まず,
- 注1)
- 執筆時点での最新版は1.
12です。 - 注2)
- Python製のビルドツール。
LCS(Longest Common Subsequence)
LCSは最長共通部分列であると書きましたが,
「d」
たとえば,
「e」
このように,
SES(Shortest Edit Script)
図1の結果からSESは③のようになりました。SESは先述したように
表1 abcdefからdacfeaへのSES
- 「追加」
の場合はマークしている文字の前に追加対象の文字を追加 - 「削除」
の場合はマークしている文字を削除 - 「LCSの要素」
の場合はマークしている文字から右に一文字進める
編集距離
表1から読み取れるように編集距離とはSESにおける要素の