読者です 読者をやめる 読者になる 読者になる

diff with Unified Format

前に作ったO(NP)なdiffのプログラムを元に、
2つのファイルの差分をUnified Formatで表示できるようにしてみた。
とりあえず、以下のe.txtとd.txtの差分を表示してみる。

e.txt

a
d
e
c
f
e
a
b
c
d
e
f
g
h
i

d.txt

a
e
c
z
z
d
e
f
a
b
c
d
e
f
g
h
i

この2つのファイルの差分を表示するわけだが、
まず、比較対象として普段UNIX系のOSを使っている大半の人が使っているであろう、
GNU diffutilsのdiffを使ってみる。

narazuya@bokkko% diff -u e.txt d.txt
--- e.txt       2008-09-05 03:42:14.000000000 +0900
+++ d.txt       2008-09-05 03:41:57.000000000 +0900
@@ -1,9 +1,11 @@
 a
-d
 e
 c
-f
+z
+z
+d
 e
+f
 a
 b
 c
narazuya@bokkko%   


続いて自分のC++製UnifiedFormatなdiff。日付部分の表示が微妙に違うのは大目に見てやってください。

narazuya@bokkko% ./unidiff e.txt d.txt
--- e.txt       2008-09-05 03:42:14 +0900
+++ d.txt       2008-09-05 03:41:57 +0900
@@ -1,9 +1,11 @@
 a
+e
+c
+z
+z
 d
 e
-c
 f
-e
 a
 b
 c
narazuya@bokkko% 

う〜ん、差分の適用結果自体は同じになるけど、SESの経路が微妙に違うなあ。
単にアルゴリズムが違うからか?*1


ちなみにdiffのアルゴリズムそのものを実装するより、
Unified Formatで表示するプログラムを書く方が難しかったというのはまた別の話。*2

*1:GNU diffutilsのアルゴリズムはO(ND)を改良したもの

*2:あの「@@」で囲まれている部分の数字をちゃんと表示するのがすごくめんどくさいのです