Levenshtein Distance

Levenshtein Distanceは2つのシーケンスの違いを数値化したもので編集距離とも言います。これは後述するSESにおける要素の「追加」と「削除」の合計数になります。

LCS

LCSはLongest Common Subsequenceの略で、最長共通部分列とも言います。シーケンスの組合せによってはLCSは複数存在する可能性があります。

SES

SESはShortest Edit Scriptの略で、その名のとおり、片方のシーケンスをもう片方のシーケンスに変換するための最小手順を表します。例えば、abc → abdのSESは、

SES # C 共通, D 削除, A 追加
C a
C b
D c
A d

となります。また上記の場合、LCSは「ab」、編集距離は1+1=2(「追加」と「削除」の合計数)になります。

効率的な差分アルゴリズム

差分を計算する方法は古くから研究されており、多くのアルゴリズムが考案されています。差分を計算する典型的な手法としてはDP(動的計画法)がありますが、ここではより効率的なアルゴリズムであるO(ND)、O(NP)、Gestalt Approachの3つについて軽く紹介します。詳細については参考文献やURLを参照してください。

O(ND)

O(ND)という名前ですが、これはそのままO記法による計算量を表しています。Nは比較する二つのシーケンスの長さの合計数、Dは編集距離になります。つまり、2つのシーケンスが似ていればいるほど速くなります。DPの計算量がO(MN)になることを考えると、これはかなり大きな改善と言えるでしょう(M, Nはそれぞれのシーケンスの長さ)。実際にどうやって差分を求めるかですが、O(ND)やO(NP)は差分の問題を最短経路の問題に還元し、片方のシーケンスからもう片方のシーケンスに変換する最短経路を求めます(つまりこれがSESです)。

GNU diffutilsやGit(で使用されているLibXDiff)はこのO(ND)に近似アルゴリズムの改良を加えたものになっています。

O(NP)

O(NP)はSubversionやMonotone(C++で書かれたバージョン管理システム)で使用されているアルゴリズムで、究極的にはO(ND)の2倍高速に動作します。O(ND)と同じく、名前が計算量を表しています。O(ND)と同じく、Nは比較する二つのシーケンスの長さの合計数、またPはSESにおける削除の合計数を表しています。なので、O(ND)と同じく2つのシーケンスが似ていればいるほど速くなります。

Gestalt Approach

Pythonに標準で搭載されているdifflibパッケージで使われているアルゴリズムです。このアルゴリズムはまず最初に2つのシーケンス間の最長一致項を検出した後、その一致項を起点に、文字列を左側と右側に分割し、両側に対してまた最初に戻るということを繰り返すことによってLCSを求めます。このアルゴリズムは実際に実装したことがないので、憶測ですが、2つの文字列間の最長一致項を求めるというのは結構重い処理のはずなので、このアルゴリズムを使った実装ではおそらく、ある程度の長さの一致項を見つけたらそこでさっさと分割してしまって、速度を向上させるといった処置がなされているのではないかと思います。このようにO(ND)やO(NP)とは少し違ったアプローチによって差分を求めているのが特徴です。こちらに解説とアセンブリコードが載っています。また、余談ですが、素晴らしいことにPythonのdifflibにはUnified Formatで差分を出力するためのunified_diffという関数が含まれています。ソースコードを眺めたところ、Mercurialもこのライブラリを使用しているようです(ただし、バイナリdiffに関してはCで書かれています)。

各アルゴリズムの比較

各アルゴリズムのパフォーマンスについては少し前に僕が自分のブログに書いたこちらが参考になるかもしれません。ただ、アルゴリズムの比較というよりは各バージョン管理システムの比較であり、差分計算以外のボトルネックについては全く考慮していませんので、あくまで参考程度に捉えてください。また、差分の計算というのは非常に重い処理であり、現実的な応答時間で計算を終えるためには速度と精度を天秤にかける必要がどうしても生じます(LCS問題はNP-hard)。なので、遅いからといって「これはひどい」とは一概には言えません。逆に計算された差分自体は、非常に精度が高いものである可能性があります。しかし、現実問題として完全なLCSやSESが必要になるということはあまりないため、近似アルゴリズムやヒューリスティクスを用いて完全とはいかなくともそれなりに正しいLCSやSESを得るというアプローチを取る実装が存在します。これが上記でも述べたGNU diffutilsやLibXDiffです。Git内のdiffがSubversionやMonotoneに比べて高速なのはそのためです。

