dtl - 考える人、コードを書く人

C++なDiffライブラリ、dtlをリリースしました。

http://code.google.com/p/dtl-cpp/

詳しくは上記のURLのSummaryやサンプルを見ていただければと思いますが、こちらでは上記に載ってないことや今後の方針や課題とかについて書こうと思います。

dtl？

Diff Template libraryの略です。実は名前は前からずっとこれにしようというのがあったんですが、某友人と先輩方に全力で「それは止めておけ」とアドバイスを頂いたので、こっちにしました。

アルゴリズムはWuのO(NP)差分アルゴリズム(以下、Wuのアルゴリズム)

差分を計算するアルゴリズムにはO(NP)を使っています。

全然違うファイルの差分を取ったときの挙動

Wuのアルゴリズムに限らず、差分を計算するアルゴリズムを真面目にコードに直すと、比較するシーケンス同士が全然違う場合、プログラムがかなり遅くなるか、めちゃくちゃメモリを喰うようになります。編集距離の計算だけなら、ほどんど変わらないのですが、LCSやSESの経路記録がネックになります。そのため、よく使われているようなdiffは完全なLCSやSESを計算するのをあきらめて近似したり、途中で必要ないと判断した経路情報を削除するGC(のようなもの)を付けたりします。

で、dtlについてですが、現状では差分が大きくなりそうだったら途中で計算するのをやめて、計算されなかった分はそのまま記録するようになっています(計算された分はまともな差分を記録します)。例えば、abc → abdならSESは、

C a
C b
D c
A d

ですが、もし最初から差分が大きくなりそうだと判断したら、

D a
D b
D c
A a
A b
A d

となります。もちろん、上記みたいにデータが大きくて、差分も大きいということでなければちゃんと全部計算されます。ほんとは近似とかGCしたりして、メモリ効率や速度を上げるべきだと思っているので、今後はその辺の改善をやっていこうかと思います。