VCDIFF

VCDIFF (ブイシーディフ) は差分符号化のフォーマットとアルゴリズムであり、 で規定されている。アルゴリズムは1999年に書かれた Jon Bentley と Douglas McIlroy の論文に基づくCiteSeerX — Data Compression Using Long Common Strings。VCDIFF は "Delta encoding in HTTP" () の中でも差分符号化アルゴリズムの一つとして使われていて、Google の SDCH (Shared Dictionary Compression Over HTTP) でも使われている。

 差分命令 
VCDIFF は3つの差分命令を持つ。
 ADD - 新しいシーケンスを追加
 COPY - 古いシーケンスからコピー
 RUN - データの繰り返し (ランレングス圧縮)

 アルゴリズム 
1999年 の Jon Bentley と Douglas McIlroy の論文は、Richard M. Karp と Michael O. Rabin の1987年の論文CiteSeerX — Efficient randomized pattern-matching algorithmsを元にしている。Karp, Rabin の論文は、あるバイト列Aから、バイト列Bを探索するアルゴリズムで、ローリングチェックサム（フィンガープリント）を使い、まず、Bのチェックサムを作り、Aから1バイトずつローリングチェックサムをずらしながら、Bと一致する場所を探索し、チェックサムが一致したら、バイト単位で本当に一致するか最終判定するというアルゴリズムである。

これを踏まえた上で、1999年の Bentley, McIlroy の論文は、データ内からデータ列が一致する部分列を見つけ出すアルゴリズムである（共通部分列問題）。まず、データ列をブロック単位で区切り、それぞれのブロックのチェックサムを計算し、"チェックサム → ブロックの位置"のハッシュテーブルを作成する。このアルゴリズムで検出できるのはブロックの長さ以上の一致列であるが、あとはデータ列に対して、1バイトずつローリングチェックサムを計算し、同じチェックサムを持つブロックを見つけ出したら、あとはグリーディーに一致する領域をバイト単位で伸ばしていく。計算量はデータ長 n に対して、O(n)。

VCDIFF では、Bentley, McIlroy の方法を2つのデータ列に対して行い、COPY 命令を作る。

rsync も似たようなアルゴリズムであるが、受信側のデータに関してはブロック単位のチェックサムしか知らないので、バイト単位でグリーディーに一致領域を伸ばすという処理が出来ない。

 実装 
 xdelta
 open-vcdiff
 diffable
 j-vcdiff
 Miscellaneous Utility Library
 CyanDelta

参考文献

外部リンク
  - The VCDIFF Generic Differencing and Compression Data Format

Category:データ圧縮
Category:データ差分
3284