diffの動作原理を知る~どのようにして差分を導き出すのか

この記事を読むのに必要な時間:およそ 7 分

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

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

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

本記事は,Software Design 2009年6月号の記事を,現在の状態に合わせて加筆/修正しています。

はじめに

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を計算してその結果を出力してくれます。

図1 strdiffの実行結果

$ ./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 abcdefからdacfeaへのSES

表1 abcdefからdacfeaへのSES

  • 「追加」の場合はマークしている文字の前に追加対象の文字を追加
  • 「削除」の場合はマークしている文字を削除
  • 「LCSの要素」の場合はマークしている文字から右に一文字進める

編集距離

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

著者プロフィール

久保達彦(くぼたつひこ)

インフラ兼ソフトウェアエンジニア。ピクシブ株式会社所属。

pixivのインフラの最適化や運用の省力化を提案・実行する傍らレコメンド・エンジンなどのソフトウェアの開発も行っている。

HP:http://cccis.jp/

twitter:@cubicdaiya

バックナンバー

プログラミング

コメント

  • 図8のキャプション

    間違ってたら申し訳ありませんが、図8のキャプションが間違ってませんか?
    図8 fp(k,p)=snake(k,fp(k-1,p"))
    ではなく
    図8 fp(k,p)=snake(k,fp(k+1,p"))
    では?

    Commented : #1  上田拓也 (2012/11/02, 16:19)

コメントの記入