Unified Format

Unified Formatはバージョン管理システムを普段から使用している人なら非常になじみのあるフォーマットです。というのもSubversionやMercurial、Gitなどの比較的新しいバージョン管理システムは、デフォルトではdiffコマンドの出力がUnified Formatになっています(CVSは-uを付ける必要があります)。通常のdiffコマンドだとuオプションを指定するとUnified Formatで表示されます。diffの出力形式としてはほかにContext Formatなどがあります。そういえば今年の春頃、btoさんがdiffで-uを付けない人は勉強が足りてないとぼやいていました。(正直に告白すると、このぼやきを真後ろで聞いていた当時、僕は-uはおろかUnified Formatという言葉すら知りませんでした。それの反省もあって(?)dtlには差分をUnified formatで出力するサンプルプロプログラムが含まれています。)

と、昔話はこれくらいにして、話の続きです。Unified Formatの詳細についてはRFCなどの明確な仕様はありませんが、Wikipediaのdiffの項目やPythonの開発者で有名なグイド・ヴァンロッサム氏の解説が参考になるでしょう。

C++で書かれたdiffライブラリ dtl

dtlはDiff Template Libraryの略で拙作のdiffライブラリです。C++のテンプレートにちなんで名付けています。アルゴリズムにはO(NP)を使用しており、ライセンスは修正BSDライセンスです。動作確認している環境は以下の通りです。

• Mac OS X 10.5.5
• GCC4.3.2
• Ubuntu 7.10 (Paralles Desktop上)
• GCC4.2.1

使い方

dtlは単一のヘッダファイル(dtl.hpp)から成っており、このファイルをインクルードするだけで使うことが出来ます。以下はdtlに含まれているサンプルプログラムであるstrdiff.cppです。

#include "../dtl.hpp"
#include "common.hpp"
#include <iostream>
#include <vector>
#include <cstdlib>
int main(int argc, char *argv[]){
  if (isFewArgs(argc)) {
    perror("few argument.");
    return(EXIT_FAILURE);
  }
  std::string A(argv[1]);
  std::string B(argv[2]);
  typedef char elem;
  dtl::Diff<elem, std::string> d(A, B);
  d.compose();
  // editDistance
  std::cout << "editDistance:" << d.getEditDistance() << std::endl;
  // Longest Common Subsequence
  dtl::Lcs<elem> lcs = d.getLcs();
  std::vector<elem> lcs_v = lcs.getSequence();
  std::vector<elem>::iterator vit;
  std::string lcs_s(lcs_v.begin(), lcs_v.end());
  std::cout << "LCS:" << lcs_s << std::endl;
  // Shortest Edit Script
  std::cout << "SES" << std::endl;
  dtl::Ses<elem> ses = d.getSes();
  std::vector< std::pair<elem, dtl::elemInfo> > ses_v = ses.getSequence();
  std::vector< std::pair<elem, dtl::elemInfo> >::iterator it;
  it = ses_v.begin();
  for (it=ses_v.begin();it!=ses_v.end();++it) {
    switch (it->second.type) {
    case dtl::SES_ADD :
      std::cout << "A " << it->first << std::endl;
      break;
    case dtl::SES_DELETE :
      std::cout << "D " << it->first << std::endl;
      break;
    case dtl::SES_COMMON :
      std::cout << "C " << it->first << std::endl;
      break;
    default :
      break;
    }
  }
  return 0;
}

上記のプログラムを実行すると2つの文字列をコマンドラインから入力として受け取って、編集距離とLCS、あとSESを表示します。

