RFC1951 日本語訳
1951 DEFLATE Compressed Data Format Specification version 1.3. P.Deutsch. May 1996. (Format: TXT=36944, PS=57408, PDF=56620 bytes) (Status: INFORMATIONAL)
プログラムでの自動翻訳です。
RFC一覧
英語原文
Network Working Group P. Deutsch Request for Comments: 1951 Aladdin Enterprises Category: Informational May 1996
コメントを求めるワーキンググループP.ドイツ語要求をネットワークでつないでください: 1951年のアラジンエンタープライズカテゴリ: 情報の1996年5月
DEFLATE Compressed Data Format Specification version 1.3
DEFLATE Compressed Data Format Specificationバージョン1.3
Status of This Memo
このメモの状態
This memo provides information for the Internet community. This memo does not specify an Internet standard of any kind. Distribution of this memo is unlimited.
このメモはインターネットコミュニティのための情報を提供します。 このメモはどんな種類のインターネット標準も指定しません。 このメモの分配は無制限です。
IESG Note:
IESGは以下に注意します。
The IESG takes no position on the validity of any Intellectual Property Rights statements contained in this document.
IESGは本書では含まれたどんなIntellectual Property Rights声明の正当性の立場も全く取りません。
Notices
通知
Copyright (c) 1996 L. Peter Deutsch
Copyright(c)1996L.ピーター、ドイツ語
Permission is granted to copy and distribute this document for any purpose and without charge, including translations into other languages and incorporation into compilations, provided that the copyright notice and this notice are preserved, and that any substantive changes or deletions from the original are clearly marked.
どんな目的のためのこのドキュメントもコピーして、配布するために許可を与えます、そして、無償に、明確に他の言語への翻訳と編集、版権情報とこの通知が保存されるか、そして、およびそれへの編入を含んでいるか、どんな実名詞も変えるオリジナルからの削除をマークします。
A pointer to the latest version of this and related documentation in HTML format can be found at the URL <ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html>.
URL<ftp://ftp.uu.net/グラフィックス/png/ドキュメント/zlib/zdoc-index.html>でこの最新版への指針とHTML形式における関連するドキュメンテーションを見つけることができます。
Abstract
要約
This specification defines a lossless compressed data format that compresses data using a combination of the LZ77 algorithm and Huffman coding, with efficiency comparable to the best currently available general-purpose compression methods. The data can be produced or consumed, even for an arbitrarily long sequentially presented input data stream, using only an a priori bounded amount of intermediate storage. The format can be implemented readily in a manner not covered by patents.
この仕様はLZ77アルゴリズムとハフマンコード化の組み合わせを使用することでデータを圧縮するlossless圧縮されたデータの形式を定義します、最も良い現在利用可能な汎用圧縮方法に匹敵する効率で。 データを作り出すか、または消費できます、連続して提示された任意に長い入力データ・ストリームのためにさえ、先験的な境界がある量の中間的ストレージだけを使用して。 特許でカバーされなかった方法で容易に形式を実装することができます。
Deutsch Informational [Page 1] RFC 1951 DEFLATE Compressed Data Format Specification May 1996
情報[1ページ]のRFC1951が圧縮されたデータの形式仕様1996年5月に空気を抜かせるドイツ語
Table of Contents
目次
1. Introduction ................................................... 2
1.1. Purpose ................................................... 2
1.2. Intended audience ......................................... 3
1.3. Scope ..................................................... 3
1.4. Compliance ................................................ 3
1.5. Definitions of terms and conventions used ................ 3
1.6. Changes from previous versions ............................ 4
2. Compressed representation overview ............................. 4
3. Detailed specification ......................................... 5
3.1. Overall conventions ....................................... 5
3.1.1. Packing into bytes .................................. 5
3.2. Compressed block format ................................... 6
3.2.1. Synopsis of prefix and Huffman coding ............... 6
3.2.2. Use of Huffman coding in the "deflate" format ....... 7
3.2.3. Details of block format ............................. 9
3.2.4. Non-compressed blocks (BTYPE=00) ................... 11
3.2.5. Compressed blocks (length and distance codes) ...... 11
3.2.6. Compression with fixed Huffman codes (BTYPE=01) .... 12
3.2.7. Compression with dynamic Huffman codes (BTYPE=10) .. 13
3.3. Compliance ............................................... 14
4. Compression algorithm details ................................. 14
5. References .................................................... 16
6. Security Considerations ....................................... 16
7. Source code ................................................... 16
8. Acknowledgements .............................................. 16
9. Author's Address .............................................. 17
1. 序論… 2 1.1. 目的… 2 1.2. 聴衆は意図しました… 3 1.3. 範囲… 3 1.4. 承諾… 3 1.5. 用語と使用されるコンベンションの定義… 3 1.6. 旧バージョンからの変化… 4 2. 表現概要を圧縮します… 4 3. 詳細な仕様… 5 3.1. 総合的なコンベンション… 5 3.1.1. バイトに荷造りします… 5 3.2. ブロックフォーマットを圧縮します… 6 3.2.1. 接頭語とハフマンコード化の構文… 6 3.2.2. 「空気を抜いてください」という形式におけるハフマンコード化の使用… 7 3.2.3. ブロックフォーマットの詳細… 9 3.2.4. 非圧縮ブロック(BTYPE=00)… 11 3.2.5. ブロック(長さと距離コード)を圧縮します… 11 3.2.6. 固定ハフマンとの圧縮は(BTYPE=01)をコード化します… 12 3.2.7. ダイナミックなハフマンとの圧縮は(BTYPE=10)をコード化します。 13 3.3. 承諾… 14 4. 圧縮アルゴリズムの詳細… 14 5. 参照… 16 6. セキュリティ問題… 16 7. ソースコード… 16 8. 承認… 16 9. 作者のアドレス… 17
1. Introduction
1. 序論
1.1. Purpose
1.1. 目的
The purpose of this specification is to define a lossless
compressed data format that:
* Is independent of CPU type, operating system, file system,
and character set, and hence can be used for interchange;
* Can be produced or consumed, even for an arbitrarily long
sequentially presented input data stream, using only an a
priori bounded amount of intermediate storage, and hence
can be used in data communications or similar structures
such as Unix filters;
* Compresses data with efficiency comparable to the best
currently available general-purpose compression methods,
and in particular considerably better than the "compress"
program;
* Can be implemented readily in a manner not covered by
patents, and hence can be practiced freely;
この仕様の目的がlosslessを定義するのがデータの形式を圧縮したということである、それ: * CPUタイプ、オペレーティングシステム、ファイルシステム、および文字集合から独立していて、したがって、置き換えに使用できます。 * 先験的な境界がある量の中間的ストレージだけを使用して、連続して提示された任意に長い入力データ・ストリームのためにさえ生産するか、または消費できて、したがって、Unixフィルタなどのデータ通信か類似構造物で使用できます。 * 最も良い現在利用可能な汎用圧縮方法、特定で匹敵する効率が「湿布」よりかなり良いデータがプログラムする湿布。 * 特許でカバーされなかった方法で容易に実装することができて、したがって、自由に練習できます。
Deutsch Informational [Page 2] RFC 1951 DEFLATE Compressed Data Format Specification May 1996
情報[2ページ]のRFC1951が圧縮されたデータの形式仕様1996年5月に空気を抜かせるドイツ語
* Is compatible with the file format produced by the current
widely used gzip utility, in that conforming decompressors
will be able to read data produced by the existing gzip
compressor.
* 広く使用された現在のgzipユーティリティによって作り出されるファイル形式と互換性があって、そんなに従っている減圧装置で既存のgzipコンプレッサーによって作り出されたデータは読むことができるでしょう。
The data format defined by this specification does not attempt to:
この仕様で定義されたデータの形式は、以下のことを試みません。
* Allow random access to compressed data;
* Compress specialized data (e.g., raster graphics) as well
as the best currently available specialized algorithms.
* 圧縮されたデータにランダムアクセスを許容してください。 * 最も良い現在利用可能な専門化しているアルゴリズムと同様に専門化しているデータ(例えば、ラスタグラフィックス)を圧縮してください。
A simple counting argument shows that no lossless compression
algorithm can compress every possible input data set. For the
format defined here, the worst case expansion is 5 bytes per 32K-
byte block, i.e., a size increase of 0.015% for large data sets.
English text usually compresses by a factor of 2.5 to 3;
executable files usually compress somewhat less; graphical data
such as raster images may compress much more.
簡単な勘定議論は、どんな可逆圧縮アルゴリズムもあらゆる可能な入力データセットを圧縮できるというわけではないのを示します。 ここで定義された書式のために、32Kバイトのブロック(すなわち、大きいデータセットのための0.015%のサイズ増加)あたり最悪の場合拡張は5バイトです。 通常、英文は2.5〜3の要素を圧縮します。 通常、実行可能なファイルは以下をいくらか圧縮します。 ラスター・イメージなどのグラフィカルなデータははるかに多くを圧縮するかもしれません。
1.2. Intended audience
1.2. 対象とする訪問者
This specification is intended for use by implementors of software
to compress data into "deflate" format and/or decompress data from
"deflate" format.
この仕様はソフトウェアの作成者による使用が「空気を抜いてください」という形式にデータを圧縮する、そして/または、「空気を抜いてください」という形式からデータを減圧することを意図します。
The text of the specification assumes a basic background in
programming at the level of bits and other primitive data
representations. Familiarity with the technique of Huffman coding
is helpful but not required.
仕様のテキストはビットと他の原始のデータ表現のレベルでプログラムを作る際に基本的なバックグラウンドを仮定します。 ハフマンコード化のテクニックへの親しみは、役立っていますが、必要ではありません。
1.3. Scope
1.3. 範囲
The specification specifies a method for representing a sequence
of bytes as a (usually shorter) sequence of bits, and a method for
packing the latter bit sequence into bytes.
仕様は、ビットの(通常より短い)の系列としてバイトの系列を表すのにメソッドを指定して、後者の噛み付いている系列にバイトに詰め込むためにメソッドを指定します。
1.4. Compliance
1.4. 承諾
Unless otherwise indicated below, a compliant decompressor must be
able to accept and decompress any data set that conforms to all
the specifications presented here; a compliant compressor must
produce data sets that conform to all the specifications presented
here.
別の方法で以下で示されない場合、対応する減圧装置は、ここに提示されたすべての仕様に従うどんなデータセットも、受け入れて、減圧できなければなりません。 言いなりになっているコンプレッサーはここに提示されたすべての仕様に従うデータセットを作り出さなければなりません。
1.5. Definitions of terms and conventions used
1.5. 用語と使用されるコンベンションの定義
Byte: 8 bits stored or transmitted as a unit (same as an octet).
For this specification, a byte is exactly 8 bits, even on machines
バイト: 8ビットは、ユニットとして(八重奏と同じ)で保存したか、または伝わりました。 この仕様に関しては、ちょうどマシンの上にさえ1バイトがあります。
Deutsch Informational [Page 3] RFC 1951 DEFLATE Compressed Data Format Specification May 1996
情報[3ページ]のRFC1951が圧縮されたデータの形式仕様1996年5月に空気を抜かせるドイツ語
which store a character on a number of bits different from eight.
See below, for the numbering of bits within a byte.
8と異なった多くのビットの上にキャラクタを保存します。 ビットの付番に関して1バイト以内で以下を見てください。
String: a sequence of arbitrary bytes.
以下を結んでください。 任意のバイトの系列。
1.6. Changes from previous versions
1.6. 旧バージョンからの変化
There have been no technical changes to the deflate format since
version 1.1 of this specification. In version 1.2, some
terminology was changed. Version 1.3 is a conversion of the
specification to RFC style.
技術変化が全くなかった、この仕様のバージョン1.1以来の形式に空気を抜かせてください。 バージョン1.2では、何らかの用語を変えました。 バージョン1.3はRFCスタイルへの仕様の変換です。
2. Compressed representation overview
2. 圧縮された表現概要
A compressed data set consists of a series of blocks, corresponding to successive blocks of input data. The block sizes are arbitrary, except that non-compressible blocks are limited to 65,535 bytes.
連続したブロックの入力データに対応している、圧縮されたデータセットは一連のブロックから成ります。 非圧縮性のブロックが6万5535バイトに制限されるのを除いて、ブロック・サイズは任意です。
Each block is compressed using a combination of the LZ77 algorithm and Huffman coding. The Huffman trees for each block are independent of those for previous or subsequent blocks; the LZ77 algorithm may use a reference to a duplicated string occurring in a previous block, up to 32K input bytes before.
各ブロックは、LZ77アルゴリズムとハフマンコード化の組み合わせを使用することで圧縮されます。 前の、または、その後のブロックにおいて、各ブロックハフマン木はそれらから独立しています。 LZ77アルゴリズムは以前前のブロックと、最大32K入力されたバイトで現れるコピーされたストリングの参照を使用するかもしれません。
Each block consists of two parts: a pair of Huffman code trees that describe the representation of the compressed data part, and a compressed data part. (The Huffman trees themselves are compressed using Huffman encoding.) The compressed data consists of a series of elements of two types: literal bytes (of strings that have not been detected as duplicated within the previous 32K input bytes), and pointers to duplicated strings, where a pointer is represented as a pair <length, backward distance>. The representation used in the "deflate" format limits distances to 32K bytes and lengths to 258 bytes, but does not limit the size of a block, except for uncompressible blocks, which are limited as noted above.
各ブロックは2つの部品から成ります: ハフマンの1組は圧縮されたデータ部分の表現、および圧縮されたデータ部分について説明する木をコード化します。 (ハフマン木自体はハフマン符号化を使用することで圧縮されます。) 圧縮されたデータは2つのタイプの一連の要素から成ります: 文字通りのバイト(前の32Kの入力バイトの中にコピーされるように検出されていないストリングの)、およびコピーされたストリングへの指針。そこでは、指針が組<の長さ、後方の距離>として表されます。 「空気を抜いてください」という形式に使用される表現は、距離を258バイトまでの32Kのバイトと長さに制限しますが、1ブロックのサイズを制限しません、uncompressibleブロックを除いて。(ブロックは上で述べたように制限されます)。
Each type of value (literals, distances, and lengths) in the compressed data is represented using a Huffman code, using one code tree for literals and lengths and a separate code tree for distances. The code trees for each block appear in a compact form just before the compressed data for that block.
圧縮されたデータのそれぞれのタイプの値(リテラル、距離、および長さ)はハフマン符号を使用することで表されます、リテラル、長さ、および別々の符号樹に1つの符号樹を距離に使用して。 各ブロック符号樹はそのブロック圧縮されたデータのすぐ前のコンパクト形に現れます。
Deutsch Informational [Page 4] RFC 1951 DEFLATE Compressed Data Format Specification May 1996
情報[4ページ]のRFC1951が圧縮されたデータの形式仕様1996年5月に空気を抜かせるドイツ語
3. Detailed specification
3. 仕様詳細
3.1. Overall conventions In the diagrams below, a box like this:
3.1. ダイヤグラム下、aが詰め込む総合的なコンベンションInはこれが好きです:
+---+
| | <-- the vertical bars might be missing
+---+
+---+ | | <-- 縦棒は+を逃しているかもしれません。---+
represents one byte; a box like this:
1バイトを表します。 このような箱:
+==============+
| |
+==============+
+==============+ | | +==============+
represents a variable number of bytes.
可変バイト数を表します。
Bytes stored within a computer do not have a "bit order", since
they are always treated as a unit. However, a byte considered as
an integer between 0 and 255 does have a most- and least-
significant bit, and since we write numbers with the most-
significant digit on the left, we also write bytes with the most-
significant bit on the left. In the diagrams below, we number the
bits of a byte so that bit 0 is the least-significant bit, i.e.,
the bits are numbered:
それらが一体にしていつも扱われるので、コンピュータの中に保存されたバイトは「噛み付いているオーダー」を持っていません。 しかしながら、0〜255の整数であるとみなされた1バイトはだいたいと最少重要なビットを持っています、そして、左における最も多くの有効数字に従った数を書くので、また、私たちは大部分が重要な状態で左で噛み付かれたバイトを書きます。 以下のダイヤグラムで、私たちが1バイトのビットに付番するのでビット0が最下位ビットである、すなわち、ビットは番号付です:
+--------+
|76543210|
+--------+
+--------+ |76543210| +--------+
Within a computer, a number may occupy multiple bytes. All
multi-byte numbers in the format described here are stored with
the least-significant byte first (at the lower memory address).
For example, the decimal number 520 is stored as:
コンピュータの中では、数は複数のバイトを占領するかもしれません。 ここで説明された形式のすべてのマルチバイト番号が最初に(下側のメモリアドレスで)、最も最少に重要なバイトで保存されます。 例えば、10進数520は以下として保存されます。
0 1
+--------+--------+
|00001000|00000010|
+--------+--------+
^ ^
| |
| + more significant byte = 2 x 256
+ less significant byte = 8
0 1 +--------+--------+ |00001000|00000010| +--------+--------+ ^ ^ | | | + それほどより重要なバイト=2x256+重要でないバイト=8
3.1.1. Packing into bytes
3.1.1. バイトに荷造りします。
This document does not address the issue of the order in which
bits of a byte are transmitted on a bit-sequential medium,
since the final data format described here is byte- rather than
このドキュメントは1バイトのビットが少し連続した媒体の上で伝えられるオーダーの問題を扱いません、ここで説明された最終データ形式がむしろバイトであるので
Deutsch Informational [Page 5] RFC 1951 DEFLATE Compressed Data Format Specification May 1996
情報[5ページ]のRFC1951が圧縮されたデータの形式仕様1996年5月に空気を抜かせるドイツ語
bit-oriented. However, we describe the compressed block format
in below, as a sequence of data elements of various bit
lengths, not a sequence of bytes. We must therefore specify
how to pack these data elements into bytes to form the final
compressed byte sequence:
ビット指向です。 しかしながら、私たちは下で圧縮されたブロックフォーマットについて説明します、系列ではなく、様々な噛み付いている長さのバイトのデータ要素の系列として。 したがって、私たちは最終的な圧縮されたバイト列を形成するためにこれらのデータ要素にバイトに詰め込む方法を指定しなければなりません:
* Data elements are packed into bytes in order of
increasing bit number within the byte, i.e., starting
with the least-significant bit of the byte.
* Data elements other than Huffman codes are packed
starting with the least-significant bit of the data
element.
* Huffman codes are packed starting with the most-
significant bit of the code.
* バイトの中で噛み付いている数を増強することの順にデータ要素はバイトに詰め込まれます、すなわち、バイトの最下位ビットをきっかけに。 * ハフマン符号以外のデータ要素はデータ要素の最下位ビットをきっかけに梱包されます。 * コードの重要なビットから最も始まって、ハフマン符号は詰まっています。
In other words, if one were to print out the compressed data as
a sequence of bytes, starting with the first byte at the
*right* margin and proceeding to the *left*, with the most-
significant bit of each byte on the left as usual, one would be
able to parse the result from right to left, with fixed-width
elements in the correct MSB-to-LSB order and Huffman codes in
bit-reversed order (i.e., with the first bit of the code in the
relative LSB position).
言い換えれば、1つがバイトの系列として圧縮されたデータを印刷するつもりであったなら、*権利*マージンにおける最初のバイトから始まって、*に続くのは通常通りの左のそれぞれのバイトのビットに大部分が重要の*を残して、1つは左への権利から結果を分析できるでしょう、MSBからLSBへの正しいオーダーにおける固定幅の要素とビットで逆にされたオーダー(すなわち、相対的なLSB位置における、コードの最初のビットがある)におけるハフマン符号で。
3.2. Compressed block format
3.2. 圧縮されたブロックフォーマット
3.2.1. Synopsis of prefix and Huffman coding
3.2.1. 接頭語とハフマンコード化の構文
Prefix coding represents symbols from an a priori known
alphabet by bit sequences (codes), one code for each symbol, in
a manner such that different symbols may be represented by bit
sequences of different lengths, but a parser can always parse
an encoded string unambiguously symbol-by-symbol.
各シンボル、方法で、異なったシンボルが表されるかもしれないそのようなものが異なった長さの系列に噛み付きましたが、パーサが明白にシンボルごとにいつもコード化されたストリングを分析できるので、接頭語コード化は噛み付いている系列(コード)、1つのコードで先験的な知られているアルファベットからシンボルを表します。
We define a prefix code in terms of a binary tree in which the
two edges descending from each non-leaf node are labeled 0 and
1 and in which the leaf nodes correspond one-for-one with (are
labeled with) the symbols of the alphabet; then the code for a
symbol is the sequence of 0's and 1's on the edges leading from
the root to the leaf labeled with that symbol. For example:
私たちがそれぞれの非葉のノードから離す2つの縁が0と1とラベルされて、葉のノードが対応する2進の木に関して接頭語コードを定義する、個人的には1、(ラベルされる、)、アルファベットのシンボル。 そして、シンボルのためのコードは、根からそのシンボルでラベルされた葉まで導く0の系列と縁の1です。 例えば:
Deutsch Informational [Page 6] RFC 1951 DEFLATE Compressed Data Format Specification May 1996
情報[6ページ]のRFC1951が圧縮されたデータの形式仕様1996年5月に空気を抜かせるドイツ語
/\ Symbol Code
0 1 ------ ----
/ \ A 00
/\ B B 1
0 1 C 011
/ \ D 010
A /\
0 1
/ \
D C
/\シンボルは0 1をコード化します。------ ---- /、\、A00/\B B1 0 1C011/\D010A/%%BODY%% 1/\D C
A parser can decode the next symbol from an encoded input
stream by walking down the tree from the root, at each step
choosing the edge corresponding to the next input bit.
パーサはコード化された入力ストリームから木を根から歩くことによって、次のシンボルを解読できます、次の入力ビットに対応する縁を選ぶ各ステップで。
Given an alphabet with known symbol frequencies, the Huffman
algorithm allows the construction of an optimal prefix code
(one which represents strings with those symbol frequencies
using the fewest bits of any possible prefix codes for that
alphabet). Such a code is called a Huffman code. (See
reference [1] in Chapter 5, references for additional
information on Huffman codes.)
知られているシンボル頻度があるアルファベットを考えて、ハフマンアルゴリズムは最適の接頭語コード(そのアルファベットにどんな可能な接頭語コードの最も数ビットしかも使用しないことでそれらのシンボル頻度でストリングを表すもの)の工事を許します。 そのようなコードはハフマン符号と呼ばれます。 (第5章における参照[1]、ハフマン符号に関する追加情報の参照を見てください。)
Note that in the "deflate" format, the Huffman codes for the
various alphabets must not exceed certain maximum code lengths.
This constraint complicates the algorithm for computing code
lengths from symbol frequencies. Again, see Chapter 5,
references for details.
「空気を抜いてください」という形式では、様々なアルファベットのためのハフマン符号が、ある最大のコードの長さを超えてはいけないことに注意してください。 この規制はシンボル頻度からコードの長さを計算するためのアルゴリズムを複雑にします。 もう一度、第5章、詳細の参照を見てください。
3.2.2. Use of Huffman coding in the "deflate" format
3.2.2. 「空気を抜いてください」という形式におけるハフマンコード化の使用
The Huffman codes used for each alphabet in the "deflate"
format have two additional rules:
「空気を抜いてください」という形式における各アルファベットに使用されるハフマン符号は2つの付則を持っています:
* All codes of a given bit length have lexicographically
consecutive values, in the same order as the symbols
they represent;
* 与えられた噛み付いている長さのすべてのコードには、彼らが表すシンボルとして同次における辞書編集に連続した値があります。
* Shorter codes lexicographically precede longer codes.
* より短いコードは辞書編集により長いコードに先行します。
Deutsch Informational [Page 7] RFC 1951 DEFLATE Compressed Data Format Specification May 1996
情報[7ページ]のRFC1951が圧縮されたデータの形式仕様1996年5月に空気を抜かせるドイツ語
We could recode the example above to follow this rule as
follows, assuming that the order of the alphabet is ABCD:
私たちは以下のこの規則に従うためには上記の例を再コード化できました、アルファベットの注文がABCDであると仮定して:
Symbol Code
------ ----
A 10
B 0
C 110
D 111
シンボルコード------ ---- A10B0C110D111
I.e., 0 precedes 10 which precedes 11x, and 110 and 111 are
lexicographically consecutive.
すなわち、0は10に先行します、そして、(11xに先行します)110と111は辞書編集に連続しています。
Given this rule, we can define the Huffman code for an alphabet
just by giving the bit lengths of the codes for each symbol of
the alphabet in order; this is sufficient to determine the
actual codes. In our example, the code is completely defined
by the sequence of bit lengths (2, 1, 3, 3). The following
algorithm generates the codes as integers, intended to be read
from most- to least-significant bit. The code lengths are
initially in tree[I].Len; the codes are produced in
tree[I].Code.
この規則を考えて、私たちはアルファベットのためにアルファベットの各シンボルのためのコードの噛み付いている長さを整然とするのに与えるだけでハフマン符号を定義できます。 これは、実際のコードを決定するために十分です。 私たちの例では、コードは噛み付いている長さ(2、1、3、3)の系列によって完全に定義されます。 以下のアルゴリズムは大部分から最下位ビットまで読まれることを意図する整数としてコードを生成します。 初めは、コードの長さが木[I].Lenにあります。 コードは木[I].Codeで作成されます。
1) Count the number of codes for each code length. Let
bl_count[N] be the number of codes of length N, N >= 1.
1) それぞれのコードの長さのためにコードの数を数えてください。 bl_カウント[N]が長さN、N>=1のコードの数であることをさせてください。
2) Find the numerical value of the smallest code for each
code length:
2) それぞれのコードの長さに関して最も小さいコードの数値を見つけてください:
code = 0;
bl_count[0] = 0;
for (bits = 1; bits <= MAX_BITS; bits++) {
code = (code + bl_count[bits-1]) << 1;
next_code[bits] = code;
}
=0をコード化してください。 bl_カウント[0]=0。 (ビット=1; ビット<=マックス_BITS; ビット++)コードは<<1と等しいです(コード+bl_カウント[ビット-1]); 次の_コード[ビット]=コード
3) Assign numerical values to all codes, using consecutive
values for all codes of the same length with the base
values determined at step 2. Codes that are never used
(which have a bit length of zero) must not be assigned a
value.
3) すべてのコードに数値を割り当ててください、基礎点が決定していた状態で同じ長さのすべてのコードにステップ2で連続した値を使用して。 決して使用されないコード(ゼロの長さを少し持っている)に値を割り当ててはいけません。
for (n = 0; n <= max_code; n++) {
len = tree[n].Len;
if (len != 0) {
tree[n].Code = next_code[len];
next_code[len]++;
}
(n=0; 最大_n<=コード; n++)、lenは(len!=0)であるなら木[n].Lenと等しいです。木[n].Codeは次の_コード[len]と等しいです; 次の_コード[len]++
Deutsch Informational [Page 8] RFC 1951 DEFLATE Compressed Data Format Specification May 1996
情報[8ページ]のRFC1951が圧縮されたデータの形式仕様1996年5月に空気を抜かせるドイツ語
}
}
Example:
例:
Consider the alphabet ABCDEFGH, with bit lengths (3, 3, 3, 3,
3, 2, 4, 4). After step 1, we have:
アルファベットが噛み付いている長さ(3、3、3、3、3、2、4、4)があるABCDEFGHであると考えてください。 ステップ1後に、私たちには、以下があります。
N bl_count[N]
- -----------
2 1
3 5
4 2
N bl_カウント[N]、------------ 2 1 3 5 4 2
Step 2 computes the following next_code values:
ステップ2は次の_コードが評価する以下を計算します:
N next_code[N]
- ------------
1 0
2 0
3 2
4 14
次のN_コード[N]、------------- 1 0 2 0 3 2 4 14
Step 3 produces the following code values:
ステップ3は以下のコード値を生産します:
Symbol Length Code
------ ------ ----
A 3 010
B 3 011
C 3 100
D 3 101
E 3 110
F 2 00
G 4 1110
H 4 1111
シンボル長さのコード------ ------ ---- 1110時間4のA3 010B3 011C3 100D3 101E3 110F2 00G4、1111
3.2.3. Details of block format
3.2.3. ブロックフォーマットの詳細
Each block of compressed data begins with 3 header bits
containing the following data:
3ヘッダービットが以下のデータを含んでいて、それぞれのブロックの圧縮されたデータは始まります:
first bit BFINAL
next 2 bits BTYPE
最初のビットのBFINALの次の2ビットのBTYPE
Note that the header bits do not necessarily begin on a byte
boundary, since a block does not necessarily occupy an integral
number of bytes.
ヘッダービットが必ずバイト境界で始まるというわけではないことに注意してください、ブロックが必ず整数のバイトを占領するというわけではないので。
Deutsch Informational [Page 9] RFC 1951 DEFLATE Compressed Data Format Specification May 1996
情報[9ページ]のRFC1951が圧縮されたデータの形式仕様1996年5月に空気を抜かせるドイツ語
BFINAL is set if and only if this is the last block of the data
set.
BFINALが用意ができている、これである場合にだけ、データセットの最後のブロックはそうです。
BTYPE specifies how the data are compressed, as follows:
BTYPEはデータが以下の通りどう圧縮されるかを指定します:
00 - no compression
01 - compressed with fixed Huffman codes
10 - compressed with dynamic Huffman codes
11 - reserved (error)
予約された00(01(固定ハフマン符号10で、圧縮される)がダイナミックなハフマン符号11で圧縮しなかった圧縮全く)(誤り)
The only difference between the two compressed cases is how the
Huffman codes for the literal/length and distance alphabets are
defined.
2つの圧縮されたケースの唯一の違いはリテラル/長さと距離アルファベットのためのハフマン符号がどう定義されるかということです。
In all cases, the decoding algorithm for the actual data is as
follows:
すべての場合では、実際のデータのための解読アルゴリズムは以下の通りです:
do
read block header from input stream.
if stored with no compression
skip any remaining bits in current partially
processed byte
read LEN and NLEN (see next section)
copy LEN bytes of data to output
otherwise
if compressed with dynamic Huffman codes
read representation of code trees (see
subsection below)
loop (until end of block code recognized)
decode literal/length value from input stream
if value < 256
copy value (literal byte) to output stream
otherwise
if value = end of block (256)
break from loop
otherwise (value = 257..285)
decode distance from input stream
入力ストリームからブロックヘッダーを読んでください; 圧縮なしで保存されるなら、現在の部分的に処理されたLENが読まれたバイトであらゆる残っているビットをスキップしてください。そうすれば、ダイナミックなハフマン符号で圧縮されるなら、そうでなければ出力するNLEN(次のセクションを見る)コピーLENバイトのデータは符号樹の表現を読みます(以下の小区分を見てください); そうでなければ、値の<256が輪からのブロック(256)中断の値=終わりであるなら値(文字通りのバイト)を出力ストリームにコピーするなら、輪(認識されたブロック・コードの終わりまでの)は入力ストリームからリテラル/長さの値を解読します。そうでなければ、(値=257.285)は入力ストリームから距離を解読します。
move backwards distance bytes in the output
stream, and copy length bytes from this
position to the output stream.
end loop
while not last block
出力ストリームで距離バイトを後方に移行させて、コピー長さのバイトをこの位置から出力ストリームまで移行させてください。最後のブロックでない間、輪を終わらせてください。
Note that a duplicated string reference may refer to a string
in a previous block; i.e., the backward distance may cross one
or more block boundaries. However a distance cannot refer past
the beginning of the output stream. (An application using a
コピーされたストリング参照が前のブロックでストリングについて言及するかもしれないことに注意してください。 すなわち、後方の距離は1ブロック以上の境界に交差するかもしれません。 しかしながら、距離は出力ストリームの始まりを過ぎて参照されることができません。 (aを使用するアプリケーション
Deutsch Informational [Page 10] RFC 1951 DEFLATE Compressed Data Format Specification May 1996
情報[10ページ]のRFC1951が圧縮されたデータの形式仕様1996年5月に空気を抜かせるドイツ語
preset dictionary might discard part of the output stream; a
distance can refer to that part of the output stream anyway)
Note also that the referenced string may overlap the current
position; for example, if the last 2 bytes decoded have values
X and Y, a string reference with <length = 5, distance = 2>
adds X,Y,X,Y,X to the output stream.
あらかじめセットされて、辞書は出力ストリームの一部を捨てるかもしれません。 出力ストリームをとにかく離れさせる缶が言及する距離) また、参照をつけられたストリングが現在の位置を重ね合わせるかもしれないことに注意してください。 例えば、<の長さがあるストリング参照解読された最後の2バイトが値XとYを持っているなら=5、2距離=>はXを加えます、Y、X、Y、出力ストリームへのX。
We now specify each compression method in turn.
私たちは現在、順番に各圧縮方法を指定します。
3.2.4. Non-compressed blocks (BTYPE=00)
3.2.4. 非圧縮ブロック(BTYPE=00)
Any bits of input up to the next byte boundary are ignored.
The rest of the block consists of the following information:
次のバイト境界までのどんなビットの入力も無視されます。 ブロックの残りは以下の情報から成ります:
0 1 2 3 4...
+---+---+---+---+================================+
| LEN | NLEN |... LEN bytes of literal data...|
+---+---+---+---+================================+
0 1 2 3 4... +---+---+---+---+================================+ | レン| NLEN|... LENバイトの文字通りのデータ…| +---+---+---+---+================================+
LEN is the number of data bytes in the block. NLEN is the
one's complement of LEN.
LENはブロックのデータ・バイトの数です。 NLENはLENの1の補数です。
3.2.5. Compressed blocks (length and distance codes)
3.2.5. 圧縮ブロック(長さと距離コード)
As noted above, encoded data blocks in the "deflate" format
consist of sequences of symbols drawn from three conceptually
distinct alphabets: either literal bytes, from the alphabet of
byte values (0..255), or <length, backward distance> pairs,
where the length is drawn from (3..258) and the distance is
drawn from (1..32,768). In fact, the literal and length
alphabets are merged into a single alphabet (0..285), where
values 0..255 represent literal bytes, the value 256 indicates
end-of-block, and values 257..285 represent length codes
(possibly in conjunction with extra bits following the symbol
code) as follows:
上で述べたように、「空気を抜いてください」という形式のコード化されたデータ・ブロックは3つの概念的に異なったアルファベットから得られたシンボルの系列から成ります: バイト値(0 .255)のアルファベットからの文字通りのバイトか<の長さのどちらか、後方の距離>(長さは(3 .258)から引き出されて、距離は(1..32、768)から引き出される)は対にされます。 事実上、リテラルと長さのアルファベットはただ一つのアルファベット(0 .285)に合併されていて、どこが0を評価するか。255 文字通りのバイトを表してください、そして、値256はブロックの端、および値257を示します。285 以下の長さのコード(ことによるとシンボルコードに従う付加的なビットに関連した)を表してください:
Deutsch Informational [Page 11] RFC 1951 DEFLATE Compressed Data Format Specification May 1996
情報[11ページ]のRFC1951が圧縮されたデータの形式仕様1996年5月に空気を抜かせるドイツ語
Extra Extra Extra
Code Bits Length(s) Code Bits Lengths Code Bits Length(s)
---- ---- ------ ---- ---- ------- ---- ---- -------
257 0 3 267 1 15,16 277 4 67-82
258 0 4 268 1 17,18 278 4 83-98
259 0 5 269 2 19-22 279 4 99-114
260 0 6 270 2 23-26 280 4 115-130
261 0 7 271 2 27-30 281 5 131-162
262 0 8 272 2 31-34 282 5 163-194
263 0 9 273 3 35-42 283 5 195-226
264 0 10 274 3 43-50 284 5 227-257
265 1 11,12 275 3 51-58 285 0 258
266 1 13,14 276 3 59-66
付加的な付加的な付加的なコードビット長さのコードビットの長さはビットの長さをコード化します。---- ---- ------ ---- ---- ------- ---- ---- ------- 257 0 3 267 1 15,16 277 4 67-82 258 0 4 268 1 17,18 278 4 83-98 259 0 5 269 2 19-22 279 4 99-114 260 0 6 270 2 23-26 280 4 115-130 261 0 7 271 2 27-30 281 5 131-162 262 0 8 272 2 31-34 282 5 163-194 263 0 9 273 3 35-42 283 5 195-226 264 0 10 274 3 43-50 284 5 227-257 265 1 11,12 275 3 51-58 285 0 258 266 1 13,14 276 3 59-66
The extra bits should be interpreted as a machine integer
stored with the most-significant bit first, e.g., bits 1110
represent the value 14.
最初に最も多くの重要なビットで保存されて、付加的なビットはマシン整数として解釈されるべきです、例えば、ビット1110は値14を表します。
Extra Extra Extra
Code Bits Dist Code Bits Dist Code Bits Distance
---- ---- ---- ---- ---- ------ ---- ---- --------
0 0 1 10 4 33-48 20 9 1025-1536
1 0 2 11 4 49-64 21 9 1537-2048
2 0 3 12 5 65-96 22 10 2049-3072
3 0 4 13 5 97-128 23 10 3073-4096
4 1 5,6 14 6 129-192 24 11 4097-6144
5 1 7,8 15 6 193-256 25 11 6145-8192
6 2 9-12 16 7 257-384 26 12 8193-12288
7 2 13-16 17 7 385-512 27 12 12289-16384
8 3 17-24 18 8 513-768 28 13 16385-24576
9 3 25-32 19 8 769-1024 29 13 24577-32768
DistコードビットDistコードビットが遠ざける余分な余分な余分なコードビット---- ---- ---- ---- ---- ------ ---- ---- -------- 0 0 1 10 4 33-48 20 9 1025-1536 1 0 2 11 4 49-64 21 9 1537-2048 2 0 3 12 5 65-96 22 10 2049-3072 3 0 4 13 5 97-128 23 10 3073-4096 4 1 5,6 14 6 129-192 24 11 4097-6144 5 1 7,8 15 6 193-256 25 11 6145-8192 6 2 9-12 16 7 257-384 26 12 8193-12288 7 2 13-16 17 7 385-512 27 12 12289-16384 8 3 17-24 18 8 513-768 28 13 16385-24576 9 3 25-32 19 8 769-1024 29 13 24577-32768
3.2.6. Compression with fixed Huffman codes (BTYPE=01)
3.2.6. 固定ハフマン符号との圧縮(BTYPE=01)
The Huffman codes for the two alphabets are fixed, and are not
represented explicitly in the data. The Huffman code lengths
for the literal/length alphabet are:
2つのアルファベットのためのハフマン符号は、修理されていて、データに明らかに表されません。 文字通りの/長さアルファベットのためのハフマン符号の長さは以下の通りです。
Lit Value Bits Codes
--------- ---- -----
0 - 143 8 00110000 through
10111111
144 - 255 9 110010000 through
111111111
256 - 279 7 0000000 through
0010111
280 - 287 8 11000000 through
11000111
ビットがコード化する点灯された値--------- ---- ----- 0--143 8、00110000、通じて、10111111、144、--、255、9、110010000、通じて、111111111、256、--、279、7、0000000、通じて、0010111、280、--、287、8、11000000〜11000111
Deutsch Informational [Page 12] RFC 1951 DEFLATE Compressed Data Format Specification May 1996
情報[12ページ]のRFC1951が圧縮されたデータの形式仕様1996年5月に空気を抜かせるドイツ語
The code lengths are sufficient to generate the actual codes,
as described above; we show the codes in the table for added
clarity. Literal/length values 286-287 will never actually
occur in the compressed data, but participate in the code
construction.
コードの長さが上で説明されるように実際のコードを発生させることができるくらいの。 私たちは加えられた明快ためにテーブルのコードを示しています。 文字通りの/長さ値286-287は実際に圧縮されたデータに決して起こらないでしょうが、コード工事に参加してください。
Distance codes 0-31 are represented by (fixed-length) 5-bit
codes, with possible additional bits as shown in the table
shown in Paragraph 3.2.5, above. Note that distance codes 30-
31 will never actually occur in the compressed data.
距離コード0-31は(固定長)5ビットのコードによって表されます、可能な追加ビットがParagraphで表に示したように見せられている状態で3.2、.5、上です。 距離コード30- 31が実際に圧縮されたデータに決して起こらないことに注意してください。
3.2.7. Compression with dynamic Huffman codes (BTYPE=10)
3.2.7. ダイナミックなハフマン符号との圧縮(BTYPE=10)
The Huffman codes for the two alphabets appear in the block
immediately after the header bits and before the actual
compressed data, first the literal/length code and then the
distance code. Each code is defined by a sequence of code
lengths, as discussed in Paragraph 3.2.2, above. For even
greater compactness, the code length sequences themselves are
compressed using a Huffman code. The alphabet for code lengths
is as follows:
2つのアルファベットのためのハフマン符号はヘッダービット直後実際の圧縮されたデータの前のブロック、最初に、文字通りの/長さコード、および次に、距離コードに現れます。 各コードはParagraph3.2.2で議論して、上でコードの長さの系列によって定義されます。 さらに大きいコンパクト性において、コード長さの系列自体は、ハフマン符号を使用することで圧縮されます。 コードの長さのためのアルファベットは以下の通りです:
0 - 15: Represent code lengths of 0 - 15
16: Copy the previous code length 3 - 6 times.
The next 2 bits indicate repeat length
(0 = 3, ... , 3 = 6)
Example: Codes 8, 16 (+2 bits 11),
16 (+2 bits 10) will expand to
12 code lengths of 8 (1 + 6 + 5)
17: Repeat a code length of 0 for 3 - 10 times.
(3 bits of length)
18: Repeat a code length of 0 for 11 - 138 times
(7 bits of length)
0 - 15: 0--15 16のコードの長さを表してください: 3--6回前のコードの長さをコピーしてください。 次の2ビットは反復の長さ(0 = 3、3 = 6の…)の例を示します: コード8、16(+2 ビット11)、16(+2 ビット10)は12のコードの長さの8(1+6+5)に17を広くするでしょう: 3--10回のために0のコードの長さを繰り返してください。 (長さの3ビット) 18: 11--138回のために0のコードの長さを繰り返してください。(長さの7ビット)
A code length of 0 indicates that the corresponding symbol in
the literal/length or distance alphabet will not occur in the
block, and should not participate in the Huffman code
construction algorithm given earlier. If only one distance
code is used, it is encoded using one bit, not zero bits; in
this case there is a single code length of one, with one unused
code. One distance code of zero bits means that there are no
distance codes used at all (the data is all literals).
0のコードの長さは、文字通りの/長さか距離アルファベットの対応するシンボルがブロックに起こらないで、より早く与えられたハフマン符号構成アルゴリズムに参加するべきでないのを示します。 1つの距離コードだけが使用されているなら、それはゼロ・ビットではなく、1ビットを使用することでコード化されます。 この場合、ただ一つのコードの長さの1つが1つの未使用のコードと共にあります。 ゼロ・ビットの1つの距離コードが、全く使用されない距離コードがあることを意味します(データはすべて誤字誤植です)。
We can now define the format of the block:
私たちは現在、ブロックの書式を定義できます:
5 Bits: HLIT, # of Literal/Length codes - 257 (257 - 286)
5 Bits: HDIST, # of Distance codes - 1 (1 - 32)
4 Bits: HCLEN, # of Code Length codes - 4 (4 - 19)
5ビット: HLIT、Literal/長さのコードの#--257 (257--286) 5Bits: HDIST、Distanceコードの#--1 (1--32) 4Bits: HCLEN、Code Lengthコードの#--4(4 - 19)
Deutsch Informational [Page 13] RFC 1951 DEFLATE Compressed Data Format Specification May 1996
情報[13ページ]のRFC1951が圧縮されたデータの形式仕様1996年5月に空気を抜かせるドイツ語
(HCLEN + 4) x 3 bits: code lengths for the code length
alphabet given just above, in the order: 16, 17, 18,
0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
(HCLEN+4)x3ビット: オーダーでちょうど上に与えられたコード長さのアルファベットのために長さをコード化してください: 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
These code lengths are interpreted as 3-bit integers
(0-7); as above, a code length of 0 means the
corresponding symbol (literal/length or distance code
length) is not used.
これらのコードの長さは3ビットの整数(0-7)として解釈されます。 同じくらい上では、0のコードの長さが、対応するシンボル(文字通りの/長さか距離コードの長さ)が使用されていないことを意味します。
HLIT + 257 code lengths for the literal/length alphabet,
encoded using the code length Huffman code
コード長さのハフマンコードを使用することでコード化された文字通りの/長さアルファベットのためのHLIT+257のコードの長さ
HDIST + 1 code lengths for the distance alphabet,
encoded using the code length Huffman code
コード長さのハフマンコードを使用することでコード化された距離アルファベットのための+ HDISTの1つのコードの長さ
The actual compressed data of the block,
encoded using the literal/length and distance Huffman
codes
文字通りの/長さと距離ハフマンコードを使用することでコード化されたブロックの実際の圧縮されたデータ
The literal/length symbol 256 (end of data),
encoded using the literal/length Huffman code
シンボル256(データの終わり)、文字通りの/長さのコード化された使用文字通りの/長さのハフマン符号
The code length repeat codes can cross from HLIT + 257 to the
HDIST + 1 code lengths. In other words, all code lengths form
a single sequence of HLIT + HDIST + 258 values.
コード長さの反復コードはHLIT+257〜+ HDISTの1つのコードの長さまで交差できます。 言い換えれば、すべてのコードの長さがHLIT+HDIST+258の値のただ一つの系列を形成します。
3.3. Compliance
3.3. 承諾
A compressor may limit further the ranges of values specified in
the previous section and still be compliant; for example, it may
limit the range of backward pointers to some value smaller than
32K. Similarly, a compressor may limit the size of blocks so that
a compressible block fits in memory.
コンプレッサーは、さらに前項で指定された値の範囲を制限して、まだ言いなりになっているかもしれません。 例えば、それは逆方向ポインタの範囲を32Kより小さい何らかの値に制限するかもしれません。 同様に、コンプレッサーがブロックのサイズを制限するかもしれないので、圧縮性のブロックはメモリをうまくはめ込みます。
A compliant decompressor must accept the full range of possible
values defined in the previous section, and must accept blocks of
arbitrary size.
対応する減圧装置は、前項で定義された最大限の範囲の可能な値を受け入れなければならなくて、ブロックの任意のサイズを受け入れなければなりません。
4. Compression algorithm details
4. 圧縮アルゴリズムの詳細
While it is the intent of this document to define the "deflate" compressed data format without reference to any particular compression algorithm, the format is related to the compressed formats produced by LZ77 (Lempel-Ziv 1977, see reference [2] below); since many variations of LZ77 are patented, it is strongly recommended that the implementor of a compressor follow the general algorithm presented here, which is known not to be patented per se. The material in this section is not part of the definition of the
どんな特定の圧縮アルゴリズムの参照なしでも「空気を抜いてください」という圧縮されたデータの形式を定義するのが、このドキュメントの意図である間、形式はLZ77によって作成された圧縮形式に関連します(Lempel-Ziv1977、[2] 以下での参照を見てください)。 LZ77の多くの変化が特許をとられるので、コンプレッサーの作成者がここに提示された一般的なアルゴリズムに従うことが強く勧められます。(アルゴリズムはそういうものとして特許をとられないのが知られています)。 このセクションの材料は定義の一部ではありません。
Deutsch Informational [Page 14] RFC 1951 DEFLATE Compressed Data Format Specification May 1996
情報[14ページ]のRFC1951が圧縮されたデータの形式仕様1996年5月に空気を抜かせるドイツ語
specification per se, and a compressor need not follow it in order to be compliant.
そういうものの仕様、コンプレッサーは、言いなりになるためにそれに続く必要はありません。
The compressor terminates a block when it determines that starting a new block with fresh trees would be useful, or when the block size fills up the compressor's block buffer.
新鮮な木から新しいブロックを始動するのが役に立つことを決定するか、またはブロック・サイズがコンプレッサーのブロックバッファを満たすとき、コンプレッサーはブロックを終えます。
The compressor uses a chained hash table to find duplicated strings, using a hash function that operates on 3-byte sequences. At any given point during compression, let XYZ be the next 3 input bytes to be examined (not necessarily all different, of course). First, the compressor examines the hash chain for XYZ. If the chain is empty, the compressor simply writes out X as a literal byte and advances one byte in the input. If the hash chain is not empty, indicating that the sequence XYZ (or, if we are unlucky, some other 3 bytes with the same hash function value) has occurred recently, the compressor compares all strings on the XYZ hash chain with the actual input data sequence starting at the current point, and selects the longest match.
3バイトの系列を作動させるハッシュ関数を使用して、コンプレッサーは、コピーされたストリングを見つけるのにチェーニングされたハッシュ表を使用します。 圧縮の間の任意な与えられた点では、XYZが次の3入力バイトであることをさせて、調べられてください(必ずもちろんすべて異なるというわけではない)。 まず最初に、コンプレッサーはXYZがないかどうか細切れ肉料理チェーンを調べます。 チェーンが空であるなら、コンプレッサーは、文字通りのバイトとして単にXを書き上げて、入力で1バイト進みます。 系列XYZ(私たちが不運であるなら、同じくらいがあるある他の3バイトは機能値を論じ尽くす)が最近起こったのを示して、細切れ肉料理チェーンが空でないなら、コンプレッサーは、現在のポイントで始まる実際の入力データ系列にXYZ細切れ肉料理チェーンのすべてのストリングをたとえて、最も長いマッチを選択します。
The compressor searches the hash chains starting with the most recent strings, to favor small distances and thus take advantage of the Huffman encoding. The hash chains are singly linked. There are no deletions from the hash chains; the algorithm simply discards matches that are too old. To avoid a worst-case situation, very long hash chains are arbitrarily truncated at a certain length, determined by a run-time parameter.
短い距離を支持して、その結果、ハフマン符号化を利用するために最新のストリングから始まって、コンプレッサーは細切れ肉料理チェーンを捜します。 細切れ肉料理チェーンは単独でリンクされます。 細切れ肉料理チェーンからの削除が全くありません。 アルゴリズムは単に古過ぎるマッチを捨てます。 最悪の場合状況を避けるために、非常に長い細切れ肉料理チェーンはラン・タイム・パラメータによって測定されたある長さで任意に先端を切られます。
To improve overall compression, the compressor optionally defers the
selection of matches ("lazy matching"): after a match of length N has
been found, the compressor searches for a longer match starting at
the next input byte. If it finds a longer match, it truncates the
previous match to a length of one (thus producing a single literal
byte) and then emits the longer match. Otherwise, it emits the
original match, and, as described above, advances N bytes before
continuing.
総合的な圧縮を改良するために、コンプレッサーは任意にマッチ(「怠惰なマッチング」)の品揃えを延期します: 長さNのマッチが見つけられた後に、コンプレッサーは次の入力バイトで始動するより長いマッチを捜し求めます。 より長いマッチを見つけるなら、それは、1(その結果、文字通りの1バイトを生産する)の長さに前のマッチに先端を切らせて、より長いマッチを放ちます。 さもなければ、それは、続くNバイト前に、オリジナルのマッチを放って、上で説明されるように進みます。
Run-time parameters also control this "lazy match" procedure. If compression ratio is most important, the compressor attempts a complete second search regardless of the length of the first match. In the normal case, if the current match is "long enough", the compressor reduces the search for a longer match, thus speeding up the process. If speed is most important, the compressor inserts new strings in the hash table only when no match was found, or when the match is not "too long". This degrades the compression ratio but saves time since there are both fewer insertions and fewer searches.
また、ラン・タイム・パラメータはこの「怠惰なマッチ」手順を制御します。 圧縮比が最も重要であるなら、コンプレッサーは初戦の長さにかかわらず2番目の完全な検索を試みます。 正常な場合では、現在のマッチが「十分長い」なら、コンプレッサーは、より長いマッチの検索を抑えます、その結果、過程を早くします。 マッチが全く単に見つけられなかったか、またはマッチが「長過ぎない」ときに、速度が最も重要であるなら、コンプレッサーは新しいストリングをハッシュ表に挿入します。 より少ない入と、より少ない検索の両方があるので、これは、圧縮比を下げますが、時間を節約します。
Deutsch Informational [Page 15] RFC 1951 DEFLATE Compressed Data Format Specification May 1996
情報[15ページ]のRFC1951が圧縮されたデータの形式仕様1996年5月に空気を抜かせるドイツ語
5. References
5. 参照
[1] Huffman, D. A., "A Method for the Construction of Minimum
Redundancy Codes", Proceedings of the Institute of Radio
Engineers, September 1952, Volume 40, Number 9, pp. 1098-1101.
[1] ハフマン、D.A.、「最小の冗長コードの工事のための方法」、無線技術学会、1952年9月、Volume40、Number9、ページのProceedings 1098-1101.
[2] Ziv J., Lempel A., "A Universal Algorithm for Sequential Data
Compression", IEEE Transactions on Information Theory, Vol. 23,
No. 3, pp. 337-343.
[2] Ziv J.、Lempel A.、「連続したデータ圧縮のための普遍的なアルゴリズム」、情報Theoryの上のIEEE Transactions、Vol.23、No.3、ページ 337-343.
[3] Gailly, J.-L., and Adler, M., ZLIB documentation and sources,
available in ftp://ftp.uu.net/pub/archiving/zip/doc/
[3] ゲイルとJ.-L.とアドラーとM.とZLIBドキュメンテーションと中で入手できているソース、 ftp://ftp.uu.net/pub/archiving/zip/doc/
[4] Gailly, J.-L., and Adler, M., GZIP documentation and sources,
available as gzip-*.tar in ftp://prep.ai.mit.edu/pub/gnu/
[4] ftp://prep.ai.mit.edu/pub/gnu/ のgzip*.tarとして手があいているゲイル、J.-L.、アドラー、M.、GZIPドキュメンテーション、およびソース
[5] Schwartz, E. S., and Kallick, B. "Generating a canonical prefix
encoding." Comm. ACM, 7,3 (Mar. 1964), pp. 166-169.
[5] B. シュワルツ、E.S.、およびKallick、「正準な接頭語コード化を発生させます。」 Comm。 ACM、7、3(1964年3月)、ページ 166-169.
[6] Hirschberg and Lelewer, "Efficient decoding of prefix codes,"
Comm. ACM, 33,4, April 1990, pp. 449-459.
[6] ヒルシュベルグ法とLelewer、「接頭語コードの効率的な解読」、Comm。 ACM、33、4、1990年4月、ページ 449-459.
6. Security Considerations
6. セキュリティ問題
Any data compression method involves the reduction of redundancy in the data. Consequently, any corruption of the data is likely to have severe effects and be difficult to correct. Uncompressed text, on the other hand, will probably still be readable despite the presence of some corrupted bytes.
どんなデータ圧縮方法もデータの、冗長の減少を伴います。 その結果、データのどんな不正も厳しい効果を持って、修正するのが難しい傾向があります。 崩壊した数バイトの存在にもかかわらず、他方では、解凍されたテキストはたぶんまだ読み込み可能になっているでしょう。
It is recommended that systems using this data format provide some means of validating the integrity of the compressed data. See reference [3], for example.
このデータの形式を使用するシステムが圧縮されたデータの保全を有効にするいくつかの手段を提供するのは、お勧めです。 例えば参照[3]を見てください。
7. Source code
7. ソースコード
Source code for a C language implementation of a "deflate" compliant compressor and decompressor is available within the zlib package at ftp://ftp.uu.net/pub/archiving/zip/zlib/.
「空気を抜いてください」という言いなりになっているコンプレッサーと減圧装置のC言語実現のためのソースコードは ftp://ftp.uu.net/pub/archiving/zip/zlib/ でのzlibパッケージの中に利用可能です。
8. Acknowledgements
8. 承認
Trademarks cited in this document are the property of their respective owners.
本書では引用された商標は彼らのそれぞれの所有者の資産です。
Phil Katz designed the deflate format. Jean-Loup Gailly and Mark Adler wrote the related software described in this specification. Glenn Randers-Pehrson converted this document to RFC and HTML format.
フィル・キャッツが設計した、形式に空気を抜かせてください。 ジーン-ループ川のゲイルとマーク・アドラーはこの仕様で説明された関連するソフトウェアを書きました。 グレン・ラナース-パーソンはRFCとHTML形式にこのドキュメントを変換しました。
Deutsch Informational [Page 16] RFC 1951 DEFLATE Compressed Data Format Specification May 1996
情報[16ページ]のRFC1951が圧縮されたデータの形式仕様1996年5月に空気を抜かせるドイツ語
9. Author's Address
9. 作者のアドレス
L. Peter Deutsch Aladdin Enterprises 203 Santa Margarita Ave. Menlo Park, CA 94025
L.ピータードイツ語アラジンエンタープライズ203サンタマルガリータAve。 メンローパーク、カリフォルニア 94025
Phone: (415) 322-0103 (AM only) FAX: (415) 322-1734 EMail: <ghost@aladdin.com>
以下に電話をしてください。 (415) 322-0103(AM専用)FAX: (415) 322-1734 メールしてください: <幽霊@aladdin.com>。
Questions about the technical content of this specification can be sent by email to:
以下のことのためにメールでこの仕様の技術的な内容に関する質問を送ることができます。
Jean-Loup Gailly <gzip@prep.ai.mit.edu> and Mark Adler <madler@alumni.caltech.edu>
ジーン-ループ川 Gailly <gzip@prep.ai.mit.edu 、gt;、 Adler <madler@alumni.caltech.edu をマークしてください、gt。
Editorial comments on this specification can be sent by email to:
以下のことのためにメールでこの仕様の編集のコメントを送ることができます。
L. Peter Deutsch <ghost@aladdin.com> and Glenn Randers-Pehrson <randeg@alumni.rpi.edu>
L.ピーター Deutsch <ghost@aladdin.com 、gt;、グレン Randers-Pehrson <randeg@alumni.rpi.edu 、gt。
Deutsch Informational [Page 17]
ドイツ語Informationalです。[17ページ]
一覧
スポンサーリンク
