ここに書きためていることは近々雑誌記事としてまとめたいと思っています。 何かコメントがありましたらお教え下さい。
UNIX の diff や MS-DOS の fc はテキストファイルを行単位に調べて差分を構成する。 対話的に差分をマージする sdiff や，一部 UNIX（SUNWesu パッケージ）には bdiff (big diff) というものもある。この bdiff は binary diff ではない。
バイナリで同じことができるであろうか。
私は1989年5月14日に PC-VAN の SIG SCIENCE の「計算機と算法」ボードで次のようなことを書いた （この当時は UNIX も使ったことがない青二才であった）。
#1099/1982 計算機と算法
★タイトル (SCIENCE ) 89/ 5/14 19:42 ( 36)
もう一つのデータ圧縮／奥村
★内容
以下に書くことは、確かどこかで読んだことのある内容だと思うのですが、ソー
スが思い出せません。オリジナルなアイデアではありません。とりあえず手もとに
ある本などを参考にして、その議論を復元してみます。
データ圧縮というと、与えられたテキストなり画像なりを圧縮することだけを考
えがちですが、われわれにとって有用なもう一つの圧縮があります。
われわれはプログラムを作るとき第１版、第２版、……と改良を重ねていくわけ
ですが、それらの間にはほぼ共通の部分もたくさんあるはずです。そこで、第２版
を発表したときは、第１版との違いの部分だけをうまく提示することができれば、
第１版をもっているものにとっては、かなり小さい「修正箇所」だけのファイルを
もらうだけで第２版が復元できるはずです。
といっても、パッチを当てるというわけではなく、ある部分に新しいコードが挿
入されてその後の部分は後ろにずれるという類のことにも対応できなければなりま
せん。
こういったことは、絶対ジャンプ命令の多い実行ファイルではあまりうまくいか
ないかもしれませんが、ソースプログラムなどではたいへん効力を発揮するのでは
ないかと思います。
ＵＮＩＸのｄｉｆｆは（といっても私はＵＮＩＸ使ったことないのですが）、こ
ういう考えの一つの実現と見ることができるでしょう。ｄｉｆｆはＭｃＩｌｒｏｙ
の作ったプログラムで、テキストファイルにしか適用できません。そのアルゴリズ
ムは例えば
J. W. Hunt and T. G. Szymanski, A fast algorithm for computing
longest common subsequences, CACM (May 1977)
にあるそうです（読んでない）。ｄｉｆｆ自体のアルゴリズムは
M. D. McIlroy and J. W. Hunt, An algorithm for differential file
comparison, Bell Labs Computing Science Technical Report 41 (1976)
にあるそうです。
データ圧縮の文脈ではｉｎｃｒｅｍｅｎｔａｌ ｃｏｄｉｎｇの一種と考えられ
ます。これについては、例えば
M. Visvalingam, Indexing with coded deltas: a data compaction
technique, Software Practice and Experience 6, 397-403 (1976)
に言及されているそうです。
どうも「そうです」が多くてすみません。どなたか研究してみてくださいません
か。われわれがＢＢＳで交換するプログラムは、完成品が１つあるだけというので
はなく、皆の意見を聞いては少しずつ手を加えて改良していくというタイプが多い
ように思いますので、この種の「圧縮」はけっこう役に立つのではないかと思いま
す。どうでしょうか。
というわけで，これまでわれわれのグループが研究していた LZ77 (特に LZSS) アルゴリズムの実装を利用して， 一つのファイルを辞書としてもう一つのファイルを圧縮すれば， うまくバイナリ差分が抽出できることを指摘し， 具体的な実装を募った。
このアイデアに最初に挑戦されたのが， LZSS を実装した LARC を作られたあの 三木和彦 氏であった。
三木氏の作品 LDIFF は残念ながら今はあまり使われていない。
LDIFF に代わって MS-DOS で広く使われるようになった和製バイナリ差分ソフトが bdiff/bupdate である。
やはり和製のソフトで，小さい差分を作ると銘打たれた WSP は，bdiff/bupdate と並んでよく使われるようになった。
やはり和製の LDF は Lintaro 氏の作品。
他の和製バイナリ差分ツールについては， Vector の /dos/util/bin/patch に紹介がある。
この bdiff は bdiff/bupdate の bdiff ではない。
RCE Home Page 参照。
Univ. of Karlsruhe, Institute for Program Structures and Data Organization の James J. Hunt による RCE は RCS の改良版で，BDE (Byte Differencing Engine) というバイナリ差分エンジンを使う。BDE を実装した bdiff は通常の diff より4倍も効率が良く，しかもバイナリデータにも適用できる。 DuraSoft GmbH というところから売られているらしい。
論文としては，
J. Hunt, K. P. Vo, and W. Tichy. An Empicical Study of Delta Algorithms. In IEEE Soft. Config. and Maint. Workshop. Berlin, March, 1996.とそれを拡張した
James J. Hunt, Kiem-Phong Vo, Walter F. Tichy. Delta algorithms: an empirical analysis. ACM Transactions on Software Engineering and Methodology Vol. 7, No. 2 (April 1998), Pages 192-214があるようである。後者は ACM 会員なら ここ から入手できる。
Josh MacDonald's XDelta is now 1.0.3. これがいま最も使いやすいと思われる。
rsync については ここ にまとめて書いた。 これもたいへん賢い一種のバイナリ差分の考え方を使っている。
次の論文に HTTP を差分で送るメリットが詳しく検討されている。 これでは diff および Vdelta を使っている。 これも ACM の会員なら ここ から入手できる。
Jeffrey C. Mogul, Fred Douglis, Anja Feldmann, Balachander Krishnamurthy. Potential benefits of delta encoding and data compression for HTTP. In Proc. SIGCOMM '97, pp. 181--194. Cannes, France, 1997.
これについては Fred Douglis のページの HTTP Deltas and Compression の項目や Optimistic Deltas のページ参照。
HTML を使った情報配信（プッシュなど）にも当然ながら差分が有効である。 Marimba Inc. （Java で有名な Arthur van Hoff らが Sun Microsystems, Inc. をスピンオフして作った会社）は差分を使った配信方法を Netscape Communications Corp., Novell, Inc., Sun Microsystems, Inc., @Home Network, Inc. と共同で W3C に The HTTP Distribution and Replication Protocol (DRP) として提案している。 また，DRP で使われる差分形式 GDIFF を別途 Generic Diff Format Specification として提案している。
しかし， W3C Staff Note on HTTP Distribution and Replication Protocol Submission に述べられているように，この提案は Novadigm, Inc. がその米国特許 5,581,764 "Distributed Computer Network Including Hierarchical Resource Information Structure and Related Method of Distributing Resources" (Filed May 2, 1994) に抵触するとして Marimba を訴えたようである（1997年3月）。 また，このことについて W3C にも警告している（1997年8月27日）。 Novadigm の Patent Information のページも参照されたい。 さすが訴訟の国であるが， プッシュ／プル技術はともかく， 差分をとることにまで特許を主張しないでほしいものである。
次のリンクを参照されたい。
彼らのいくつかの論文が上のサイトから入手できる。
Mark Nelson's FAQ に次の記述がある。
May 1995 issue of DDJ has an article called "A Cross-Platform Binary Diff", by Kris Coppieters.
In some ways performing a diff on two files is a compression problem. I wrote an article called "Fast String Searching With Suffix Trees" in Dr. Dobb's Journal. You can find the article online by going to my home page, following the link to "Magazine Articles", then going down to August 1996:
If you create a suffx tree using the contents of File A, you can then work your way through File B, repetitively finding the longest match offset/length pairs for the contents of B. All you have to do after that is compress the offset/length output, and you should have a pretty good diff file. (Find the optimal one is a lot harder.)
Quake というゲームで差分圧縮を使っているようだ。
リンクはご自由にどうぞ。
松阪大学
奥村晴彦
okumura@matsusaka-u.ac.jp
Copyright (c) 1999 Haruhiko Okumura.
Last modified: Sat Feb 27 14:24:25 1999