narazuya@bokkko% make strdiff
narazuya@bokkko% ./strdiff acbdeacbed acebdabbabed
editDistance:6
LCS:acbdabed
SES
C a
C c
A e
C b
C d
D e
C a
D c
C b
A b
A a
A b
C e
C d
narazuya@bokkko%

また、int型のvector同士の差分を取るサンプルもあります。(ソースはintdiff.cppを参照)

narazuya@bokkko% ./intdiff
1 2 3 4 5 6 7 8 9 10 
3 5 1 4 5 1 7 9 6 10 
editDistance:8
LCS: 3 4 5 7 9 10 
SES
D 1
D 2
C 3
A 5
A 1
C 4
C 5
D 6
A 1
C 7
D 8
C 9
A 6
C 10
narazuya@bokkko%

サンプルプログラムは他に、2つのファイルの差分をUnified Formatで出力するunidiffや、差分を適用して片方の文字列からもう片方の文字列に変換できるか試すpatchとそのファイル版であるfpatchがあります。

dtlのパフォーマンス

ほかのdiffと同じく、全然違うファイルの差分を計算しようとするとパフォーマンスが劣化します。
dtlの初期の頃の実装だと1万行単位のファイル同士で片方がC言語のソースコードでもう片方が全て空行のファイルを比較した際に数十秒かかっていたり、ひどいときはメモリを喰い過ぎてプログラムが落ちてしまったりしていました。今だとパフォーマンスはこんな感じです(unidiffにtimeつけて実行。最適化オプション-O2を付加)。環境は先述のMac OS Xのものに準じます。編集距離はGNU diffutilsのdiffの出力を元に事前に算出したものです。(なので、dtlのunidiffが出力する差分とは微妙に異なります)

O(ND)やO(NP)などのアルゴリズムは比較する2つのシーケンスが似通っている場合に特に効率よく動作します。逆に言うとシーケンス同士の差異が大きいほど最悪の計算量に近づいていきます。なので、真面目に差分の経路を記録しようとすると全然違うシーケンスを比較した際にかなりのメモリ領域が必要になります。当初は記録した経路のうちのあとでホントに必要になる経路だけを抽出して節約しようと試みたのですが、どうにもうまくいかなくて、単純に、経路記録のためのvectorが一定のサイズを越えたら、そこまでの経路の記録を使って、差分を計算してvectorを廃棄した後、また途中から経路を記録していくという実装になっています。(バージョン0.04から)
これにより、差分が非常に大きい場合でも、メモリを大量に消費することはありません。最初はサイズ越えたら残りのシーケンスを「削除」と「追加」だけで構成するようになっていました。これは(途中までしか計算しないんで)めっちゃ速いんですが、精度の点であまりにダメダメだろうということで0.04からは今の実装になっています(でも、やっぱり個人的にはまだ「う～ん」という感じが否めないです)。ちなみに最後の一番行数の多いファイルはすべて空行のファイルで、残りはCのソースコードです。

余談ですが、GCCのバージョンの違いだけで最大0.2～0.3秒ぐらいパフォーマンスが変わりました。

dtlの今後の課題と展望

・効率改善
・mergeの実装
・unidiffの出力で、「-」→「+」の順ではなく、「+」→「-」の順で表示されることがある

現状の実装にはあまり満足していなくて、近似アルゴリズムを使ったら効率化できないかなあと思いつつ、そのへんは今のところ、さっぱりなので今必死こいて勉強してるところです。あと、作ったdiffを元にmergeも作ろうと考えてるところです。最後のは割と細かいことですが、undiffの出力が「削除」→「追加」ではなく、「追加」→「削除」の順に表示されてしまうことがある点です。ほかのdiffみたいに前者の形で表示された方が見やすいと思うので、これは暇を見て修正する予定です。

参考文献・URL

・E.W.MYERS, "An O(ND) Difference Algorithm and Its Variations"
・S.W.Maner, G.Myers, W.Miller, "An O(NP) Sequence Comparison Algorithm"
・文書比較アルゴリズム
・diff(1), diff(2), diff(3)