VCDIFF
VCDIFF (ブイシーディフ) は差分符号化のフォーマットとアルゴリズムであり、RFC 3284 で規定されている。アルゴリズムは1999年に書かれた Jon Bentley と Douglas McIlroy の論文に基づく[1]。VCDIFF は "Delta encoding in HTTP" (RFC 3229) の中でも差分符号化アルゴリズムの一つとして使われていて、Google の SDCH (Shared Dictionary Compression Over HTTP) でも使われている。
差分命令
[編集]VCDIFF は3つの差分命令を持つ。
- ADD - 新しいシーケンスを追加
- COPY - 古いシーケンスからコピー
- RUN - データの繰り返し (ランレングス圧縮)
アルゴリズム
[編集]1999年 の Jon Bentley と Douglas McIlroy の論文は、Richard M. Karp と Michael O. Rabin の1987年の論文[2]を元にしている。Karp, Rabin の論文は、あるバイト列Aから、バイト列Bを探索するアルゴリズムで、ローリングチェックサム（フィンガープリント）を使い、まず、Bのチェックサムを作り、Aから1バイトずつローリングチェックサムをずらしながら、Bと一致する場所を探索し、チェックサムが一致したら、バイト単位で本当に一致するか最終判定するというアルゴリズムである。
これを踏まえた上で、1999年の Bentley, McIlroy の論文は、データ内からデータ列が一致する部分列を見つけ出すアルゴリズムである（共通部分列問題）。まず、データ列をブロック単位で区切り、それぞれのブロックのチェックサムを計算し、"チェックサム → ブロックの位置"のハッシュテーブルを作成する。このアルゴリズムで検出できるのはブロックの長さ以上の一致列であるが、あとはデータ列に対して、1バイトずつローリングチェックサムを計算し、同じチェックサムを持つブロックを見つけ出したら、あとはグリーディーに一致する領域をバイト単位で伸ばしていく。計算量はデータ長 n に対して、O(n)。
VCDIFF では、Bentley, McIlroy の方法を2つのデータ列に対して行い、COPY 命令を作る。
rsync も似たようなアルゴリズムであるが、受信側のデータに関してはブロック単位のチェックサムしか知らないので、バイト単位でグリーディーに一致領域を伸ばすという処理が出来ない。
実装
[編集]参考文献
[編集]- ^ CiteSeerX — Data Compression Using Long Common Strings
- ^ CiteSeerX — Efficient randomized pattern-matching algorithms