一般記事

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

初出：Software Design2009年6月号（2009年5月18日発売）

diff, アルゴリズム, UNIX

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

Wuのアルゴリズムの問題点

Wuのアルゴリズムは2つの要素列が似通っている場合，非常に高速に動作しますが，そうでない場合は探索する範囲が広くなった分遅くなり，SESを求めるために記録する経路のサイズも大きくなります。今回のように比較対象となる要素列が短い文字列であればとくに問題ではないのですが，万単位の行からなるファイル同士を比較したりするとなると，実装によっては実用上使い物にならないくらい遅くなったり，メモリを大量に消費するようになってしまう可能性があるので，工夫が必要になります注9。

注9）
リスト1のように編集距離だけを求めるのであれば，探索する範囲は広くなっても，メモリの消費はさほど大きくなりません。問題となるのはSESの経路記録です。

その他のアルゴリズム

本稿ではWuのアルゴリズムについて解説しましたが，ここでは他のアルゴリズムについて軽く紹介します。

動的計画法（Dynamic Programming）

動的計画法（以下，DP）とはひとつひとつの小さな問題の解を組み合わせて，より大きな問題を解くというもので，diffに限らずいろいろな応用ができるアルゴリズムです。DPを使った差分の計算における小さな問題の解とは，2つの要素列の先頭からの各部分列におけるLCSの長さです。各部分列のLCSの長さは各一要素分前の部分列のLCSの長さがわかっていれば計算することができるので，先頭からの各部分列のLCSの長さを全部求めていけば最終的にもとの2つの要素列のLCSの長さが求められます。

また，各部分列のLCSの長さを求める過程で，どの部分列を選択したかという情報も保存します。

最後にこの情報を逆順にたどっていけば，編集距離，LCS，SESを求めることができます。

DPを使った差分の計算では単純に各部分列のLCSの長さを保存しようとすると，M×N（M, Nはそれぞれの要素列の長さ）の表が必要になるので計算量がO(MN)，計算に必要なメモリもM×Nになります。

Myersのアルゴリズム

MyersのアルゴリズムはWuのアルゴリズムと同じく，差分の計算問題をエディットグラフ上の最短経路問題に還元するアルゴリズムです。Dは編集距離を表しており，Wuのアルゴリズムと同じような感じで探索範囲を-D<=k<=Dに絞り込むことによって，計算効率を向上させています。

GNU diffutilsや分散型バージョン管理システムの1つであるGitのdiffエンジンとして採用されているXLibdiffの実装はこのアルゴリズムを基にしています（注10⁠）⁠。

注10）
P≦Dなので，素のMyersのアルゴリズムはWuのアルゴリズムよりも計算コストが高いですが，これらの実装ではMyersのアルゴリズムに差分をヒューリスティックに求める改良を施して，精度を落とす代わりに計算速度を向上させています（ここで言う「精度を落とす」とは，「⁠最短経路ではない経路で解を求める」という意味で，「⁠差分の解析結果の精度を落とす」という意味ではありません⁠）⁠。実際，dtlやSubversionのdiffエンジンよりもこれらの実装のほうが計算速度は速いです。

Gestalt Approach

Gestalt ApproachはWuのアルゴリズムやMyersのアルゴリズムと違い，差分の計算問題をエディットグラフ上の最短経路問題に還元するのではありません。2つの要素列中の連続する共通部分を探し出し，その共通部分を中心に2つの要素列をそれぞれ分割します。そして，その分割した2つの要素列の左部分と右部分のそれぞれから再び共通部分を探し出すといったことを繰り返し，最後にその共通部分を全部つなげてLCSなどを算出するというアルゴリズムです。

最後に

本稿のサンプルコードでは，編集距離を求めるところまでしか紹介できませんでしたが，興味のある方は本稿でも紹介した拙作のdtlやGNU diffutilsまた各種バージョン管理システムのソースコードに含まれているdiffエンジンのソースコードを読んでみると良いでしょう。また，githubに筆者が各種言語でWuのアルゴリズムを利用して実装した差分計算プログラムのソースコードがあります。

