[要約] RFC 3284は、VCDIFFというデータフォーマットについての仕様書です。VCDIFFは差分と圧縮を行うための汎用的なフォーマットであり、データの効率的な転送や保存を目的としています。
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
vcdiff genericの違いと圧縮データ形式
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.
Copyright（c）The Internet Society（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ユーティリティDiff、Compress、および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:
データの違いとデータ圧縮は、伝統的に異なるタイプのデータ処理として扱われていました。ただし、KornとVo [1]によるVdelta手法に示されているように、圧縮はソースデータが空である差異の特別なケースと考えることができます。基本的なアイデアは、Lempel-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]。ただし、このアルゴリズムを使用しても、メモリの要件は大きなファイルでは依然として禁止されている可能性があります。メモリ制限に対処する一般的な方法は、「Windows」と呼ばれるチャンクに入力ファイルを分割し、個別に処理することです。ここでは、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]。このデータ処理の方法は、圧縮を差分の特別なケースとして扱うため、「Deltaファイル」という用語を使用して、両方のケースの圧縮出力を示すものです。
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に番号が付けられ、MSBに番号が付けられているという条約を採用します。ビット番号はエンコード形式自体には表示されません。
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は、ポータブルで可変サイズの形式（SFIOライブラリ[7]に導入された）を使用して、署名のない整数値をエンコードします。このエンコードは、整数をベース128の数値として扱います。その後、この表現の各数字は、バイトの下部7ビットでエンコードされます。最も有意なバイトを除いて、他のバイトは、エンコードにさらに多くの数字があることを示すために最も重要なビットをオンにしています。データ圧縮形式に有益なこの整数エンコードの2つの重要なプロパティは次のとおりです。
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.
たとえば、値123456789を考慮してください。これは、値が58、111、26、21である4つの7ビット桁で表現できます。以下は、これらの数字の8ビットバイトエンコードです。58、111、および26のMSBがオンになっていることに注意してください。
+-------------------------------------------+
| 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].
「必須」、「そうしない」、「必須」、「必要」、「「しない」、「そうでない」、「そうではない」、「そうでない」、「推奨」、「5月」、および「オプション」は、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のjthバイトを表し、t [k]がTのkthバイトを表していると仮定します。その後、デルタの指示では、濃縮によって形成されたスーパーストリングuのサブストリングとしてデータウィンドウsとtを扱います。彼らはこのように：
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のバイトの「アドレス」は、Uの場所でその場所で言及されています。たとえば、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.
追加：この命令には、コピーするサイズxとxバイトのシーケンスの2つの引数があります。コピー：この命令には、文字列Uのサイズxとアドレスpの2つの引数があります。引数は、コピーする必要があるuのサブストリングを指定します。このようなサブストリングは、SまたはTに完全に含まれている必要があると断言します。
RUN: This instruction has two arguments, a size x and a byte b, that will be repeated x times.
実行：この命令には、サイズXとバイトBの2つの引数があり、X倍繰り返されます。
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
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
COPY 4, 0 ADD 4, w x y z COPY 4, 4 COPY 12, 24 RUN 4, z
コピー4、0追加4、w x y zコピー4、4コピー12、24 Run 4、z
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.
したがって、ターゲットウィンドウの最初の文字「A」は、スーパーストリングの場所16にあります。4番目の命令「コピー12、24」は、アドレス24がTの位置8であるため、T自体からのデータをコピーしています。後者が早く始まる限り。これにより、周期シーケンスの効率的なエンコード、つまり定期的に繰り返されるサブシーケンスを持つシーケンスが可能になります。実行命令は、そのようなシーケンスが期間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.
ターゲットウィンドウを再構築するには、一度に1つのデルタ命令を処理し、ソースウィンドウまたは再構築されるターゲットウィンドウからデータをコピーして、命令の種類と関連するアドレスがあればコピーします。
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 Deltaファイルは、ヘッダーセクションから始まり、その後のウィンドウセクションのシーケンスが続きます。ヘッダーセクションには、ファイルタイプを識別するマジックバイトと、基本的なエンコード形式を超えたデータ処理に関する情報が含まれています。ウィンドウセクションは、ターゲットウィンドウをエンコードします。
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 ...
Header Header1 -BYTE HEADER2 -BYTE HEADER3 -BYTE HEADER4 -BYTE HDR_INDICATOR -BYTE [セカンダリコンプレッサーID] -BYTE [コードテーブルデータの長さ] - 整数[コードテーブルデータ]近くのキャッシュのサイズ - 同じキャッシュのバイトサイズ - バイト圧縮コードテーブルデータウィンドウWin_indicator -BYTE [ソースセグメントサイズ] - 整数[ソースセグメント位置] - 整数デルタエンコードのターゲットウィンドウの長さのデルタエンコード - 整数ターゲットウィンドウのデルタエンコードサイズ - 整数delta_indicator-バイトの長さ追加および実行のデータ - 整数の命令とサイズの長さ - コピーの整数のアドレスの長さ - 追加および実行の整数データセクション - バイト命令とサイズの配列セクション - バイトアドレスの配列セクション - バイトの配列Window2。。
Each delta file starts with a header section organized as below. Note the convention that square-brackets enclose optional items.
各デルタファイルは、以下のように整理されたヘッダーセクションから始まります。Square-Bracketsがオプションのアイテムを囲む条約に注意してください。
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.
最初の3つのヘッダーバイトは、最も重要なビットがオンになったASCII文字 'V'、「C」、および「D」です（16進数では、値は0xD6、0XC3、および0xC4です）。4番目のヘッダーバイトは現在ゼロに設定されています。将来的には、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_DECOPRESSおよび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 -byte [ソースセグメントの長さ] - 整数[ソースセグメントの位置] - 整数ターゲットウィンドウのデルタエンコード
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つの整数が続きます。インジケータバイトがゼロの場合、ターゲットウィンドウは別のデータセグメントと比較せずにそれ自体によって圧縮され、これら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-追加および実行のデータの長さ - instegerの長さセクション - コピーの整数データセクションの整数データセクションバイトの命令とサイズのセクション - バイトの配列コピーのセクションアドレス - バイトの配列
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.
VCD_DATACOMP：ビット値1. VCD_INSTCOMP：ビット値2. VCD_ADDRCOMP：ビット値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:
説明したように、デルタエンコーディングはコピー、追加、実行の命令で構成されています。ADDおよび実行命令には、比類のないデータ（つまり、ソースウィンドウまたはターゲットウィンドウの以前の部分のデータと一致しないデータ）が付属しており、コピー命令には一致が発生する場所のアドレスがあります。オプションで、これらのタイプのデータは、セカンダリコンプレッサーを使用してさらに圧縮される場合があります。したがって、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 and Run Instructionsの比類のないデータ、b。デルタの指示と付随するサイズ、およびc。コピー指示のアドレス。
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.
追加および実行のデータの長さ：これは、追加および実行命令に付随する比類のないデータを保存するデータのセクションの長さ（バイト単位）です。
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.
コピーのアドレスの長さ：これは、コピー命令のアドレスを保存するセクションの長さ（バイト単位）です。
Data section for ADDs and RUNs: This sequence of bytes encodes the unmatched data for the ADD and RUN instructions.
追加および実行のデータセクション：このバイトのシーケンスは、追加および実行命令の比類のないデータをエンコードします。
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のアドレスセクション：このバイトのシーケンスでは、コピー命令のアドレスをエンコードします。
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で説明されているデルタの指示は、文字列マッチングの結果を表しています。ソースデータとターゲットデータの間の変更が小さい多くのデータ差異アプリケーションでは、これらの命令の簡単な表現は適切です。ただし、バイナリファイルやデータ圧縮の違いを含むアプリケーションの場合、これらの指示を適切にエンコードして、良好な圧縮率を達成することが重要です。この成果の鍵は、コピー命令のアドレスとすべてのデルタ命令のサイズを効率的にエンコードすることです。
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.
コピー命令のアドレスは一致の場所であり、多くの場合、互いに近くにあるか、互いに正確に等しくなります。これは、ローカル地域のデータがしばしば小さな変化で再現されているためです。次に、これは、最近一致したアドレスに対して新しく一致するアドレスをコーディングすることが有益であることを意味します。この現象を活用し、コピー命令のアドレスをより効率的にエンコードするために、VCDIFFデータ形式は2つの異なるタイプのアドレスキャッシュの使用をサポートします。エンコーダーとデコーダーの両方がこれらのキャッシュを維持するため、デコーダーのキャッシュはエンコーダのキャッシュと同期したままです。
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」インデックスも維持しています。Nearキャッシュへの新しいエントリは、常に最新のアドレスの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. 「同じ」キャッシュは、「S_SAME」を備えた配列で、それぞれにアドレスが含まれている256個のスロットがあります。同じキャッシュは、まったく同じアドレスの繰り返しエンコードに使用される最近のアドレスのハッシュテーブルを維持します。
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.
デフォルトでは、デフォルトでは、パラメーターS_NEARとS_SAMEはそれぞれ4および3に設定されます。エンコーダはこれらの値を変更できますが、セクション7で説明したように、エンコード自体の新しい値をエンコードする必要があります。独自のキャッシュ。
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.
コピー命令がエンコーダーまたはデコーダーによって処理されるたびに、実装のキャッシュは次のように更新されます。「addr」はコピー命令のアドレスです。
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インデックスで参照されるニアキャッシュのスロットは、対処するように設定されています。次のスロットインデックスは、modulo 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. インデックスがaddr％（s_same*256）である同じキャッシュのスロットがaddrに設定されています。[Moduloには％の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）{int i;
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;
}
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;
}
The address of a COPY instruction is encoded using different modes, depending on the type of cached address used, if any.
コピー命令のアドレスは、使用されるキャッシュアドレスのタイプに応じて、異なるモードを使用してエンコードされます。
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]を近くのキャッシュのjth要素とし、同じ[k]同じキャッシュのkth要素とします。以下は、可能なアドレスモードです。
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_HORE：このモードには値1があります。アドレスは、整数値「ここ - addr」としてエンコードされました。
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 -near [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をエンコードのモードとします。アドレスは、「addr ==同じ[（m-（s_near 2））*256 b]」になるような単一のバイト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;
/* 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; }
if(ka->s_same > 0 && ka->same[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（）は、それぞれ「コピーのアドレスセクション」（セクション4.3）、整数またはバイトから取得します。これらのユーティリティはここでは説明されません。セクション2（つまり、ベース128）で説明されているように、整数はコンパクトな可変サイズのバイト文字列として表されていることを単に思い出します。
int addr_decode(Cache_t* ka, int here, int mode)
{ 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.
一致の長さが短く、少量の比類のないデータで区切られています。つまり、コピーと追加の指示の長さは、多くの場合小さいです。これは、実行可能ファイルやHTMLやXMLなどの構造化データなどのバイナリデータに特に当てはまります。そのような場合、サイズのエンコードと命令タイプを組み合わせることと、隣接するデルタ命令のエンコードと十分な小さなデータサイズを組み合わせることにより、圧縮を改善できます。このような組み合わせをいつ実行するかの効果的な選択は、処理されるデータや使用中の文字列マッチングアルゴリズムなど、多くの要因に依存します。たとえば、多くのコピー命令が同じデータサイズを持っている場合、これらの命令を他の命令よりもコンパクトにエンコードする価値があるかもしれません。
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、サイズ、モード）は、デルタ命令を定義します。これらのフィールドの意味は次のとおりです。
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：「inst」フィールドは、noop（0）、add（1）、run（2）、またはcopy（3）の4つの値のいずれかを持つことができます。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.
モード：「モード」フィールドは、関連するデルタ命令がコピーである場合にのみ重要です。関連するアドレスをエンコードするために使用されるモードを定義します。他の指示では、これは常にゼロです。
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.
S_NEAR：近くのキャッシュのサイズ、S_SAME：同じキャッシュのサイズ、i_code：256-entry命令コードテーブル。
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.
VCDIFF自体は、S_NEARが4、S_SAMEが3である「デフォルトのコードテーブル」を定義します。したがって、コピー命令には9つのアドレスモードがあります。最初の2つはVCD_Self（0）とVCD_HORE（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を参照してください。描写では、サイズのゼロ値は、サイズが個別にコーディングされていることを示します。非コピー命令のモードは、使用されていない場合でも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つの複合デルタ命令を表すことができることを思い出してください。）最後の列（ "index"）は、どのインデックス値を示していますか、またはインデックス値の範囲、エントリはその行でカバーされます。（表記[i、j]は、iからjからjからの値を包括的に意味します。）描写の行の最初の6列は、対応するインデックス値に使用される命令のペアを説明しています。
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]範囲は外側のループを指定します、2番目は内側のループを指定します。
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の単一の実行命令を示しています。サイズフィールドは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のシングル追加命令が示されています。サイズフィールド0の追加命令（つまり、実際のサイズには個別にコーディングされます）にはインデックス1があります。1〜17の使用コードインデックス2から18を使用したサイズの命令を追加し、サイズは与えられたとおりです（したがって、個別にエンコードされません。））
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.
単一の追加命令に従って、アドレスエンコードモードで注文された単一のコピー命令があります。たとえば、11行目は、モード8のコピー命令、つまり同じキャッシュの最後の手順を示しています。この場合、サイズフィールド0のコピー命令にはインデックス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行目は、追加命令が直後のコピー命令と組み合わされる12のエントリを示しています。インデックス163、164、165のエントリは、追加命令がすべてサイズ1のペアを表し、コピー命令にはそれぞれモード0（VCD_Self）とサイズ4、5、6があります。
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つの命令ペアを示しています。最初の命令はコピーで、2番目の命令は追加です。この場合、すべてのコピー命令は0から8の範囲のモードのサイズ4を持ち、すべての追加命令にはサイズ1があります。したがって、最大のインデックス255のエントリは、サイズ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.
Inst：命令とサイズをコーディングするバイト。データ：追加および実行に関連付けられた比類のないデータ。Addr：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.
INST：（index、[size1]、[size2]）タプルのシーケンス。「index」は命令コードテーブルへのインデックスであり、size1とsize2は次のようにタプルに含まれている場合と含まれない場合がある整数です。命令コードテーブルに指定された「インデックス」があるエントリは、2つのデルタ命令を潜在的に定義します。最初のデルタ命令がVCD_NOOPではなく、そのサイズがゼロの場合、Size1が存在する必要があります。それ以外の場合、size1を省略する必要があり、命令のサイズ（VCD_NOOPではない場合）はテーブルで定義されています。サイズ2の有無は、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.
デコード手順は、一度に1つのコードインデックスを読み取り、対応する命令コードエントリを検索し、このエントリの指示に従ってそれぞれのサイズ、データ、アドレスを消費することにより、配列を単純に処理します。言い換えれば、デコーダーは各配列の暗黙の次の要素ポインターを維持します。命令のタプル、データ、または住所値を「消費」することは、関連するポインターの増加を意味します。
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.
たとえば、ターゲットウィンドウの処理中に、Instアレイの次の消費されていないタプルのインデックス値は19の場合、最初の命令はコピーで、そのサイズはInstアレイの整数のすぐ後に見つかります。このコピー命令のモードはVCD_Selfであるため、対応するアドレスは、ADDRアレイの次の整数を消費することで見つかります。データアレイはそのまま残されます。Code Index 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で使用されるデフォルトのコードテーブルは、汎用エンコーダーに適していますが、他のコードテーブルのパフォーマンスが向上する場合があります。たとえば、データの多くの同一のセグメントを持つファイルをコーディングするには、これらのデータセグメントの特定のサイズのコピー命令を使用して、命令を単一のバイトでエンコードできるようにすることが有利かもしれません。そのような特別なコードテーブルは、データをデコードする前にデコーダーが再構築できるように、Deltaファイルにエンコードする必要があります。
Vcdiff allows an application-defined code table to be specified in a delta file with the following data:
VCDIFFを使用すると、アプリケーション定義のコードテーブルを次のデータを含むDELTAファイルで指定できます。
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。命令ペアの2番目の命令のタイプを表す256バイトを順に追加します。iii。命令ペアの最初の命令のサイズを表す256バイトを順に追加します。IV。命令ペアの2番目の命令のサイズを表す256バイトを順に追加します。v。命令ペアの最初の命令のモードを表す256バイトを順に追加します。vi。命令ペアの2番目の命令のモードを表す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コンパイラの3つのバージョン、GCC-2.95.1.TAR、GCC-2.95.2.TAR、GCC-2.95.3.3.TARのアーカイブを使用して、Compress、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は、差異のみとして使用されます。つまり、ターゲットデータをソースデータと比較するだけです。関係するファイルは大きいため、Windowsに分かれています。この場合、ターゲットファイルのあるファイルオフセットで始まる各ターゲットウィンドウは、同じファイルオフセット（ソースファイル）を持つソースウィンドウと比較されます。また、ソースウィンドウは、マッチングの機会を増やすために、ターゲットウィンドウよりもわずかに大きくなっています。
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は両方とも違いを計算し、データを圧縮します。ウィンドウアルゴリズムは上記と同じです。ただし、この場合は上記のヒントが繰り返されます。
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.2カラムの違いの結果は、GCC-2.95.1を考慮して取得しました。GCC-2.95.3を圧縮することにより、CCC-2.95.3を圧縮することにより、列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、3、4は、圧縮のみで、VCDIFFからの圧縮速度がGZIPよりも悪い、圧縮よりも優れていることを示しています。
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データ形式を残して、将来的に必要になったときにセカンダリコンプレッサーの使用を実装できるようにすることをお勧めします。このようなコンプレッサーまたは将来定義される可能性のあるコンプレッサーを介した圧縮データの形式は、実装に開かれたままになります。これらには、Huffmanエンコード、算術エンコード、およびスプレーツリーエンコードが含まれます[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、Jeff Mogul、Arthur Van Hoffに感謝します。特に、ジェフはここに示されているデータ形式の説明を明確にするのに役立ちました。
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は、Phong VoのVCodexライブラリのデータ変換方法として実装されています。AT＆T Corp.は、http/1.1 Deltaエンコード[10,11]を介してデータを送信するために誰でも使用できるVCodexのソースコードを利用できるようにしました。ソースコードとライセンスに従って、以下のURLでアクセスできます。
http://www.research.att.com/sw/tools
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の手順に関する情報は、BCP 11に記載されています。この仕様の実施者またはユーザーによるそのような独自の権利を使用するための一般的なライセンスまたは許可を取得するために行われたのは、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）は、セカンダリコンプレッサー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、Inc.、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. ZIVおよびA. LEMPEL、シーケンシャルデータ圧縮のユニバーサルアルゴリズム、IEEE Trans。情報理論、23（3）：337-343、1977。
[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、宇宙経済的接尾辞ツリー構造アルゴリズム、Journal of the 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、Deltaアルゴリズムの実証研究、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、Deltaアルゴリズム：実証分析、ACM Trans。ソフトウェアエンジニアリングと方法論、7：192-214、1998。
[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。1991年夏のUsenix Conferenceの
[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。ガイリー、The Data Compression Book、ISBN 1-55851- 434-1、M＆T Books、ニューヨーク、ニューヨーク、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. Mogul、F。Douglis、A。Feldmann、および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] Mogul、J.、Krishnamurthy、B.、Douglis、F.、Feldmann、A.、Goland、Y.、A。VanHoff、「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] Bradner、S。、「要件レベルを示すためにRFCで使用するためのキーワード」、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.
[13] Narten、T。およびH. Alvestrand、「RFCSでIANA考慮事項セクションを書くためのガイドライン」、BCP 26、RFC 2434、1998年10月。
[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
Kiem-Phong Vo（メインコンタクト）AT＆Tラボ、ルームD223 180パークアベニューフローハムパーク、ニュージャージー07932
Phone: 1 973 360 8630 EMail: kpv@research.att.com
電話：1 973 360 8630メール：kpv@research.att.com
David G. Korn AT&T Labs, Room D237 180 Park Avenue Florham Park, NJ 07932
David G. Korn AT＆T Labs、ルームD237 180パークアベニューフローハムパーク、ニュージャージー07932
Phone: 1 973 360 8602 EMail: dgk@research.att.com
電話：1 973 360 8602メール：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. Mogul Western Research Laboratory Hewlett-Packard Company 1501 Page Mill Road、MS 1251 Palo Alto、California、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ソーダホールバークレー、カリフォルニア94720
EMail: jmacd@cs.berkeley.edu
Copyright (C) The Internet Society (2002). All Rights Reserved.
Copyright（c）The Internet Society（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エディター機能の資金は現在、インターネット協会によって提供されています。