Network Working Group D. Korn
Request for Comments: 3284 AT&T Labs
Category: Standards Track J. MacDonald
UC Berkeley
J. Mogul
Hewlett-Packard Company
K. Vo
AT&T Labs
June 2002
The VCDIFF Generic Differencing and Compression Data Format
Status of this Memo
このメモの位置付け
This document specifies an Internet standards track protocol for the Internet community, and requests discussion and suggestions for improvements. Please refer to the current edition of the "Internet Official Protocol Standards" (STD 1) for the standardization state and status of this protocol. Distribution of this memo is unlimited.
この文書は、インターネットコミュニティのためのインターネット標準トラックプロトコルを指定し、改善のための議論と提案を要求します。このプロトコルの標準化状態と状態への「インターネット公式プロトコル標準」（STD 1）の最新版を参照してください。このメモの配布は無制限です。
Copyright Notice
著作権表示
Copyright (C) The Internet Society (2002). All Rights Reserved.
著作権（C）インターネット協会（2002）。全著作権所有。
Abstract
抽象
This memo describes VCDIFF, a general, efficient and portable data format suitable for encoding compressed and/or differencing data so that they can be easily transported among computers.
このメモはVCDIFF、それらは容易にコンピュータ間で搬送することができるように、圧縮及び/又は差分データを符号化するのに適した一般的な、効率的でポータブルデータフォーマットを記述する。
Table of Contents
目次
1. Executive Summary ........................................... 2
2. Conventions ................................................. 4
3. Delta Instructions .......................................... 5
4. Delta File Organization ..................................... 6
5. Delta Instruction Encoding .................................. 12
6. Decoding a Target Window .................................... 20
7. Application-Defined Code Tables ............................. 21
8. Performance ................................................. 22
9. Further Issues .............................................. 24
10. Summary ..................................................... 25
11. Acknowledgements ............................................ 25
12. Security Considerations ..................................... 25
13. Source Code Availability .................................... 25
14. Intellectual Property Rights ................................ 26
15. IANA Considerations ......................................... 26
16. References .................................................. 26
17. Authors' Addresses .......................................... 28
18. Full Copyright Statement .................................... 29
Compression and differencing techniques can greatly improve storage and transmission of files and file versions. Since files are often transported across machines with distinct architectures and performance characteristics, such data should be encoded in a form that is portable and can be decoded with little or no knowledge of the encoders. This document describes Vcdiff, a compact portable encoding format designed for these purposes.
圧縮と差分技術は大幅にファイルとファイルバージョンの保存や送信を向上させることができます。ファイルは、多くの場合、異なるアーキテクチャ及び性能特性と機械を横切って輸送されているので、そのようなデータは、ポータブルであり、エンコーダのほとんど、あるいは全く知識を用いて復号化することができる形式で符号化されるべきです。この文書では、Vcdiff、これらの目的のために設計されたコンパクトなポータブルエンコード形式を説明しています。
Data differencing is the process of computing a compact and invertible encoding of a "target file" given a "source file". Data compression is similar, but without the use of source data. The UNIX utilities diff, compress, and gzip are well-known examples of data differencing and compression tools. For data differencing, the computed encoding is called a "delta file", and for data compression, it is called a "compressed file". Delta and compressed files are good for storage and transmission as they are often smaller than the originals.
データの差分は、「ソース・ファイル」は、所与の「対象ファイル」のコンパクトかつ可逆符号化を計算する処理です。データ圧縮は似ていますが、ソースデータを使用せず。差分UNIXユーティリティは、圧縮、とgzipは、データの差分と圧縮ツールの周知の例です。データ差分のため、計算されたエンコーディングは、「デルタファイル」と呼ばれ、データ圧縮のために、それは「圧縮ファイル」と呼ばれています。彼らは多くの場合、オリジナルよりも小さいとデルタと圧縮されたファイルは、記憶および伝送のために良いです。
Data differencing and data compression are traditionally treated as distinct types of data processing. However, as shown in the Vdelta technique by Korn and Vo [1], compression can be thought of as a special case of differencing in which the source data is empty. The basic idea is to unify the string parsing scheme used in the Lempel-Ziv'77 (LZ'77) style compressors [2] and the block-move technique of Tichy [3]. Loosely speaking, this works as follows:
データの差分データ圧縮は、従来のデータ処理の異なるタイプとして扱われます。しかし、コーン及びVoとによってVdelta技術に示されるように[1]、圧縮は、ソースデータが空である差分の特殊な場合と考えることができます。基本的な考え方は、レンペル - Ziv'77（LZ'77）形式の圧縮機で使用される文字列の構文解析方式を統一することである[2]とTichyのブロック移動技術[3]。次のように大まかに言えば、これは動作します：
a. Concatenate source and target data. b. Parse the data from left to right as in LZ'77 but make sure that a parsed segment starts the target data. c. Start to output when reaching target data.
A。ソースとターゲットのデータを連結します。 B。 LZ'77のように左から右にデータを解析するが、解析されたセグメントは、対象データを開始していることを確認してください。 C。対象データに到達したときに出力を開始します。
Parsing is based on string matching algorithms, such as suffix trees [4] or hashing with different time and space performance characteristics. Vdelta uses a fast string matching algorithm that requires less memory than other techniques [5,6]. However, even with this algorithm, the memory requirement can still be prohibitive for large files. A common way to deal with memory limitation is to partition an input file into chunks called "windows" and process them separately. Here, except for unpublished work by Vo, little has been done on designing effective windowing schemes. Current techniques, including Vdelta, simply use source and target windows with corresponding addresses across source and target files.
解析は、接尾辞木のような文字列照合アルゴリズム、[4]に基づいて、または異なる時間と空間の性能特性を持つハッシュされます。 Vdeltaは、他の技術[5,6]より少ないメモリを必要とする高速文字列照合アルゴリズムを使用します。しかし、このアルゴリズムで、メモリ要件は、まだ大きなファイルのために法外なことができます。メモリの制限に対処する一般的な方法は、「ウィンドウ」と呼ばれる塊に、入力ファイルを分割し、それらを別々に処理することです。ここで、Voのことで未発表の作品を除いて、少しは効果的なウィンドウのスキームを設計する上で行われています。 Vdeltaを含む現在の技術は、単にソースとターゲットのファイル間のアドレスを対応するソースとターゲットのウィンドウを使用しています。
String matching and windowing algorithms have great influence on the compression rate of delta and compressed files. However, it is desirable to have a portable encoding format that is independent of such algorithms. This enables the construction of client-server applications in which a server may serve clients with unknown computing characteristics. Unfortunately, all current differencing and compressing tools, including Vdelta, fall short in this respect. Their storage formats are closely intertwined with the implemented string matching and/or windowing algorithms.
文字列のマッチングとウィンドウアルゴリズムは、デルタと圧縮ファイルの圧縮率に大きな影響を与えます。しかし、そのようなアルゴリズムの独立している携帯型の符号化フォーマットを有することが望ましいです。これは、サーバーが不明なコンピューティングの特性を持つ顧客にサービスを提供しているクライアント・サーバ・アプリケーションの構築を可能にします。残念ながら、現在のすべての差分とVdeltaなどの圧縮ツールは、この点では及ばない。その記憶形式は密接実施ストリングマッチング及び/又はウィンドウアルゴリズムと絡み合っています。
The encoding format Vcdiff proposed here addresses the above issues. Vcdiff achieves the characteristics below:
Vcdiffは、ここで提案エンコード形式は、上記の問題に対処します。 Vcdiffは、以下の特性を実現します。
Output compactness: The basic encoding format compactly represents compressed or delta files. Applications can further extend the basic encoding format with "secondary encoders" to achieve more compression.
出力コンパクト：基本的なエンコード形式をコンパクトに圧縮または差分ファイルを表します。アプリケーションは、より一層の圧縮を達成するために、「二エンコーダー」を基本的なエンコード形式を拡張することができます。
Data portability: The basic encoding format is free from machine byte order and word size issues. This allows data to be encoded on one machine and decoded on a different machine with different architecture.
データポータビリティ：基本的なエンコード形式は、マシンのバイト順とワードサイズの問題から自由です。これは、データが1台のマシン上で符号化され、異なるアーキテクチャを有する異なるマシン上で復号化することを可能にします。
Algorithm genericity: The decoding algorithm is independent from string matching and windowing algorithms. This allows competition among implementations of the encoder while keeping the same decoder.
アルゴリズムの汎用性：復号アルゴリズムは、文字列マッチングとウィンドウアルゴリズムから独立しています。これは、同じデコーダを維持したまま、エンコーダの実装間の競争を可能にします。
Decoding efficiency: Except for secondary encoder issues, the decoding algorithm runs in time proportionate to the size of the target file and uses space proportionate to the maximal window size. Vcdiff differs from more conventional compressors in that it uses only byte-aligned data, thus avoiding bit-level operations, which improves decoding speed at the slight cost of compression efficiency.
効率をデコード：二エンコーダの問題を除いて、復号化アルゴリズムは、時間内にターゲットファイルのサイズに比例して動作し、最大ウィンドウサイズに比例した空間を使用しています。 Vcdiffは、圧縮効率のわずかなコストで復号速度を向上させることが唯一のバイト整列されたデータを使用することで、より従来型の圧縮機、従ってビットレベルの操作を回避すること、と異なります。
The combined differencing and compression method is called "delta compression" [14]. As this way of data processing treats compression as a special case of differencing, we shall use the term "delta file" to indicate the compressed output for both cases.
合わせた差分圧縮方式を「差分圧縮」[14]と呼ばれています。差分の特殊なケースとして、データ処理の扱い圧縮するこの方法として、我々は両方のケースのために圧縮された出力を示すために、用語「デルタファイル」を使用しなければなりません。
The basic data unit is a byte. For portability, Vcdiff shall limit a byte to its lower eight bits even on machines with larger bytes. The bits in a byte are ordered from right to left so that the least significant bit (LSB) has value 1, and the most significant bit (MSB), has value 128.
基本的なデータ単位はバイトです。移植のために、Vcdiffも大きいバイトのマシン上で、その下位8ビットのバイトを制限しなければなりません。最下位ビット（LSB）の値が1、最上位ビット（MSB）を有するように、バイト内のビットは右から左に順序付けられ、値128を有します。
For purposes of exposition in this document, we adopt the convention that the LSB is numbered 0, and the MSB is numbered 7. Bit numbers never appear in the encoded format itself.
この文書の博覧会の目的のために、私たちはLSB 0に番号が付けられ規則を採用し、MSBはエンコード形式自体には表示されません7.ビット番号を番号が付けられています。
Vcdiff encodes unsigned integer values using a portable, variable-sized format (originally introduced in the Sfio library [7]). This encoding treats an integer as a number in base 128. Then, each digit in this representation is encoded in the lower seven bits of a byte. Except for the least significant byte, other bytes have their most significant bit turned on to indicate that there are still more digits in the encoding. The two key properties of this integer encoding that are beneficial to a data compression format are:
Vcdiffは（[7]元々Sfioライブラリーに導入された）ポータブル、可変サイズの形式を使用して符号なし整数値を符号化します。この符号化は、この表現の各桁は、バイトの下位7ビットで符号化され、そしてベース128に数値として整数を扱います。最下位バイトを除いて、他のバイトは、その最上位ビットがエンコーディングでまだ多くの桁数があることを示すために、オンにしています。データ圧縮フォーマットに有益であり、この整数符号化の二つの重要な特性は次のとおりです。
a. The encoding is portable among systems using 8-bit bytes, and b. Small values are encoded compactly.
A。符号化は、8ビットバイト、およびBを使用してシステム間で移植性があります。小さい値をコンパクトにエンコードされています。
For example, consider the value 123456789, which can be represented with four 7-bit digits whose values are 58, 111, 26, 21 in order from most to least significant. Below is the 8-bit byte encoding of these digits. Note that the MSBs of 58, 111 and 26 are on.
例えば、最下位に最もから順にその値が58である4つの7ビットの数字、111、26、21で表すことができる値123456789を考えます。以下は、これらの数字の8ビットバイトエンコーディングがあります。 58、111と26の最上位ビットがオンになっていることに注意してください。
+-------------------------------------------+
| 10111010 | 11101111 | 10011010 | 00010101 |
+-------------------------------------------+
MSB+58 MSB+111 MSB+26 0+21
Henceforth, the terms "byte" and "integer" will refer to a byte and an unsigned integer as described.
説明したように今後、用語「バイト」および「整数」バイトと符号なし整数を指します。
Algorithms in the C language are occasionally exhibited to clarify the descriptions. Such C code is meant for clarification only, and is not part of the actual specification of the Vcdiff format.
C言語でアルゴリズムは時折説明を明確にするために展示されています。そのようなCコードは、明確化のためのもの、及びVcdiffフォーマットの実際の仕様の一部ではありません。
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14, RFC 2119 [12].
この文書のキーワード "MUST"、 "MUST NOT"、 "REQUIRED"、、、、 "べきではない" "べきである" "ないもの" "ものとし"、 "推奨"、 "MAY"、および "OPTIONAL" はありますBCP 14、RFC 2119 [12]に記載されているように解釈されます。
A large target file is partitioned into non-overlapping sections called "target windows". These target windows are processed separately and sequentially based on their order in the target file.
大きなターゲットファイルは、「ターゲットの窓」と呼ばれる非重複セクションに分割されます。これらのターゲットウィンドウは、ターゲットファイル内の順序に基づいて順次別々に処理しています。
A target window T, of length t, may be compared against some source data segment S, of length s. By construction, this source data segment S comes either from the source file, if one is used, or from a part of the target file earlier than T. In this way, during decoding, S is completely known when T is being decoded.
ターゲットウィンドウTは、長さtの、長さsのいくつかのソースデータセグメントS、比較されてもよいです。いずれかが使用される場合に構成することにより、このソースデータセグメントSは、いずれかのソース・ファイルから来る、またはTがデコードされているときに、復号時に、このように早いTよりもターゲット・ファイルの部分から、Sは完全に知られています。
The choices of T, t, S and s are made by some window selection algorithm, which can greatly affect the size of the encoding. However, as seen later, these choices are encoded so that no knowledge of the window selection algorithm is needed during decoding.
T、T、SとSの選択肢が大幅に符号化の大きさに影響を与えることができるいくつかのウィンドウ選択アルゴリズムによって行われます。ウィンドウ選択アルゴリズムの知識が復号中に必要とされないように、しかし、後で見られるように、これらの選択は、符号化されます。
Assume that S[j] represents the jth byte in S, and T[k] represents the kth byte in T. Then, for the delta instructions, we treat the data windows S and T as substrings of a superstring U, formed by concatenating them like this:
仮定するがS [j]はS内のj番目のバイトを示し、T [k]は、デルタ手順について、我々は、超弦Uのサブストリング、連結することによって形成されたデータ窓SとTを治療、そしてT.におけるk番目のバイトを表しますこのようにそれら：
S[0]S[1]...S[s-1]T[0]T[1]...T[t-1]
S [0]〜S [1] ... S [S-1] T [0] T [1] ... T [T-1]
The "address" of a byte in S or T is referred to by its location in U. For example, the address of T[k] is s+k.
SまたはTでバイトの「アドレス」は、例えば米国におけるその位置によって参照され、T [K]のアドレスがs + Kです。
The instructions to encode and direct the reconstruction of a target window are called delta instructions. There are three types:
ターゲットウィンドウの再建をエンコードし、指示する命令はデルタ命令と呼ばれています。 3つのタイプがあります。
ADD: This instruction has two arguments, a size x and a sequence of x bytes to be copied. COPY: This instruction has two arguments, a size x and an address p in the string U. The arguments specify the substring of U that must be copied. We shall assert that such a substring must be entirely contained in either S or T.
ADD：この命令は、2つの引数、サイズXとコピーされるxバイトの配列を有します。 COPY：この命令は、2つの引数、引数をコピーしなければならないUの部分文字列を指定サイズxと文字列U.内のアドレスpを持っています。私たちは、そのような部分文字列が完全にSまたはTのいずれかに含まれていなければならないと主張するもの
RUN: This instruction has two arguments, a size x and a byte b, that will be repeated x times.
RUN：この命令は、x回繰り返される二つの引数、サイズxとバイトbを、持っています。
Below are example source and target windows and the delta instructions that encode the target window in terms of the source window.
以下の例ソースとターゲットウィンドウやソースウィンドウの観点からターゲットウィンドウをエンコードデルタ命令です。
a b c d e f g h i j k l m n o p
a b c d w x y z e f g h e f g h e f g h e f g h z z z z
COPY 4, 0 ADD 4, w x y z COPY 4, 4 COPY 12, 24 RUN 4, z
Y、Z COPY 4,4 COPY 12、24 RUN 4、Z、X、W COPY 4,0 ADD 4、
Thus, the first letter 'a' in the target window is at location 16 in the superstring. Note that the fourth instruction, "COPY 12, 24", copies data from T itself since address 24 is position 8 in T. This instruction also shows that it is fine to overlap the data to be copied with the data being copied from, as long as the latter starts earlier. This enables efficient encoding of periodic sequences, i.e., sequences with regularly repeated subsequences. The RUN instruction is a compact way to encode a sequence repeating the same byte even though such a sequence can be thought of as a periodic sequence with period 1.
したがって、 'ターゲットウィンドウ内の最初の文字は超弦内の位置16にあります。以下のように、この命令はまたそれからコピーされるデータをコピーするデータを重なるように微細であることを示す第4の命令、「COPY 12、24」、アドレス24がT自体からのコピーデータはT.における位置8であることに注意してください後者の開始以前の限り。これは、周期的配列、すなわち、規則的に繰り返すサブシーケンスを有する配列の効率的な符号化を可能にします。 RUN命令は、そのような配列は、期間1の周期配列と考えることができるにもかかわらず、同じバイトの繰り返しシーケンスを符号化するコンパクトな方法です。
To reconstruct the target window, one simply processes one delta instruction at a time and copies the data, either from the source window or the target window being reconstructed, based on the type of the instruction and the associated address, if any.
もしあればターゲットウィンドウを再構成するためには、単純に、一度に一つのデルタ命令を処理し、コピーしたデータを、いずれかのソースウィンドウまたはターゲットウィンドウから命令の種類と関連付けられたアドレスに基づいて、再構成されています。
A Vcdiff delta file starts with a Header section followed by a sequence of Window sections. The Header section includes magic bytes to identify the file type, and information concerning data processing beyond the basic encoding format. The Window sections encode the target windows.
Vcdiffデルタファイルは、窓部の配列が続くヘッダ部から始まります。ヘッダセクションは、ファイルタイプを識別し、基本的な符号化フォーマットを越えてデータ処理に関する情報にマジックバイトを含みます。ウィンドウのセクションでは、ターゲットウィンドウを符号化します。
Below is the overall organization of a delta file. The indented items refine the ones immediately above them. An item in square brackets may or may not be present in the file depending on the information encoded in the Indicator byte above it.
以下は、デルタファイルの全体的な組織です。インデントされたアイテムは、すぐに上記のものを絞り込みます。角括弧内のアイテムは、又はそれ以上のインジケータバイトに符号化された情報に応じて、ファイル内に存在してもしなくてもよいです。
Header Header1 - byte Header2 - byte Header3 - byte Header4 - byte Hdr_Indicator - byte [Secondary compressor ID] - byte [Length of code table data] - integer [Code table data] Size of near cache - byte Size of same cache - byte Compressed code table data Window1 Win_Indicator - byte [Source segment size] - integer [Source segment position] - integer The delta encoding of the target window Length of the delta encoding - integer The delta encoding Size of the target window - integer Delta_Indicator - byte Length of data for ADDs and RUNs - integer Length of instructions and sizes - integer Length of addresses for COPYs - integer Data section for ADDs and RUNs - array of bytes Instructions and sizes section - array of bytes Addresses section for COPYs - array of bytes Window2 ...
ヘッダヘッダ1 - バイトヘッダ2 - バイトHeader3 - バイトHeader4 - バイトHdr_Indicator - バイト[二次圧縮機ID] - バイト[コード表データの長さ] - ニア・キャッシュの整数【コードテーブルデータ]サイズ - 同じキャッシュのバイトサイズ - バイト圧縮符号表データWindow1のWin_Indicator - バイト[ソース・セグメント・サイズ] - 整数[ソースセグメント位置] - デルタ符号化の対象窓長の差分エンコーディング整数 - 整数Delta_Indicator - - のバイト長ターゲットウィンドウの差分エンコーディングサイズを整数追加して実行するためのデータ - 命令及びサイズの整数の長さ - COPYsのアドレスの整数の長さ - 追加し、実行のために整数データ部 - バイト命令のアレイとセクションのサイズ - COPYsのバイトアドレス部のアレイ - バイトウィンドウ2のアレイ.. 。
Each delta file starts with a header section organized as below. Note the convention that square-brackets enclose optional items.
各デルタファイルは、以下のように編成ヘッダ部から始まります。角括弧はオプション項目を囲み規則に注意してください。
Header1 - byte = 0xD6
Header2 - byte = 0xC3
Header3 - byte = 0xC4
Header4 - byte
Hdr_Indicator - byte
[Secondary compressor ID] - byte
[Length of code table data] - integer
[Code table data]
The first three Header bytes are the ASCII characters 'V', 'C' and 'D' with their most significant bits turned on (in hexadecimal, the values are 0xD6, 0xC3, and 0xC4). The fourth Header byte is currently set to zero. In the future, it might be used to indicate the version of Vcdiff.
最初の三つのヘッダバイトは、ASCII文字「V」、「C」およびその最上位ビットの「D」が（16進数で、値は0xD6、0xC3と0xC4である）がオンされています。第四ヘッダーバイトは、現在はゼロに設定されています。将来的には、Vcdiffのバージョンを示すために使用される可能性があります。
The Hdr_Indicator byte shows if there is any initialization data required to aid in the reconstruction of data in the Window sections. This byte MAY have non-zero values for either, both, or neither of the two bits VCD_DECOMPRESS and VCD_CODETABLE below:
Hdr_Indicatorバイトは、窓部におけるデータの再構成を支援するために必要な初期化データがある場合を示しています。このバイトは、いずれかのための非ゼロ値を持っている両方、または2つのビットVCD_DECOMPRESS以下VCD_CODETABLEのでもないことがあります。
7 6 5 4 3 2 1 0
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
^ ^
| |
| +-- VCD_DECOMPRESS
+---- VCD_CODETABLE
If bit 0 (VCD_DECOMPRESS) is non-zero, this indicates that a secondary compressor may have been used to further compress certain parts of the delta encoding data as described in Sections 4.3 and 6. In that case, the ID of the secondary compressor is given next. If this bit is zero, the compressor ID byte is not included.
ビット0（VCD_DECOMPRESS）が非ゼロである場合、これはその場合、セクション4.3および6に記載されているように、二次圧縮機のIDである二次圧縮機は、さらに、デルタ符号化データの特定の部分を圧縮するために使用されてきた可能性があることを示し次の与えられました。このビットがゼロの場合、コンプレッサIDバイトが含まれていません。
If bit 1 (VCD_CODETABLE) is non-zero, this indicates that an application-defined code table is to be used for decoding the delta instructions. This table itself is compressed. The length of the data comprising this compressed code table and the data follow next. Section 7 discusses application-defined code tables. If this bit is zero, the code table data length and the code table data are not included.
ビット1（VCD_CODETABLE）が非ゼロである場合、これは、アプリケーション定義のコードテーブルはデルタ命令を復号するために使用されることを示します。このテーブル自体が圧縮されています。この圧縮符号テーブルを含むデータの長さとデータが次従います。セクション7は、アプリケーション定義されたコードテーブルを論じています。このビットがゼロである場合、コードテーブルデータ長と符号テーブルデータが含まれていません。
If both bits are set, then the compressor ID byte is included before the code table data length and the code table data.
両方のビットが設定されている場合、圧縮機IDバイトは、コードテーブルデータ長と符号テーブルデータの前に含まれています。
Each Window section is organized as follows:
次のように各窓部が構成されています。
Win_Indicator - byte [Source segment length] - integer [Source segment position] - integer The delta encoding of the target window
Win_Indicator - バイト[ソースセグメント長] - 整数[ソースセグメント位置] - ターゲットウィンドウの差分エンコーディング整数
Below are the details of the various items:
以下は、様々なアイテムの詳細は以下のとおりです。
Win_Indicator: This byte is a set of bits, as shown:
Win_Indicator：示すように、このバイトは、ビットの集合です。
7 6 5 4 3 2 1 0
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
^ ^
| |
| +-- VCD_SOURCE
+---- VCD_TARGET
If bit 0 (VCD_SOURCE) is non-zero, this indicates that a segment of data from the "source" file was used as the corresponding source window of data to encode the target window. The decoder will use this same source data segment to decode the target window.
ビット0（VCD_SOURCE）が非ゼロである場合、これは「ソース」ファイルからデータのセグメントをターゲットウィンドウを符号化するために、データの対応するソースウィンドウとして使用したことを示しています。デコーダは、ターゲットウィンドウをデコードするために、この同じソース・データ・セグメントを使用します。
If bit 1 (VCD_TARGET) is non-zero, this indicates that a segment of data from the "target" file was used as the corresponding source window of data to encode the target window. As above, this same source data segment is used to decode the target window.
ビット1（VCD_TARGET）が非ゼロである場合、これは「対象」ファイルからデータのセグメントがターゲットウィンドウを符号化するデータの対応するソースウィンドウとして使用したことを示しています。上記のように、この同じソースデータセグメントは、ターゲットウィンドウをデコードするために使用されます。
The Win_Indicator byte MUST NOT have more than one of the bits set (non-zero). It MAY have none of these bits set.
Win_Indicatorバイトは設定されたビット（非ゼロ）の複数を有してはなりません。これは、設定され、これらのビットのいずれを有していなくてもよいです。
If one of these bits is set, the byte is followed by two integers to indicate respectively, the length and position of the source data segment in the relevant file. If the indicator byte is zero, the target window was compressed by itself without comparing against another data segment, and these two integers are not included.
これらのビットのいずれかが設定されている場合、バイトは、それぞれ関連するファイル内のソース・データ・セグメントの長さと位置を示すために、2つの整数が続きます。インジケータバイトがゼロの場合、対象ウィンドウは、別のデータセグメントと比較することなく、それ自体で圧縮し、これら二つの整数が含まれていません。
The delta encoding of the target window:
ターゲットウィンドウのデルタエンコーディング：
This contains the delta encoding of the target window, either in terms of the source data segment (i.e., VCD_SOURCE or VCD_TARGET was set) or by itself if no source window is specified. This data format is discussed next.
これには、ソースウィンドウが指定されていない場合、ソース・データ・セグメントの点で（すなわち、VCD_SOURCE又はVCD_TARGETが設定された）、またはそれ自体のいずれかによって、ターゲットウィンドウの差分エンコーディングを含んでいます。このデータ形式は、次の議論されています。
The delta encoding of a target window is organized as follows:
次のようにターゲットウィンドウのデルタエンコーディングが編成されています。
Length of the delta encoding - integer The delta encoding Length of the target window - integer Delta_Indicator - byte Length of data for ADDs and RUNs - integer Length of instructions section - integer Length of addresses for COPYs - integer Data section for ADDs and RUNs - array of bytes Instructions and sizes section - array of bytes Addresses section for COPYs - array of bytes
差分エンコーディングの長さ - ターゲットウィンドウのデルタ符号化長整数 - 整数Delta_Indicator - 追加し、実行のためにデータのバイト長 - 命令区間の整数の長さ - COPYsのアドレスの整数の長さ - 追加し、実行のために整数データ部 - 配列COPYsのバイトアドレス部の配列 - - バイトの配列バイト命令とセクションサイズの
Length of the delta encoding: This integer gives the total number of remaining bytes that comprise the data of the delta encoding for this target window.
差分エンコーディングの長さ：この整数は、このターゲット・ウィンドウのデルタ符号化のデータを含む残りのバイトの総数を与えます。
The delta encoding: This contains the data representing the delta encoding which is described next.
デルタ符号化：これは、次に説明する差分エンコーディングを表すデータを含みます。
Length of the target window: This integer indicates the actual size of the target window after decompression. A decoder can use this value to allocate memory to store the uncompressed data.
ターゲットウィンドウの長さ：この整数は、解凍後にターゲットウィンドウの実際のサイズを示します。デコーダは、非圧縮データを格納するためにメモリを割り当てるためにこの値を使用することができます。
Delta_Indicator: This byte is a set of bits, as shown:
Delta_Indicator：示すように、このバイトは、ビットの集合です。
7 6 5 4 3 2 1 0
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
^ ^ ^
| | |
| | +-- VCD_DATACOMP
| +---- VCD_INSTCOMP
+------ VCD_ADDRCOMP
VCD_DATACOMP: bit value 1.
VCD_INSTCOMP: bit value 2.
VCD_ADDRCOMP: bit value 4.
As discussed, the delta encoding consists of COPY, ADD and RUN instructions. The ADD and RUN instructions have accompanying unmatched data (that is, data that does not specifically match any data in the source window or in some earlier part of the target window) and the COPY instructions have addresses of where the matches occur. OPTIONALLY, these types of data MAY be further compressed using a secondary compressor. Thus, Vcdiff separates the encoding of the delta instructions into three parts:
論じたように、デルタ符号化は、COPYから成り、命令を追加して実行します。 ADDとRUN命令は、添付の不一致データを有する（すなわち、特異的にソースウィンドウまたはターゲットウィンドウのいくつかの以前の部分にデータが一致しないデータ）とCOPY命令は、一致が発生する場所のアドレスを有しています。任意選択的に、データのこれらのタイプは、さらに、二次圧縮を用いて圧縮することができます。したがって、Vcdiffは、3つの部分にデルタ命令のエンコーディングを分離します：
a. The unmatched data in the ADD and RUN instructions, b. The delta instructions and accompanying sizes, and c. The addresses of the COPY instructions.
A。 ADDとRUN説明書、Bで比類のないデータ。デルタの指示および付随するサイズおよびc。 COPY命令のアドレス。
If the bit VCD_DECOMPRESS (Section 4.1) was on, each of these sections may have been compressed using the specified secondary compressor. The bit positions 0 (VCD_DATACOMP), 1 (VCD_INSTCOMP), and 2 (VCD_ADDRCOMP) respectively indicate, if non-zero, that the corresponding parts are compressed. Then, these parts MUST be decompressed before decoding the delta instructions.
ビットVCD_DECOMPRESS（セクション4.1）であった場合、これらのセクションの各々は、指定された二次圧縮を用いて圧縮されていてもよいです。非ゼロの場合はビット位置0（VCD_DATACOMP）、1（VCD_INSTCOMP）、及び2（VCD_ADDRCOMP）は、それぞれ対応する部分が圧縮されていること、を示しています。次に、これらの部品は、デルタ命令をデコードする前に解凍する必要があり。
Length of data for ADDs and RUNs: This is the length (in bytes) of the section of data storing the unmatched data accompanying the ADD and RUN instructions.
追加して実行するためのデータの長さ：これは、ADDとRUN命令を伴う不一致データを格納するデータの部分の長さ（バイト単位）です。
Length of instructions section: This is the length (in bytes) of the delta instructions and accompanying sizes.
指示部の長さ：これは、デルタ命令および添付サイズの長さ（バイト単位）です。
Length of addresses for COPYs: This is the length (in bytes) of the section storing the addresses of the COPY instructions.
COPYsのアドレスの長さ：これは、COPY命令のアドレスを格納する部分の長さ（バイト単位）です。
Data section for ADDs and RUNs: This sequence of bytes encodes the unmatched data for the ADD and RUN instructions.
追加され、実行されるためのデータセクション：バイトのシーケンスはADDとRUN手順については、比類のないデータを符号化します。
Instructions and sizes section: This sequence of bytes encodes the instructions and their sizes.
命令とセクションのサイズ：バイトのシーケンスは、命令とそのサイズを符号化します。
Addresses section for COPYs: This sequence of bytes encodes the addresses of the COPY instructions.
COPYsのアドレスセクション：バイトのシーケンスは、COPY命令のアドレスを符号化します。
The delta instructions described in Section 3 represent the results of string matching. For many data differencing applications in which the changes between source and target data are small, any straightforward representation of these instructions would be adequate. However, for applications including differencing of binary files or data compression, it is important to encode these instructions well to achieve good compression rates. The keys to this achievement is to efficiently encode the addresses of COPY instructions and the sizes of all delta instructions.
セクション3で説明デルタ命令は文字列マッチングの結果を表します。ソースとターゲットのデータ間の変化が小さいされたアプリケーションを差分多くのデータの場合、これらの命令のいずれかの直接的な表現が適当でしょう。しかし、バイナリファイルの差分やデータ圧縮などのアプリケーションのために、良い圧縮率を達成するためにも、これらの命令をエンコードすることが重要です。この成果の鍵は、効率的にCOPY命令のアドレスと、すべてのデルタ命令のサイズを符号化することです。
Addresses of COPY instructions are locations of matches and often occur close by or even exactly equal to one another. This is because data in local regions are often replicated with minor changes. In turn, this means that coding a newly matched address against some recently matched addresses can be beneficial. To take advantage of this phenomenon and encode addresses of COPY instructions more efficiently, the Vcdiff data format supports the use of two different types of address caches. Both the encoder and decoder maintain these caches, so that decoder's caches remain synchronized with the encoder's caches.
COPY命令のアドレスが一致した場所であり、多くの場合、近くまたは相互にさえ正確に等しく起こります。地元の地域内のデータは、多くの場合、若干の変更をレプリケートされるためです。ターンでは、これはいくつかの最近一致したアドレスに対して、新たにマッチしたアドレスをコーディングすることは有益であり得ることを意味しています。この現象を利用し、より効率的にCOPY命令のアドレスを符号化するために、Vcdiffデータ形式は、アドレスキャッシュ二つの異なるタイプの使用をサポートしています。そのデコーダのキャッシュがエンコーダのキャッシュと同期残るように、エンコーダとデコーダの両方は、これらのキャッシュを維持します。
a. A "near" cache is an array with "s_near" slots, each containing an address used for encoding addresses nearby to previously encoded addresses (in the positive direction only). The near cache also maintains a "next_slot" index to the near cache. New entries to the near cache are always inserted in the next_slot index, which maintains a circular buffer of the s_near most recent addresses.
A。 「近い」キャッシュが「s_near」スロット（のみ正方向に）以前に符号化されたアドレスに近くのアドレスを符号化するために使用されるアドレスを含むそれぞれの配列です。ニア・キャッシュは、また、ニア・キャッシュに「next_slot」インデックスを維持します。ニア・キャッシュへの新エントリは常にs_near最新のアドレスの循環バッファを維持next_slotインデックスに挿入されています。
b. A "same" cache is an array with "s_same", with a multiple of 256 slots, each containing an address. The same cache maintains a hash table of recent addresses used for repeated encoding of the exact same address.
B。 「同一の」キャッシュは、256スロット、アドレスを含むそれぞれの倍数で、「s_same」を持つ配列です。同じキャッシュはまったく同じアドレスの繰り返し符号化のために使用される最近のアドレスのハッシュテーブルを維持します。
By default, the parameters s_near and s_same are respectively set to 4 and 3. An encoder MAY modify these values, but then it MUST encode the new values in the encoding itself, as discussed in Section 7, so that the decoder can properly set up its own caches.
セクション7で説明したようにデコーダが適切に設定できるように、デフォルトでは、パラメータはs_nearとs_sameは、それぞれエンコーダがこれらの値を変更することができる4および3に設定されているが、それは、符号化自体に新しい値を符号化しなければなりません独自のキャッシュ。
At the start of processing a target window, an implementation (encoder or decoder) initializes all of the slots in both caches to zero. The next_slot pointer of the near cache is set to point to slot zero.
ターゲットウィンドウ処理の開始時に、インプリメンテーション（エンコーダまたはデコーダ）はゼロに両方のキャッシュ内のスロットの全てを初期化します。ニア・キャッシュのnext_slotポインタはゼロをスロットに指すように設定されています。
Each time a COPY instruction is processed by the encoder or decoder, the implementation's caches are updated as follows, where "addr" is the address in the COPY instruction.
COPY命令は、エンコーダまたはデコーダによって処理されるたびに、実装のキャッシュは「addrが」COPY命令のアドレスである場合、次のように更新されます。
a. The slot in the near cache referenced by the next_slot index is set to addr. The next_slot index is then incremented modulo s_near.
A。 next_slotインデックスによって参照ニア・キャッシュ内のスロットはADDRに設定されています。 next_slotインデックスは、モジュロs_nearをインクリメントされます。
b. The slot in the same cache whose index is addr%(s_same*256) is set to addr. [We use the C notations of % for modulo and * for multiplication.]
B。インデックス（s_same * 256）ADDR％であり、同じキャッシュ内のスロットはADDRに設定されています。 [私たちは、乗算の剰余と*のため％のCの表記を使用します。]
To make clear the above description, below are examples of cache data structures and algorithms to initialize and update them:
明確な上記の説明を行うために、以下にそれらを初期化し、更新するためにキャッシュ・データ構造とアルゴリズムの例は以下のとおりです。
typedef struct _cache_s
{
int* near; /* array of size s_near */
int s_near;
int next_slot; /* the circular index for near */
int* same; /* array of size s_same*256 */
int s_same;
} Cache_t;
cache_init(Cache_t* ka) { int i;
cache_init（Cache_tの*のKA）{iはint型。
ka->next_slot = 0;
for(i = 0; i < ka->s_near; ++i)
ka->near[i] = 0;
for(i = 0; i < ka->s_same*256; ++i) ka->same[i] = 0; }
用（i = 0; I <KA-> s_same * 256; ++ I）KA->同じ[I] = 0; }
cache_update(Cache_t* ka, int addr)
{
if(ka->s_near > 0)
{ ka->near[ka->next_slot] = addr;
ka->next_slot = (ka->next_slot + 1) % ka->s_near;
}
if(ka->s_same > 0) ka->same[addr % (ka->s_same*256)] = addr; }
IF（KA-> s_same> 0）KA->同じ[ADDR％（KA-> s_same * 256）= ADDR。 }
The address of a COPY instruction is encoded using different modes, depending on the type of cached address used, if any.
もしあればCOPY命令のアドレスは、使用されるキャッシュされたアドレスのタイプに応じて、異なるモードを使用して符号化されます。
Let "addr" be the address of a COPY instruction to be decoded and "here" be the current location in the target data (i.e., the start of the data about to be encoded or decoded). Let near[j] be the jth element in the near cache, and same[k] be the kth element in the same cache. Below are the possible address modes:
「addrが」デコードするコピー命令のアドレスであると「ここで」ターゲットデータ（すなわち、約データの開始が符号化又は復号化される）内の現在の場所とします。近く[j]は近く、キャッシュ内のj番目の要素、および同じ[k]は、同じキャッシュ内のk番目の要素であるとします。以下は、可能なアドレスモードは次のとおりです。
VCD_SELF: This mode has value 0. The address was encoded by itself as an integer.
VCD_SELF：アドレスは整数として単独で符号化された0このモードでは、値を有します。
VCD_HERE: This mode has value 1. The address was encoded as the integer value "here - addr".
VCD_HERE：「 - ADDRここで」このモードでは、アドレスを整数値としてエンコードされた値1を持っています。
Near modes: The "near modes" are in the range [2,s_near+1]. Let m be the mode of the address encoding. The address was encoded as the integer value "addr - near[m-2]".
周辺のモード：「近いモード」は範囲[2、s_near + 1]です。 mは、アドレスエンコーディングのモードとします。アドレスは、整数値として符号化された「ADDR - [M-2]の近くに」。
Same modes: The "same modes" are in the range [s_near+2,s_near+s_same+1]. Let m be the mode of the encoding. The address was encoded as a single byte b such that "addr == same[(m - (s_near+2))*256 + b]".
同じモード： "同じモード" は範囲[s_near + 2、+ s_near s_same + 1]です。 mは、符号化のモードとします。アドレスは、単一のバイトbと符号化されたように、 "ADDR ==同じ[（M - （s_near + 2））* 256 + B]"。
We show example algorithms below to demonstrate the use of address modes more clearly. The encoder has the freedom to choose address modes, the sample addr_encode() algorithm merely shows one way of picking the address mode. The decoding algorithm addr_decode() will uniquely decode addresses, regardless of the encoder's algorithm choice.
私たちは、以下の例のアルゴリズムがより明確にアドレスモードの使用を実証することを示しています。エンコーダがアドレスモードを選択する自由を持っている、サンプルaddr_encode（）アルゴリズムは、単にアドレスモードを選ぶ1つの方法を示しています。復号アルゴリズムaddr_decode（）が一意にかかわらず、エンコーダのアルゴリズムを選択した、アドレスをデコードします。
Note that the address caches are updated immediately after an address is encoded or decoded. In this way, the decoder is always synchronized with the encoder.
アドレスは、エンコードやデコードされた直後のアドレスキャッシュが更新されていることに注意してください。このように、デコーダは常にエンコーダと同期しています。
int addr_encode(Cache_t* ka, int addr, int here, int* mode) { int i, d, bestd, bestm;
int型addr_encode（Cache_t * KA、int型のaddrが、ここでINT、INT *モード）{int型iは、D、bestd、bestm。
/* Attempt to find the address mode that yields the
* smallest integer value for "d", the encoded address
* value, thereby minimizing the encoded size of the
* address. */
bestd = addr; bestm = VCD_SELF; /* VCD_SELF == 0 */
if((d = here-addr) < bestd)
{ bestd = d; bestm = VCD_HERE; } /* VCD_HERE == 1 */
for(i = 0; i < ka->s_near; ++i) if((d = addr - ka->near[i]) >= 0 && d < bestd) { bestd = d; bestm = i+2; }
{bestd = D - IF（KA->周辺の[I]）> = 0 && D <bestd（D = ADDR）;（++ I; I <KA-> s_near I = 0）のためのbestm = I + 2。 }
if(ka->s_same > 0 && ka->same[d = addr%(ka->s_same*256)] == addr) { bestd = d%256; bestm = ka->s_near + 2 + d/256; }
IF（KA-> s_same> 0 && KA->同じ[D = ADDR％（KA-> s_same×256）] == ADDR）{bestd = D％256。 bestm = KA-> s_near + 2 + D / 256。 }
cache_update(ka,addr);
cache_update（KA、ADDR）。
*mode = bestm; /* this returns the address encoding mode */
return bestd; /* this returns the encoded address */
}
Note that the addr_encode() algorithm chooses the best address mode using a local optimization, but that may not lead to the best encoding efficiency because different modes lead to different instruction encodings, as described below.
addr_encode（）アルゴリズムは、局所最適化を使用して、最良のアドレスモードを選択し、異なるモードは異なる命令符号化につながるので、以下に記載されるようにそれは、最高の符号化効率をもたらさないことに留意されたいです。
The functions addrint() and addrbyte() used in addr_decode(), obtain from the "Addresses section for COPYs" (Section 4.3), an integer or a byte, respectively. These utilities will not be described here. We simply recall that an integer is represented as a compact variable-sized string of bytes, as described in Section 2 (i.e., base 128).
（addr_decodeで使用される関数addrint（）とaddrbyte（））は、それぞれ「COPYsのアドレス部」（セクション4.3）、整数またはバイトから得ます。これらのユーティリティは、ここで説明されることはありません。我々は、単に第2（即ち、ベース128）に記載のように、整数は、バイトの小型可変サイズの文字列として表現されていることを思い出します。
int addr_decode(Cache_t* ka, int here, int mode) { int addr, m;
int型addr_decode（Cache_t * KA、ここでINT、INTモード）{int型のADDR、M。
if(mode == VCD_SELF)
addr = addrint();
else if(mode == VCD_HERE)
addr = here - addrint();
else if((m = mode - 2) >= 0 && m < ka->s_near) /* near cache */
addr = ka->near[m] + addrint();
else /* same cache */
{ m = mode - (2 + ka->s_near);
addr = ka->same[m*256 + addrbyte()];
}
cache_update(ka, addr);
cache_update（KA、ADDR）。
return addr; }
差出人住所; }
Matches are often short in lengths and separated by small amounts of unmatched data. That is, the lengths of COPY and ADD instructions are often small. This is particularly true of binary data such as executable files or structured data, such as HTML or XML. In such cases, compression can be improved by combining the encoding of the sizes and the instruction types, as well as combining the encoding of adjacent delta instructions with sufficiently small data sizes. Effective choices of when to perform such combinations depend on many factors including the data being processed and the string matching algorithm in use. For example, if many COPY instructions have the same data sizes, it may be worthwhile to encode these instructions more compactly than others.
試合は、多くの場合、長さが短いと比類のない少量のデータで区切られています。これは、COPYの長さで、ADD命令は、多くの場合、小さいです。これは、HTMLやXMLなどの実行可能ファイルや構造化データなどのバイナリデータの特に当てはまります。このような場合には、圧縮サイズおよび命令タイプの符号化を組み合わせること、ならびに十分に小さいデータサイズを有する隣接デルタ命令の符号化を組み合わせることにより改善することができます。このような組み合わせを実行するときの有効な選択肢があるが、処理されたデータと、使用中の文字列照合アルゴリズムを含む多くの要因に依存します。多くのCOPY命令は同じデータサイズを持っている場合、よりコンパクトに他よりも、これらの命令をエンコードするために価値があるかもしれません。
The Vcdiff data format is designed so that a decoder does not need to be aware of the choices made in encoding algorithms. This is achieved with the notion of an "instruction code table", containing 256 entries. Each entry defines, either a single delta instruction or a pair of instructions that have been combined. Note that the code table itself only exists in main memory, not in the delta file (unless using an application-defined code table, described in Section 7). The encoded data simply includes the index of each instruction and, since there are only 256 indices, each index can be represented as a single byte.
デコーダは、符号化アルゴリズムで行った選択を意識する必要がないようにVcdiffデータフォーマットが設計されています。これは、256個のエントリを含む、「命令コード表」の概念を用いて達成されます。各エントリは、単一のデルタ命令または合成された命令の組のいずれかを定義します。 （項7に記載のアプリケーション定義コードテーブルを使用しない場合）、コードテーブル自体だけではないデルタファイルに、メインメモリに存在することに留意されたいです。符号化データは、単に唯一256インデックスが存在するので、各インデックスは単一バイトとして表すことができ、各命令のインデックスを含み、。
Each instruction code entry contains six fields, each of which is a single byte with an unsigned value:
各命令コードエントリは、符号なしの値を有する単一のバイトであり、それぞれが6つのフィールドが、含まれています。
+-----------------------------------------------+
| inst1 | size1 | mode1 | inst2 | size2 | mode2 |
+-----------------------------------------------+
Each triple (inst,size,mode) defines a delta instruction. The meanings of these fields are as follows:
各トリプル（工大、サイズ、モード）デルタ命令を定義します。次のようにこれらのフィールドの意味は以下のとおりです。
inst: An "inst" field can have one of the four values: NOOP (0), ADD (1), RUN (2) or COPY (3) to indicate the instruction types. NOOP means that no instruction is specified. In this case, both the corresponding size and mode fields will be zero.
工大： "INST" フィールドは、4つの値のいずれかを有することができる：NOOP（0）、（1）、RUN（2）またはCOPY（3）命令の種類を示すために追加します。 NOOPには、命令が指定されていないことを意味します。この場合、両方の対応するサイズとモードフィールドはゼロになります。
size: A "size" field is zero or positive. A value zero means that the size associated with the instruction is encoded separately as an integer in the "Instructions and sizes section" (Section 6). A positive value for "size" defines the actual data size. Note that since the size is restricted to a byte, the maximum value for any instruction with size implicitly defined in the code table is 255.
サイズ：「サイズ」フィールドがゼロまたは正です。値ゼロは、命令に関連付けられたサイズは「命令およびサイズの」整数（第6節）として別々に符号化されることを意味します。 「サイズ」の正の値は、実際のデータのサイズを定義します。サイズはバイトに制限されているので、暗黙的コード表で定義されたサイズを有する任意の命令の最大値が255であることに留意されたいです。
mode: A "mode" field is significant only when the associated delta instruction is a COPY. It defines the mode used to encode the associated addresses. For other instructions, this is always zero.
モード：関連付けられたデルタ命令がCOPYの場合にのみ、「モード」フィールドが重要です。これは、関連するアドレスを符号化するために使用されるモードを定義します。他の手順については、これは常にゼロです。
Following the discussions on address modes and instruction code tables, we define a "Code Table" to have the data below:
アドレスモードと命令コードのテーブル上の議論の後、我々は、以下のデータを持っている「コード表」を定義します。
s_near: the size of the near cache,
s_same: the size of the same cache,
i_code: the 256-entry instruction code table.
Vcdiff itself defines a "default code table" in which s_near is 4 and s_same is 3. Thus, there are 9 address modes for a COPY instruction. The first two are VCD_SELF (0) and VCD_HERE (1). Modes 2, 3, 4 and 5 are for addresses coded against the near cache. And modes 6, 7 and 8, are for addresses coded against the same cache.
それ自体がs_nearは4であり、s_sameが3である「デフォルト・コード・テーブル」を定義Vcdiffしたがって、COPY命令の9つのアドレスモードがあります。最初の二つはVCD_SELF（0）とVCD_HERE（1）です。モード2、3、4と5は、ニア・キャッシュに対して符号化されたアドレスのためのものです。そしてモード6、図7及び図8は、アドレスに対して同一のキャッシュに対して符号化されます。
TYPE SIZE MODE TYPE SIZE MODE INDEX
---------------------------------------------------------------
1. RUN 0 0 NOOP 0 0 0
2. ADD 0, [1,17] 0 NOOP 0 0 [1,18]
3. COPY 0, [4,18] 0 NOOP 0 0 [19,34]
4. COPY 0, [4,18] 1 NOOP 0 0 [35,50]
5. COPY 0, [4,18] 2 NOOP 0 0 [51,66]
6. COPY 0, [4,18] 3 NOOP 0 0 [67,82]
7. COPY 0, [4,18] 4 NOOP 0 0 [83,98]
8. COPY 0, [4,18] 5 NOOP 0 0 [99,114]
9. COPY 0, [4,18] 6 NOOP 0 0 [115,130]
10. COPY 0, [4,18] 7 NOOP 0 0 [131,146]
11. COPY 0, [4,18] 8 NOOP 0 0 [147,162]
12. ADD [1,4] 0 COPY [4,6] 0 [163,174]
13. ADD [1,4] 0 COPY [4,6] 1 [175,186]
14. ADD [1,4] 0 COPY [4,6] 2 [187,198]
15. ADD [1,4] 0 COPY [4,6] 3 [199,210]
16. ADD [1,4] 0 COPY [4,6] 4 [211,222]
17. ADD [1,4] 0 COPY [4,6] 5 [223,234]
18. ADD [1,4] 0 COPY 4 6 [235,238]
19. ADD [1,4] 0 COPY 4 7 [239,242]
20. ADD [1,4] 0 COPY 4 8 [243,246]
21. COPY 4 [0,8] ADD 1 0 [247,255]
---------------------------------------------------------------
The default instruction code table is depicted above, in a compact representation that we use only for descriptive purposes. See section 7 for the specification of how an instruction code table is represented in the Vcdiff encoding format. In the depiction, a zero value for size indicates that the size is separately coded. The mode of non-COPY instructions is represented as 0, even though they are not used.
デフォルト命令コード表は、説明の目的のためにのみ使用するコンパクトな表現では、上記示されています。命令コードテーブルはVcdiff符号化形式で表現される方法の指定のためのセクション7を参照してください。描写では、サイズのゼロ値は、サイズが別々に符号化されることを示しています。非COPY命令のモードは、彼らが使用されていないにも関わらず、0として表現されます。
In the depiction, each numbered line represents one or more entries in the actual instruction code table (recall that an entry in the instruction code table may represent up to two combined delta instructions.) The last column ("INDEX") shows which index value, or range of index values, of the entries are covered by that line. (The notation [i,j] means values from i through j, inclusively.) The first 6 columns of a line in the depiction, describe the pairs of instructions used for the corresponding index value(s).
図では、各番号の行は、実際の命令コードテーブル内の1つのまたは複数のエントリを表す（命令コードテーブル内のエントリが2つまでの合成デルタ命令を表すことができることを想起されたい。）最後の列（「インデックス」）はインデックス値を示し、またはエントリのインデックス値の範囲は、そのラインで覆われています。 （表記法[I、J]は、包括的に、IからJまでの値を意味する。）描写の行の最初の6列を、対応するインデックス値（S）のために使用される命令の組を記述する。
If a line in the depiction includes a column entry using the [i,j] notation, this means that the line is instantiated for each value in the range from i to j, inclusively. The notation "0, [i,j]" means that the line is instantiated for the value 0 and for each value in the range from i to j, inclusively.
描写の行は[I、J]の表記法を使用してカラムエントリが含まれている場合、これは、ラインが包括的に、iからjまでの範囲内の各値に対してインスタンス化されることを意味します。表記は「0 [i、jは」ラインは包括的に、値0とiからjまでの範囲内の各値に対してインスタンス化されることを意味します。
If a line in the depiction includes more than one entry using the [i,j] notation, implying a "nested loop" to convert the line to a range of table entries, the first such [i,j] range specifies the outer loop, and the second specifies the inner loop.
描写の行は、テーブルエントリの範囲に行を変換するために、「ネストされたループ」を意味する、[I、J]表記を使用して一つのエントリよりも多く含まれている場合、最初のそのような[I、J]の範囲は、外側のループを指定します、及び第二の内側ループを指定します。
The below examples should make clear the above description:
以下の例は、上記の説明をクリアにする必要があります。
Line 1 shows the single RUN instruction with index 0. As the size field is 0, this RUN instruction always has its actual size encoded separately.
行1は、この実行命令は常に別々に符号化された実際のサイズを有し、サイズフィールドとしてインデックス0を有する単一のRUN命令が0であることを示しています。
Line 2 shows the 18 single ADD instructions. The ADD instruction with size field 0 (i.e., the actual size is coded separately) has index 1. ADD instructions with sizes from 1 to 17 use code indices 2 to 18 and their sizes are as given (so they will not be separately encoded.)
2行目は、18つのADD命令を示しています。サイズフィールド0（すなわち、実際のサイズは別々に符号化される）とADD命令は、1〜18 17に使用するコードインデックス2からサイズでインデックス1 ADD命令を有しており、与えられたそれらのサイズは、（それらが別々に符号化されることがないであろう。 ）
Following the single ADD instructions are the single COPY instructions ordered by their address encoding modes. For example, line 11 shows the COPY instructions with mode 8, i.e., the last of the same cache. In this case, the COPY instruction with size field 0 has index 147. Again, the actual size of this instruction will be coded separately.
単一ADD命令は、そのアドレスの符号化モードによって命じ単一COPY命令は次のとおり。例えば、ライン11は、モード8、すなわち、同じキャッシュの最後とCOPY命令を示しています。この場合、サイズフィールド0とCOPY命令は、この命令の実際のサイズは別々に符号化され、再びインデックス147を有しています。
Lines 12 to 21 show the pairs of instructions that are combined together. For example, line 12 depicts the 12 entries in which an ADD instruction is combined with an immediately following COPY instruction. The entries with indices 163, 164, 165 represent the pairs in which the ADD instructions all have size 1, while the COPY instructions have mode 0 (VCD_SELF) and sizes 4, 5 and 6 respectively.
行12〜21は、一緒に結合された命令の組を示します。例えば、ライン12は、ADD命令は直後のコピー指示を組み合わせた12個のエントリを示しています。指数163、164、165のエントリは、COPY命令がモード0（VCD_SELF）を有し、それぞれ4,5及び6のサイズながら、ADD命令はすべて、サイズ1を有するでペアを表します。
The last line, line 21, shows the eight instruction pairs, where the first instruction is a COPY and the second is an ADD. In this case, all COPY instructions have size 4 with mode ranging from 0 to 8 and all the ADD instructions have size 1. Thus, the entry with the largest index 255 combines a COPY instruction of size 4 and mode 8 with an ADD instruction of size 1.
最後の行は、ライン21は、最初の命令がコピーである8命令ペアを示し、第二は、ADDです。この場合、全てのコピー命令は、0から8までの範囲のモードとサイズ4を有し、すべてのADD命令がサイズ1を有するこのように、最大のインデックスのエントリ255のADD命令でサイズ4及びモード8のコピー命令を組み合わせサイズ1。
The choice of the minimum size 4 for COPY instructions in the default code table was made from experiments that showed that excluding small matches (less then 4 bytes long) improved the compression rates.
デフォルト・コード・テーブル内のコピー指示の最小サイズ4の選択は除く小さなマッチ（長未満4バイト）は、圧縮率を向上させることが示された実験から作製しました。
Section 4.3 discusses that the delta instructions and associated data are encoded in three arrays of bytes:
セクション4.3は、デルタ命令および関連するデータバイトの3つの配列にコードされていることを説明します。
Data section for ADDs and RUNs,
Instructions and sizes section, and
Addresses section for COPYs.
Further, these data sections may have been further compressed by some secondary compressor. Assuming that any such compressed data has been decompressed so that we now have three arrays:
さらに、これらのデータセクションは、さらに、いくつかの二次圧縮機で圧縮されていてもよいです。私たちは今、3つの配列を持っているように、そのような圧縮されたデータが解凍されたと仮定すると：
inst: bytes coding the instructions and sizes.
data: unmatched data associated with ADDs and RUNs.
addr: bytes coding the addresses of COPYs.
These arrays are organized as follows:
次のようにこれらの配列は、組織化されています。
inst: a sequence of (index, [size1], [size2]) tuples, where "index" is an index into the instruction code table, and size1 and size2 are integers that MAY or MAY NOT be included in the tuple as follows. The entry with the given "index" in the instruction code table potentially defines two delta instructions. If the first delta instruction is not a VCD_NOOP and its size is zero, then size1 MUST be present. Otherwise, size1 MUST be omitted and the size of the instruction (if it is not VCD_NOOP) is as defined in the table. The presence or absence of size2 is defined similarly with respect to the second delta instruction.
工大：「インデックス」は、命令コードテーブルへのインデックスであり、そしてSIZE1とsize2には、以下のように、またはタプルに含まれなくてもよい整数であり（指数、[SIZE1]、[size2に]）タプルのシーケンス。命令コードテーブル内の指定された「インデックス」のエントリは、潜在的に2つのデルタ命令を定義します。第1のデルタ命令がVCD_NOOPなく、その大きさがゼロである場合、SIZE1が存在しなければなりません。そうでなければ、SIZE1を省略しなければならなくて、テーブルに定義されている命令のサイズは、（そうでない場合VCD_NOOP）です。 size2にの有無は、第2のデルタ命令に対して同様に定義されます。
data: a sequence of data values, encoded as bytes.
データ：バイトとして符号化されたデータ値のシーケンス。
addr: a sequence of address values. Addresses are normally encoded as integers as described in Section 2 (i.e., base 128). However, since the same cache emits addresses in the range [0,255], same cache addresses are always encoded as a single byte.
ADDR：アドレス値のシーケンス。アドレスは、通常、第2（即ち、ベース128）に記載のように整数として符号化されます。同じキャッシュが範囲[0,255]のアドレスを放出するので、同じキャッシュ・アドレスは常に単一バイトとして符号化されます。
To summarize, each tuple in the "inst" array includes an index to some entry in the instruction code table that determines:
要約すると、「INST」アレイ内の各タプルは、決定命令コードテーブル内のいくつかのエントリに対するインデックスを含みます。
a. Whether one or two instructions were encoded and their types.
A。 1つのまたは2つの命令がエンコードされたかどうかとその種類。
b. If the instructions have their sizes encoded separately, these sizes will follow, in order, in the tuple.
B。命令はそのサイズが別々に符号化されている場合は、これらのサイズはタプルで、順番に、従います。
c. If the instructions have accompanying data, i.e., ADDs or RUNs, their data will be in the array "data".
C。説明書は、添付データを持っている場合、すなわち、追加または実行し、そのデータは、アレイ「データ」になります。
d. Similarly, if the instructions are COPYs, the coded addresses are found in the array "addr".
D。命令がコピーである場合、同様に、符号化されたアドレスは、アレイ「ADDR」に見出されます。
The decoding procedure simply processes the arrays by reading one code index at a time, looking up the corresponding instruction code entry, then consuming the respective sizes, data and addresses following the directions in this entry. In other words, the decoder maintains an implicit next-element pointer for each array; "consuming" an instruction tuple, data, or address value implies incrementing the associated pointer.
復号手順は、単に、このエントリで指示に従ってそれぞれのサイズ、データ及びアドレスを消費し、対応する命令コードのエントリをルックアップする、一度に一つのコードインデックスを読み取ることにより、アレイを処理します。換言すれば、デコーダは、各アレイの暗黙の次の要素のポインタを維持します。 「消費」命令タプル、データ、またはアドレス値は、関連付けられたポインタをインクリメントを意味します。
For example, if during the processing of the target window, the next unconsumed tuple in the inst array has an index value of 19, then the first instruction is a COPY, whose size is found as the immediately following integer in the inst array. Since the mode of this COPY instruction is VCD_SELF, the corresponding address is found by consuming the next integer in the addr array. The data array is left intact. As the second instruction for code index 19 is a NOOP, this tuple is finished.
ターゲットウィンドウの処理中に、インストアレイ内の次の未使用のタプルが19のインデックス値を有する場合、例えば、最初の命令は、そのサイズ工大アレイにおける直後の整数として発見されたコピーがあります。このコピー命令のモードはVCD_SELFあるため、対応するアドレスは、ADDRアレイ内の次の整数を消費することによって見出されます。データ配列がそのまま残されています。コード指数19のための第2の命令はNOOPであるように、このタプルを終了します。
Although the default code table used in Vcdiff is good for general purpose encoders, there are times when other code tables may perform better. For example, to code a file with many identical segments of data, it may be advantageous to have a COPY instruction with the specific size of these data segments, so that the instruction can be encoded in a single byte. Such a special code table MUST then be encoded in the delta file so that the decoder can reconstruct it before decoding the data.
Vcdiffで使用されるデフォルトのコード表は、汎用エンコーダのために良いですが、他のコードテーブルは、より良い実行することがございます。例えば、データの多くの同一のセグメントを持つファイルを符号化するためには、命令は単一バイトで符号化することができるように、これらのデータ・セグメントの特定サイズのコピー命令を有することが有利であり得ます。デコーダは、データを復号する前に、それを再構成することができるように、そのような特殊コードテーブルは、次に、デルタ・ファイルにエンコードされなければなりません。
Vcdiff allows an application-defined code table to be specified in a delta file with the following data:
Vcdiffは、アプリケーション定義のコードテーブルは、以下のデータを有するデルタ・ファイルに指定することを可能にします。
Size of near cache - byte
Size of same cache - byte
Compressed code table data
The "compressed code table data" encodes the delta between the default code table (source) and the new code table (target) in the same manner as described in Section 4.3 for encoding a target window in terms of a source window. This delta is computed using the following steps: a. Convert the new instruction code table into a string, "code", of 1536 bytes using the below steps in order:
ソースウィンドウの観点からターゲットウィンドウを符号化するためのセクション4.3に記載されるように「圧縮コードテーブルデータが」デフォルトコードテーブル（ソース）と同様に、新しいコードテーブル（ターゲット）との間の差分を符号化します。このデルタは、次の手順を使用して計算されます。順序で以下の手順を使用して1536バイトの、文字列、「コード」に、新たな命令コード表を変換します。
i. Add in order the 256 bytes representing the types of the first instructions in the instruction pairs. ii. Add in order the 256 bytes representing the types of the second instructions in the instruction pairs. iii. Add in order the 256 bytes representing the sizes of the first instructions in the instruction pairs. iv. Add in order the 256 bytes representing the sizes of the second instructions in the instruction pairs. v. Add in order the 256 bytes representing the modes of the first instructions in the instruction pairs. vi. Add in order the 256 bytes representing the modes of the second instructions in the instruction pairs.
私。ために、命令のペアの最初の命令の種類を表す256バイトを追加します。 II。順に命令の組における第二の命令タイプを表す256バイトを追加します。 III。ために、命令のペアの最初の命令の大きさを表す256バイトを追加します。 IV。順に命令の組における第二の命令のサイズを示す256バイトを追加します。 V。順番に命令ペアの最初の命令のモードを表す256バイトを追加します。 VI。順に命令の組における第二の命令モードを示す256バイトを追加します。
b. Similarly, convert the default code table into a string "dflt".
B。同様に、文字列「DFLT」にデフォルトのコード・テーブルを変換します。
c. Treat the string "code" as a target window and "dflt" as the corresponding source data and apply an encoding algorithm to compute the delta encoding of "code" in terms of "dflt". This computation MUST use the default code table for encoding the delta instructions.
C。対応するソースデータとして文字列ターゲットウィンドウとして「コード」と「DFLT」を扱い、「DFLT」の用語で「コード」の差分エンコーディングを計算する符号化アルゴリズムを適用します。この計算はデルタ命令を符号化するためのデフォルトのコード表を使用しなければなりません。
The decoder can then reverse the above steps to decode the compressed table data using the method of Section 6, employing the default code table, to generate the new code table. Note that the decoder does not need to know about the details of the encoding algorithm used in step (c). It is able to decode the new code table because the Vcdiff format is independent from the choice of encoding algorithm, and because the encoder in step (c) uses the known, default code table.
デコーダは、次に、新しいコードテーブルを生成するために、デフォルト・コード・テーブルを用いて、第6の方法を使用して圧縮された表データを復号するために上記の手順を逆にすることができます。デコーダは、工程（c）で使用される符号化アルゴリズムの詳細を知る必要がないことに注意してください。 Vcdiffフォーマットは、符号化アルゴリズムの選択から独立しているので、新しいコードテーブルを復号することができ、ステップ（c）において、エンコーダは既知の、デフォルト・コード・テーブルを使用しているため。
The encoding format is compact. For compression only, using the LZ-77 string parsing strategy and without any secondary compressors, the typical compression rate is better than Unix compress and close to gzip. For differencing, the data format is better than all known methods in terms of its stated goal, which is primarily decoding speed and encoding efficiency.
エンコード形式は、コンパクトです。唯一の圧縮のために、戦略および任意の二次圧縮なしを解析LZ-77文字列を使用して、一般的な圧縮率は、Unix圧縮よりも良好とgzipに近接しています。差分のために、データ・フォーマットは、主に速度を復号し、符号化効率をされ、その述べられた目標の点ですべての既知の方法よりも優れています。
We compare the performance of compress, gzip and Vcdiff using the archives of three versions of the Gnu C compiler, gcc-2.95.1.tar, gcc-2.95.2.tar and gcc-2.95.3.tar. Gzip was used at its default compression level. The Vcdiff data were obtained using the Vcodex/Vcdiff software (Section 13).
私たちは、GNU Cコンパイラ、GCC-2.95.1.tar、GCC-2.95.2.tarとgcc-2.95.3.tar 3つのバージョンのアーカイブを使用して圧縮、gzipとVcdiffの性能を比較します。 gzipはそのデフォルトの圧縮レベルで使用しました。 VcdiffデータはVcodex / Vcdiffソフトウェア（セクション13）を用いて得ました。
Below are the different Vcdiff runs:
以下は異なるVcdiffの実行は、次のとおりです。
Vcdiff: vcdiff is used as a compressor only.
Vcdiff：vcdiffは唯一の圧縮機として使用されています。
Vcdiff-d: vcdiff is used as a differencer only. That is, it only compares target data against source data. Since the files involved are large, they are broken into windows. In this case, each target window, starting at some file offset in the target file, is compared against a source window with the same file offset (in the source file). The source window is also slightly larger than the target window to increase matching opportunities.
Vcdiff-D：vcdiffのみ差分器として使用されています。つまり、それが唯一のソースデータに対して対象データを比較します。関連するファイルが大きいので、窓に分割されています。この場合、各ターゲットウィンドウは、ターゲット・ファイル内のオフセットいくつかのファイルから始まる、（ソースファイル内）オフセット同じファイルとソースウィンドウと比較されます。ソースウィンドウはまた、マッチングの機会を増加させるためにターゲットウィンドウよりもわずかに大きいです。
Vcdiff-dc: This is similar to Vcdiff-d, but vcdiff can also compare target data against target data as applicable. Thus, vcdiff both computes differences and compresses data. The windowing algorithm is the same as above. However, the above hint is recinded in this case.
Vcdiff-DC：これはVcdiff-Dに似ていますが、vcdiffも適用可能な対象データに対して対象データを比較することができます。したがって、vcdiff両方とも差を計算し、データを圧縮します。ウィンドウアルゴリズムは、上記と同様です。しかし、上記のヒントは、この場合にはrecindedされます。
Vcdiff-dcw: This is similar to Vcdiff-dc but the windowing algorithm uses a content-based heuristic to select a source window that is more likely to match with a given target window. Thus, the source data segment selected for a target window often will not be aligned with the file offsets of this target window.
Vcdiff-DCW：これはVcdiff-DCに似ていますが、ウィンドウアルゴリズムは、与えられたターゲットウィンドウと一致する可能性が高いソース・ウィンドウを選択するために、コンテンツベースのヒューリスティックを使用しています。このように、多くの場合、ターゲットウィンドウのために選択したソースデータセグメントは、このターゲットウィンドウのファイルオフセットで整列されることはありません。
gcc-2.95.1 gcc-2.95.2 gcc-2.95.3
---------------------------------------------------------
1. raw size 55,746,560 55,797,760 55,787,520
2. compress - 19,939,390 19,939,453
3. gzip - 12,973,443 12,998,097
4. Vcdiff - 15,358,786 15,371,737
5. Vcdiff-d - 100,971 26,383,849
6. Vcdiff-dc - 97,246 14,461,203
7. Vcdiff-dcw - 256,445 1,248,543
The above table shows the raw sizes of the tar files and the sizes of the compressed results. The differencing results in the gcc-2.95.2 column were obtained by compressing gcc-2.95.2, given gcc-2.95.1. The same results for the column gcc-2.95.3 were obtained by compressing gcc-2.95.3, given gcc-2.95.2.
上記の表には、tarファイルや圧縮された結果の大きさの生の大きさを示しています。 GCC-2.95.2列の差分結果がGCC-2.95.1所与、GCC-2.95.2を圧縮することにより得ました。カラムGCC-2.95.3について同じ結果がGCC-2.95.2所与、GCC-2.95.3を圧縮することにより得ました。
Rows 2, 3 and 4 show that, for compression only, the compression rate from Vcdiff is worse than gzip and better than compress.
行2、唯一の圧縮のため、Vcdiffから圧縮率がGZIPより悪いと圧縮よりも良好であり、図3および4に示します。
The last three rows in the column gcc-2.95.2 show that when two file versions are very similar, differencing can give dramatically good compression rates. Vcdiff-d and Vcdiff-dc use the same simple window selection method of aligning by file offsets, but Vcdiff-dc also does compression so its output is slightly smaller. Vcdiff-dcw uses a content-based algorithm to search for source data that likely will match a given target window. Although it does a good job, the algorithm does not always find the best matches, which in this case, are given by the simple algorithm of Vcdiff-d. As a result, the output size for Vcdiff-dcw is slightly larger.
列のgcc-2.95.2での最後の3行は、2つのファイルのバージョンが非常に類似している場合、差分が劇的に良好な圧縮率を与えることができることを示しています。 Vcdiff-DおよびVcdiff-DCは、ファイルオフセットによって整列の同じ単純なウィンドウ選択方法を使用し、その出力がわずかに小さくなるようにVcdiff-DCはまた、圧縮を行います。 Vcdiff-DCWは、おそらく特定のターゲットウィンドウを一致するソースデータを検索するためのコンテンツベースのアルゴリズムを使用しています。それは良い仕事をしていますが、このアルゴリズムは、常にこのような場合には、Vcdiff-Dの単純なアルゴリズムによって与えられる、ベストマッチを見つけることができません。結果として、Vcdiff-DCWの出力サイズが若干大きくなっています。
The situation is reversed in the gcc-2.95.3 column. Here, the files and their contents were sufficiently rearranged or changed between the making of the gcc-2.95.3.tar archive and the gcc-2.95.2 archive so that the simple method of aligning windows by file offsets no longer works. As a result, Vcdiff-d and Vcdiff-dc do not perform well. By allowing compression, along with differencing, Vcdiff-dc manages to beat Vcdiff-c, which does compression only. The content-based window matching algorithm in Vcdiff-dcw is effective in matching the right source and target windows so that Vcdiff-dcw is the overall winner.
状況はGCC-2.95.3列に逆転されます。ここでは、ファイルとその内容が十分に再配置またはGCC-2.95.3.tarアーカイブの作成とファイルオフセットによってウィンドウを整列させる簡単な方法は、もはや機能しているように、gcc-2.95.2アーカイブの間で変更されました。その結果、Vcdiff-DとVcdiff-dcがうまく実行されません。圧縮を可能にすることにより、差分とともに、Vcdiff-DCにのみ圧縮を行うVcdiff-cは、ビートに管理します。 Vcdiff-DCWにおけるコンテンツベースのウィンドウマッチングアルゴリズムはVcdiff-DCWが総合優勝となるように、右のソースとターゲットウィンドウのマッチングに有効です。
This document does not address a few issues:
このドキュメントでは、いくつかの問題に対処していません。
Secondary compressors: As discussed in Section 4.3, certain sections in the delta encoding of a window may be further compressed by a secondary compressor. In our experience, the basic Vcdiff format is adequate for most purposes so that secondary compressors are seldom needed. In particular, for normal use of data differencing, where the files to be compared have long stretches of matches, much of the gain in compression rate is already achieved by normal string matching. Thus, the use of secondary compressors is seldom needed in this case. However, for applications beyond differencing of such nearly identical files, secondary compressors may be needed to achieve maximal compressed results.
二次圧縮：4.3節で述べたように、ウィンドウのデルタ符号化における特定のセクションでは、さらに、二次圧縮機で圧縮されてもよいです。二次コンプレッサーはほとんど必要ありませんように、私たちの経験では、基本的なVcdiff形式は、ほとんどの目的のために適切です。具体的には、比較されるファイルは、マッチの長いストレッチを有するデータ差分、通常の使用のために、圧縮率の利得の多くはすでに通常の文字列マッチングによって達成されます。このように、二次圧縮機を使用することは、めったにこのような場合には必要ありません。しかし、そのようなほぼ同一のファイルの差分を超えたアプリケーションのために、二次コンプレッサーは最大の圧縮結果を達成するために必要とすることができます。
Therefore, we recommend leaving the Vcdiff data format defined as in this document so that the use of secondary compressors can be implemented when they become needed in the future. The formats of the compressed data via such compressors or any compressors that may be defined in the future are left open to their implementations. These could include Huffman encoding, arithmetic encoding, and splay tree encoding [8,9].
したがって、我々は、彼らが将来必要になったときに二次コンプレッサーの使用を実装することができるように、この文書に記載されているように定義さVcdiffデータ形式を残してお勧めします。将来的に定義することができるような圧縮機または任意の圧縮機を介して、圧縮されたデータのフォーマットは、その実装に開放されています。これらは、ハフマン符号化、算術符号化、及びスプレー木エンコード[8,9]を含むことができます。
Large file system vs. small file system: As discussed in Section 4, a target window in a large file may be compared against some source window in another file or in the same file (from some earlier part). In that case, the file offset of the source window is specified as a variable-sized integer in the delta encoding. There is a possibility that the encoding was computed on a system supporting much larger files than in a system where the data may be decoded (e.g., 64-bit file systems vs. 32- bit file systems). In that case, some target data may not be recoverable. This problem could afflict any compression format, and ought to be resolved with a generic negotiation mechanism in the appropriate protocol(s).
小さなファイルシステム対大きいファイルシステムは：第4章で述べたように、大きなファイルのターゲットウィンドウは、別のファイル内のいくつかのソースウインドウに対して、または（いくつかの以前の部分からの）同じファイルに比較することができます。その場合には、ソースウィンドウのファイルオフセットは、デルタ符号化における可変サイズの整数として指定されています。符号化は、データを復号することができるシステム（例えば、64ビット・ファイル・システム対32ビット・ファイル・システム）の場合よりもはるかに大きいファイルをサポートするシステム上で計算された可能性があります。その場合、いくつかのターゲットデータは回復可能ではないかもしれません。この問題は、任意の圧縮形式を苦しめるし、適切なプロトコル（複数可）で、一般的な交渉メカニズムで解決されるべきである可能性があります。
We have described Vcdiff, a general and portable encoding format for compression and differencing. The format is good in that it allows implementing a decoder without knowledge of the encoders. Further, ignoring the use of secondary compressors not defined within the format, the decoding algorithms run in linear time and requires working space proportional to window size.
我々はVcdiff、圧縮および差分のための一般的なポータブルエンコード形式を記載しています。それはエンコーダの知識なしにデコーダを実装できるようにフォーマットが良好です。さらに、フォーマット内で定義されていない二次コンプレッサーの使用を無視して、デコードアルゴリズムが線形時間で実行され、ウィンドウサイズに比例した作業スペースが必要です。
Thanks are due to Balachander Krishnamurthy, Jeff Mogul and Arthur Van Hoff who provided much encouragement to publicize Vcdiff. In particular, Jeff helped in clarifying the description of the data format presented here.
おかげでVcdiffを公表するために多くの励ましを提供Balachander Krishnamurthy、ジェフムガール人とアーサー・バン・ホフによるものです。特に、ジェフは、ここに提示したデータ形式の記述を明確に助けました。
Vcdiff only provides a format to encode compressed and differenced data. It does not address any issues concerning how such data are, in fact, stored in a given file system or the run-time memory of a computer system. Therefore, we do not anticipate any security issues with respect to Vcdiff.
Vcdiffのみ圧縮に差分をデータを符号化するためのフォーマットを提供します。それは、実際には、与えられたファイルシステムやコンピュータシステムの実行時のメモリに格納されているか、そのようなデータに関するすべての問題に対処していません。したがって、我々はVcdiffに関してどのようなセキュリティ上の問題を予想していません。
Vcdiff is implemented as a data transforming method in Phong Vo's Vcodex library. AT&T Corp. has made the source code for Vcodex available for anyone to use to transmit data via HTTP/1.1 Delta Encoding [10,11]. The source code and according license is accessible at the below URL:
VcdiffはフォンVoとのVcodexライブラリ内のデータ変換方法として実装されています。 AT＆T社は、HTTP / 1.1のデルタエンコーディング[10,11]を介してデータを送信するために使用する人のための利用可能なVcodexのソースコードを行いました。ソースコードと応じたライセンスは、以下のURLでアクセスできます。
http://www.research.att.com/sw/tools
ｈっｔｐ：／／ｗっｗ。れせあｒｃｈ。あっｔ。こｍ／ｓｗ／とおｌｓ
The IETF has been notified of intellectual property rights claimed in regard to some or all of the specification contained in this document. For more information consult the online list of claimed rights, at <http://www.ietf.org/ipr.html>.
IETFは、この文書に含まれる仕様の一部またはすべてについて記載知的財産権について通知されています。詳細については、<http://www.ietf.org/ipr.html>で、要求された権利のオンラインリストを参照してください。
The IETF takes no position regarding the validity or scope of any intellectual property or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; neither does it represent that it has made any effort to identify any such rights. Information on the IETF's procedures with respect to rights in standards-track and standards-related documentation can be found in BCP 11. Copies of claims of rights made available for publication and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementors or users of this specification can be obtained from the IETF Secretariat.
IETFは、そのような権限下で、ライセンスがたりないかもしれない可能性があるためにどの本書または程度に記載されている技術の実装や使用に関係すると主張される可能性があります任意の知的財産やその他の権利の有効性または範囲に関していかなる位置を取りません利用可能。また、そうした権利を特定するために取り組んできたことを表していないん。スタンダードトラックおよび標準関連文書における権利に関するIETFの手順に関する情報は、11の出版物のために利用可能となる権利の主張のコピーやライセンスの保証が利用できるようにするBCPで見つかった、または試みの結果することができますIETF事務局から入手することができます実装者またはこの仕様のユーザーによる、このような所有権の使用のための一般的なライセンスまたは許可を取得するために作られました。
The Internet Assigned Numbers Authority (IANA) administers the number space for Secondary Compressor ID values. Values and their meaning must be documented in an RFC or other peer-reviewed, permanent, and readily available reference, in sufficient detail so that interoperability between independent implementations is possible. Subject to these constraints, name assignments are First Come, First Served - see RFC 2434 [13]. Legal ID values are in the range 1..255.
IANA（Internet Assigned Numbers Authority）は補助圧縮機のID値の数のスペースを管理します。独立した実装の間の相互運用性が可能になるような値とその意味は十分に詳細に、RFCまたは他の査読、永久的な、かつ容易に入手可能な文献に文書化されなければなりません。これらの制約を受けるには、名前の割り当ては早い者勝ちしている - RFC 2434 [13]を参照してください。法律ID値は、範囲1 255です。
This document does not define any values in this number space.
この文書では、この番号空間内の任意の値を定義していません。
[1] D.G. Korn and K.P. Vo, Vdelta: Differencing and Compression, Practical Reusable Unix Software, Editor B. Krishnamurthy, John Wiley & Sons, Inc., 1995.
[1] D.G. KornシェルとK。P. Voは、Vdelta：差分と圧縮、実用的な再利用可能なUnixのソフトウェア、エディタB. Krishnamurthy、John Wiley＆Sons社、1995年。
[2] J. Ziv and A. Lempel, A Universal Algorithm for Sequential Data Compression, IEEE Trans. on Information Theory, 23(3):337-343, 1977.
[2] J.ジブ及びA.レンペル、逐次データ圧縮用の汎用アルゴリズム、IEEEトランス。 337-343、1977：情報理論、23（3）に。
[3] W. Tichy, The String-to-String Correction Problem with Block Moves, ACM Transactions on Computer Systems, 2(4):309-321, November 1984.
[3] W. Tichy、ブロック移動、コンピュータシステム上のACMトランザクション、とストリングから文字列補正問題2（4）：309-321、1984年11月。
[4] E.M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM, 23:262-272, 1976.
[4] E.M. McCreight、スペース・経済的なサフィックスツリーの構築法、ACMのジャーナル、23：262から272、1976。
[5] J.J. Hunt, K.P. Vo, W. Tichy, An Empirical Study of Delta Algorithms, IEEE Software Configuration and Maintenance Workshop, 1996.
[5] J.J.ハント、K。P. Voは、W. Tichy、デルタアルゴリズム、IEEEソフトウェアの設定とメンテナンスワークショップ、1996年の実証的研究。
[6] J.J. Hunt, K.P. Vo, W. Tichy, Delta Algorithms: An Empirical Analysis, ACM Trans. on Software Engineering and Methodology, 7:192-214, 1998.
[6] J.J.ハント、K。P. Voは、W. Tichy、デルタアルゴリズム：実証分析、ACMトランス。 192から214、1998：ソフトウェア工学と方法論、7上。
[7] D.G. Korn, K.P. Vo, Sfio: A buffered I/O Library, Proc. of the Summer '91 Usenix Conference, 1991.
[7] D.G. Kornシェル、K。P. Voは、Sfio：バッファードI / Oライブラリ、PROC。夏'91 Usenixの会議、1991年。
[8] D. W. Jones, Application of Splay Trees to Data Compression, CACM, 31(8):996:1007.
[8] D. W.ジョーンズ、データ圧縮、CACM、31（8）にスプレイ木の応用：996：1007。
[9] M. Nelson, J. Gailly, The Data Compression Book, ISBN 1-55851- 434-1, M&T Books, New York, NY, 1995.
[9] M・ネルソン、J. Gailly氏、データ圧縮ブック、ISBN 1-55851- 434-1、M＆Tブックス、ニューヨーク、NY、1995。
[10] J.C. Mogul, F. Douglis, A. Feldmann, and B. Krishnamurthy, Potential benefits of delta encoding and data compression for HTTP, SIGCOMM '97, Cannes, France, 1997.
[10] J.C.モーグル、F. Douglis、A.フェルドマン、及びB. Krishnamurthy、HTTPのデルタ符号化及びデータ圧縮の潜在的な利点、SIGCOMM '97、カンヌ、フランス、1997。
[11] Mogul, J., Krishnamurthy, B., Douglis, F., Feldmann, A., Goland, Y. and A. Van Hoff, "Delta Encoding in HTTP", RFC 3229, January 2002.
[11]モーグル、J.、クリシュナムルティ、B.、ダグラス、F.、フェルドマン、A.、Golang、Y.及びA.ヴァン・ホッフ、 "HTTPデルタエンコーディング"、RFC 3229、2002年1月。
[12] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
[12]ブラドナーの、S.、 "要件レベルを示すためにRFCsにおける使用のためのキーワード"、BCP 14、RFC 2119、1997年3月。
[13] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 2434, October 1998.
、BCP 26、RFC 2434、1998年10月[13] Narten氏、T.とH. Alvestrand、 "RFCsにIANA問題部に書くためのガイドライン"。
[14] D.G. Korn and K.P. Vo, Engineering a Differencing and Compression Data Format, Submitted to Usenix'2002, 2001.
[14] D.G. KornシェルとK。P. Voは、Usenix'2002、2001年に提出された差分と圧縮データフォーマットを、エンジニアリング。
Kiem-Phong Vo (main contact) AT&T Labs, Room D223 180 Park Avenue Florham Park, NJ 07932
キエム・フォンVO（主接点）AT＆T Labs社、ルームD223 180パークアベニューフローラムパーク、NJ 07932
Phone: 1 973 360 8630 EMail: kpv@research.att.com
電話番号：1 973 360 8630 Eメール：kpv@research.att.com
David G. Korn AT&T Labs, Room D237 180 Park Avenue Florham Park, NJ 07932
デビッドG.コーンAT＆T Labs社、ルームD237 180パークアベニューフローラムパーク、NJ 07932
Phone: 1 973 360 8602 EMail: dgk@research.att.com
電話番号：1 973 360 8602 Eメール：dgk@research.att.com
Jeffrey C. Mogul Western Research Laboratory Hewlett-Packard Company 1501 Page Mill Road, MS 1251 Palo Alto, California, 94304, U.S.A.
ジェフリーC.モーグル西研究所、米国Hewlett-Packard Company 1501ページミルロード、MS 1251パロアルト、カリフォルニア、94304、U.S.A.
Phone: 1 650 857 2206 (email preferred) EMail: JeffMogul@acm.org
電話番号：1 650 857 2206（電子メール優先）メール：JeffMogul@acm.org
Joshua P. MacDonald Computer Science Division University of California, Berkeley 345 Soda Hall Berkeley, CA 94720
ジョシュアP.マクドナルドカリフォルニアのコンピュータサイエンス部門大学バークレー校345ソーダホールバークレー、CA 94720
EMail: jmacd@cs.berkeley.edu
メールアドレス：jmacd@cs.berkeley.edu
Copyright (C) The Internet Society (2002). All Rights Reserved.
著作権（C）インターネット協会（2002）。全著作権所有。
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.
この文書とその翻訳は、コピーして他の人に提供し、それ以外についてはコメントまたは派生物は、いかなる種類の制限もなく、全体的にまたは部分的に、準備コピーし、公表して配布することができることを説明したり、その実装を支援することができます、上記の著作権表示とこの段落は、すべてのそのようなコピーや派生物に含まれていることを条件とします。しかし、この文書自体は著作権のための手順はで定義されている場合には、インターネット標準を開発するために必要なものを除き、インターネットソサエティもしくは他のインターネット関連団体に著作権情報や参照を取り除くなど、どのような方法で変更されないかもしれませんインターネット標準化プロセスが続く、または英語以外の言語に翻訳するために、必要に応じなければなりません。
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.
上記の制限は永久で、インターネット学会やその後継者や譲渡者によって取り消されることはありません。
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
この文書とここに含まれている情報は、基礎とインターネットソサエティおよびインターネットエンジニアリングタスクフォースはすべての保証を否認し、明示または黙示、その情報の利用がない任意の保証を含むがこれらに限定されない「として、」上に設けられています特定の目的への権利または商品性または適合性の黙示の保証を侵害します。
Acknowledgement
謝辞
Funding for the RFC Editor function is currently provided by the Internet Society.
RFC Editor機能のための基金は現在、インターネット協会によって提供されます。