コラム「dtl開発の苦労話」

筆者はdtlを開発しているとき，本稿にある「Wuのアルゴリズムの問題点」に思いっきり当たりました。あるとき，数千もしくは数万行からなるまったく内容の違う2つのファイルを比較すると動作が非常に遅くなったり，プログラムがメモリ不足で落ちてしまったりといった現象に出くわしたのですが，最初は原因がわかりませんでした。そして詳しく調べてみると，全然違うファイルを比較した場合，SESを求めるのに必要な経路の座標候補を記録している（動的）配列のサイズがとんでもない数になっていることに気づきました（注A⁠）⁠。

プログラムではWuのアルゴリズムの経路探索の過程でその配列にSESの経路候補の座標を追加していき，最後に，その記録された座標から経路を逆にたどっていくことによってSESを算出していたのですが，最終的にどの経路がSESになるかというのは経路探索の途中ではわからないため，どうやって解決したものかと悩んだ記憶があります。

少々悩んだあと，私が取った解決策は，次のようなものです。

  • ① SESの座標候補の配列に座標を追加していく
  • ② SESの座標候補の配列のサイズが一定のサイズになったら，いったんそこまでのLCSやSESを計算する
  • ③ 座標候補の配列を空にする
  • ④ 2つの要素列の比較が最後まで終わっていない場合は①に戻る。終わっている場合は⑤へ
  • ⑤ これまでに計算した複数のLCSやSESを全部つなげて1つにする

この方法により，全然違う要素列を比較する場合でも計算に必要な経路情報を一定のサイズ以下に抑えることができ，問題は発生しなくなりました。ただ，当然，このようなことをすると完全なLCSやSESを求めることができない可能性が出てきます。

しかし，実際問題として完全なLCSやSESが必要となるケースはそれほど多くなく，ふだん使われているようなdiffのプログラムでも近似アルゴリズム（注B）を使って，つねに最適解を求めるのではなく，計算速度を優先させて準最適解を求めるような実装になっているのが見受けられます。

注A）
OSに付属のプロセスモニタを見ると，dtlを使ったプログラムのメモリ使用量が1Gバイトを越えていました。
注B）
近似アルゴリズムについて詳しく勉強したい方は参考文献の『近似アルゴリズム』が参考になるかもしれません。
参考文献・URL
  1. E.W.MYERS, "An O(ND) Difference Algorithm and Its Variations"
  2. Sun Wu, Udi Manber, G.Myers, W.Miller, "An O(NP) Sequence Comparison Algorithm"
  3. 『アルゴリズムイントロダクション「第2巻」アルゴリズムの設計と解析手法 改訂2版』
    T.コルメン，C.ライザーソン，R.リベスト，C.シュタイン共著／浅野哲夫，岩野和生，梅尾博司，山下雅史，和田幸一共訳／近代科学社／ 987-4-7649-0335-7
  4. 『近似アルゴリズム』V.V.ヴァジラーニ著／浅野孝夫訳／シュプリンガー・ジャパン／987-4-4317-00991-6
  5. PATTERN MATCHING:THE GESTALT APPROACH
    URL：http://www.ddj.com/184407970?pgno=5
  6. 文書比較アルゴリズム
    URL：http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm
  7. Webサイト「/0」内の記事――diff(1)，diff(2)，diff(3),
    URL：http://www.slash-zero.jp/archives/program/466
    URL：http://www.slash-zero.jp/archives/program/468
    URL：http://www.slash-zero.jp/archives/program/476
  8. 各種言語(C, Go, Java, Lua, Perl, Python, Ruby)によるWuのアルゴリズムの実装
    URL：https://github.com/cubicdaiya/onp

diff, アルゴリズム, UNIX

著者プロフィール

久保達彦（くぼたつひこ）

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

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

HP：http://cccis.jp/

twitter：@cubicdaiya

バックナンバー

プログラミング