VCDIFFとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > VCDIFFの意味・解説 

VCDIFF

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/11/28 17:14 UTC 版)

ナビゲーションに移動 検索に移動
差分符号化 > 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 も似たようなアルゴリズムであるが、受信側のデータに関してはブロック単位のチェックサムしか知らないので、バイト単位でグリーディーに一致領域を伸ばすという処理が出来ない。

実装

参考文献

  1. ^ CiteSeerX — Data Compression Using Long Common Strings
  2. ^ CiteSeerX — Efficient randomized pattern-matching algorithms

外部リンク

  • RFC 3284 - The VCDIFF Generic Differencing and Compression Data Format



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「VCDIFF」の関連用語

VCDIFFのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



VCDIFFのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのVCDIFF (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS