 |
 |
Perlで作るCGI講座 |  |
 |
|
英語技術文書日本語訳 |  |
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
||||||||||
|
||||||||||||||
|
本ドキュメントは、RFC 1951 『DEFLATE Compressed Data Format Specification version 1.3』 を futomi が日本語化したものです。みなさまの理解に役立てれば幸いです。なお、緑色で記載された文章は、futomi が注釈として加筆したものです。また、一部、直訳ではなく、意訳した部分がございます。原文と表現が異なることがございますので、ご了承ください。
注意: この日本語訳は、futomi が理解を深めるために、自分なりに日本語化したものです。本日本語訳には、翻訳上の誤りがある可能性があります。したがって、内容について一切保証をするものではありません。正確さを求める場合には、必ず原文を参照してください。当方は、この文書によって利用者が被るいかなる損害の責任を負いません。
もし誤りなどを見つけたら、こちらからご連絡いただければ幸いです。
| Network Working Group | P. Deutsch |
| Request for Comments: 1951 | Aladdin Enterprises |
| Category: Informational | May 1996 |
このメモは、インターネットコミュニティーのために情報を提供するものです。このメモは、いかなる種類のインターネット標準を定めるものではありません。このメモの配布は無制限です。
IESG は、本文書に含まれるいかなる知的所有権声明の正当性に関して、特定の立場をとりません。
Copyright (c) 1996 L. Peter Deutsch
いかなる目的に対しても、多言語への翻訳、編集物への組み込みを含めて、本文書のコピーおよび配布を無償で許諾します。ただし、著作権表示およびこの注意事項を遵守して下さい。また、元文書から実質的な変更や削除があれば、その部分を明確に表示下さい。※本日本語訳においては、緑色で記した箇所が futomi による加筆部分です。実質的な変更や削除は、本日本語訳においてはございません。
本文書の最新版と、HTML フォーマットの関連文書の情報は、こちらに掲載されております。
<ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html>.
この仕様は、LZ77 アルゴリズムとハフマン符号化を組み合わせた圧縮データの可逆圧縮データフォーマットを定義するもので、その能力は、現時点でもっとも良いとされる汎用的な圧縮方式に匹敵します。次々に現れるどんな長さの入力データストリームでさえも、事前に制限した中間記憶装置の容量を使うだけで、データを生成または利用することができます。このフォーマットは、特許に抵触しない形で、ためらうことなく実装することができます。
この仕様は、以下に示す可逆圧縮データフォーマットを定義することを目的としています。
この仕様書で定義されているデータフォーマットは、以下に示す事項に関して試みません。
ひとつ言っておかなければいけませんが、可逆圧縮アルゴリズムは、どんな可能性のある入力データセットでも圧縮できるとは限らないということに注意して下さい。ここで定義されるフォーマットでは、最悪のケースで、32K バイトブロックごとに 5 バイト膨らんでしまいます。つまり、圧縮前のデータセットに対して、0.015% サイズが増加してしまうということです。英語のテキストは、通常、2.5 〜 3 分の 1 に圧縮されます。実行ファイルは通常いくぶんかは少なめです。ラスタ画像のような画像データは、さらに圧縮されるかもしれません。
この仕様は、データを "deflate" フォーマットに圧縮する、もしくは "deflate" フォーマットから解凍するソフトウェアの開発者による利用を対象としています。
この仕様の文章は、ビットレベルや他の原始的なデータ表現でのプログラミングにおける基本的な知識を前提としています。ハフマン符号化の技術知識は助けにはなりますが、必須ではありません。
この仕様書は、連続したバイトを、（通常は短い）連続したビットとして表現するための方式を定義します。
以降で特に指定がない限り、準拠した解凍器は、ここで提示されるすべての仕様に準拠したどんなデータセットでも受け入れ、そして解凍できなければいけません。；準拠した圧縮器は、ここで提示されるすべての仕様に準拠したデータセットを生成しなければいけません。
バイト： 一つのユニットとして、蓄積もしくは転送された 8 ビット です。（オクテットと同義）。（たとえ 8 ビットで一つの文字を蓄積しないマシンにおいても、この仕様では、バイトは正確に 8 ビットを意味します。） バイトの中でのビットの番号付けは、下記をご覧下さい。
ストリング： 任意の連続したバイト
この仕様のバージョン 1.1 から、deflate フォーマットの技術的な変更はありません。バージョン 1.2 では、いくつかの専門用語が変更されました。バージョン 1.3 では、この仕様が RFC 形式に変換されました。
圧縮データセットは、連続したブロックで構成されますが、入力データのブロックの順に対応しています。ブロックサイズは任意ですが、非圧縮ブロックは 65,535 バイト以内でないといけません。
各ブロックは、LZ77 アルゴリズムとハフマン符号化の組み合わせで圧縮されます。各ブロックに対応したハフマン木は、前後のブロックのハフマン木から独立しています。LZ77 アルゴリズムは、32K の入力バイトまで遡って、前のブロックで発生した複製されたストリングへの参照を使うかもしれません。
各ブロックは 2 つの部分から構成されます。一つは、圧縮されたデータ部分の表現を記述するハフマン符号木で、もう一つは圧縮データ部分です。（ハフマン木は、それ自身、ハフマン符号化を使って圧縮されます。） 圧縮データは、2 種類の連続要素から構成されます。（前の 32K 入力バイトの中に複製されたと検出されなかったストリングの）文字バイトと、複製されたストリングへのポインターです。そのポインターは、一対の <長さ、戻る距離> として表現されるものです。"deflate" フォーマットで使われるその表現は、距離を 32K バイトまでに、長さを 258 バイトまでに制限されています。しかし、圧縮できないブロックを除いては、前述の制限はありますが、ブロックのサイズに制限はありません。
圧縮データ内の各タイプの値（文字列、距離、長さ）は、ハフマン符号を使って表現されます。文字列と長さに対する一つの符号木と、距離に対する別の符号木を使います。各ブロックの符号木は、そのブロックの圧縮データの直前に、コンパクトな形式で現れます。
下図をご覧下さい。次のような箱は 1 バイトを表します。
+---+ | | <-- 垂直棒は表示されない場合があります。 +---+
次の様な箱は、可変長バイトを表します。
+==============+ | | +==============+
コンピュータに蓄積されているバイトは、ビットの順番に意味はありません。なぜなら、それらは常に一つの単位として扱われるからです。しかし、0 〜 255 までの整数としてみなされるバイトは、最上位ビット（MSB）もしくは最下位ビット（LSB）を持っています。私達は左から最上位桁の数字を書きますから、左に最上位ビットを持つバイトを書き込みます。下図をご覧下さい。ビット 0 が最下位ビットとなるように、バイトのビットを番号付けしています。
+--------+ |76543210| +--------+
コンピュータ内部では、数字はマルチバイトで構成される場合があります。ここで説明するフォーマット内のすべてのマルチバイト数字は、最下位バイトから順に蓄積されます（低いメモリアドレスに）※。例えば、十進数 520 は、次のように蓄積されます。
0 1 +--------+--------+ |00001000|00000010| +--------+--------+ ^ ^ | | | + 上位バイト = 2 x 256 + 下位バイト = 8
※ RFC 1950 の蓄積順番とは逆なので、注意が必要です。
この文書は、バイト内のビットがどのような順番で転送されるかに関しては、取り扱いません。なぜなら、ここで説明されている最終的なデータフォーマットは、ビット指向というよりはバイト指向だからです。しかし、後述の圧縮データフォーマットに関しては、連続バイトとしてではなく、さまざまなビット長のデータ要素の列として説明します。従って、最終的な圧縮バイト列を形成するために、これらのデータをどのようにバイト内にパックするのかを、次の通りに規定します。
言い換えると、圧縮データを出力する際には、各バイトの通常左側にある最上位ビットを使って、最初のバイトの"右"端のからスタートし、"左"へ進めます。このようなバイト列として圧縮データを出力すれば、右から左へ結果を解析することができます。ただし、固定長要素は正確に最上位ビットから最下位ビットの順番になり、ハフマン符号は逆のビット順（つまり、最下位ビットの位置に符号の最初のビットがきている）になるのです。
プレフィックス符号化は、ビット列（符号）ごとに、事前に決めておいたアルファベットを使って記号を表現します。各記号ごとに一つの符号が割り当てられます。異なる記号は、異なる長さのビット列によって表現されるかもしれません。それでも、解析器はいつでも、符号化されたストリングを、明確に記号ごと分けて解析することができます。
我々は、二進木を使ってプレフィックス符号を定義します。二進木の中で、下端ではない分岐点から下がる 2 本の線それぞれに、0 と 1 をラベル付けします。そして、二進木の下端にアルファベットの記号を一対一で対応付けます。そして、二進木の頂上から下端までたどった線上の 0 と 1の列が、下端に対応付けられた記号の符号になるのです。次の例をご覧下さい。
/\
0 1
/ \
/\ B
0 1
/ \
A /\
0 1
/ \
D C
記号 符号 ------ ---- A 00 B 1 C 011 D 010
解析器は、二進木の頂上から、次にくる入力ビットに対応した線を選択しながら下端までたどります。そうすることで、符号化された入力ストリームから次の記号を復号することができるのです。
記号の出現率が分かっていれば、ハフマンアルゴリズムは、最適なプレフィックス符号を構成することができます。（ストリングを、そのアルファベットに対応付けられたプレフィクス符号の中から最もビット数が少ないものを使った記号出現率で、表現します。） そのような符号をハフマン符号と呼びます。（第 5 章 リファレンス [1] をご覧下さい。ハフマン符号に関する追加情報のリファレンスです。）
"deflate" フォーマットにおいて、各種アルファベットに対応するハフマンコードは、一定の最大符号長を超えてはいけないということに注意して下さい。この制限があるために、記号の出現率から符号長を計算するためのアルゴリズムは複雑になります。再度、第 5 章のリファレンスで詳細を確認して下さい。
"deflate" フォーマットで各アルファベットに対して使われたハフマン符号には、次の 2 つのルールが追加で適用されます。
| ※1 | ここで言っている "辞書的に連続した値になる" という意味は、例えば、同じ長さ 3 の符号がいくつかあったとしましょう。一番小さい符号が "010" だとすると、それ以降の符号は連続するということですので、"011", "100" … となります。間を飛ばしていきなり、"111" になることはないのです。 |
| ※2 | ここで言っている "辞書的に前に来る" という意味は、例えば、符号の長さが 2 と 3 の 2つの符号があったとしましょう。長さが 3 の符号が "010" だったとすると、長さが 2 の符号は "01"（010 の上 2 桁） より前の値になるということです。ということは、"00" になるということです。ビットを数字の大きさで並べるのではなく、英和辞典で単語がアルファべト順に並んでいるように、単純に文字として並べるのです。 |
これらのルールに沿って、前述の例を表すと下表のとおりになります。ただし、アルファベットの順番が ABCD だと仮定します。
記号 符号 ------ ---- A 10 B 0 C 110 D 111
つまり、0 は 10 より前に来て、10 は 11x より前に来ています。そして、110 や 111 は、辞書的に連続しています。※
| ※ | このフレーズは、"0 は 10 より前に来て" と言っていますが、これは上表の順番を差しているのではありません。ただ単に、上表で割り振った符号が前述の 2 つのルールにそった形になっていると言いたいだけだと思われます。 |
このルールが与えられると、我々は、アルファベットの各記号に対する符号ビット長を順番に与えさえすれば、アルファベットに対するハフマン符号を定義することができます。これは、実際の符号を決定するのに十分です。我々の例では、その符号は、ビット長 (2, 1, 3, 3) の列によって、完全に定義されます。次に示すアルゴリズムは、整数として符号を生成します。その整数は、最上位ビットから最下位ビットに向けて読み込むように考えられています。符号長は事前に tree[I].Len で与えられ、符号は tree[I].Code に生成されます。
| 1) | 各符号長に対する符号の数を数えます。bl_count[N] に、1 以上の長さ N の符号の数字を代入します。 |
| 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; } |
| 3) | step 2 で決定した基本値を使って、同じ長さのすべての符号に対する連続した値を使って、すべての符号に数値を割り付けます。全く使われなかった（ビット長が 0 であった）符号は、値を割り付けられてはいけません。
for (n = 0; n <= max_code; n++) {
len = tree[n].Len; if (len != 0) { tree[n].Code = next_code[len]; next_code[len]++; } } |
例：
ビット長 (3, 3, 3, 3, 3, 2, 4, 4) であるアルファベット ABCDEFGH を取り上げます。step 1 を経ると下表の結果が得られます。
N bl_count[N] - ----------- 2 1 3 5 4 2
Step2 で next_code の値を計算し、下表の結果が得られます。
N next_code[N] - ------------ 1 0 2 0 3 2 4 14
Step 3 で符号値を生成し、下表の結果が得られます。
記号 長さ 符号 ------ ------ ---- A 3 010 B 3 011 C 3 100 D 3 101 E 3 110 F 2 00 G 4 1110 H 4 1111
圧縮データの各ブロックは、次のデータを含む 3 ビットのヘッダーから始まります。
第1ビット BFINAL 次の2ビット BTYPE
ヘッダービットは、必ずしもバイトの境界で始まるわけではないことに注意して下さい。一つのブロックは、必ずしも整数分のバイトで占められるわけではないのです。
BFINAL は、これがデータセットの最後のブロックである時かつその時に限り、セットされます。
BTYPE は、次の通り、データがどのように圧縮されたかを特定します。
00 - 非圧縮 01 - 固定長ハフマン符号で圧縮 10 - 可変長ハフマン符号で圧縮 11 - 予約 (エラー)
2 つの圧縮方式（01 の固定長ハフマン符号と 10 の可変長ハフマン符号）は、リテラル / 長さ と距離に対するハフマン符号がどのように定義されたかという点が違うだけです。
どの場合においても、実際のデータを復号するアルゴリズムは次のようになります。
do 入力ストリームからブロックヘッダを読み込む if 非圧縮 現時点で進んだバイト内の残りのビットをスキップ LEN と NLEN を読み込む (次章を参照のこと) データの LEN のバイトを出力にコピーする otherwise if 可変長ハフマン符号で圧縮 符号木の表現を読み込む (後述の項を参照) loop (until 認識できるブロック符号の最後) 入力ストリームからリテラル/長さ値を復号する if 値 < 256 出力ストリームへ値（リテラルバイト）をコピーする otherwise if 値 = ブロック終端 (256) break from loop otherwise (値 = 257..285) 入力ストリームからの距離を復号する 出力ストリームで距離バイト分だけ戻り、この場所から出力ストリームまでの長さバイトをコピーする end loop while not last block
複製されたストリングの参照は、前のブロックのストリングへ参照するかも知れません。つまり、戻る距離は、一つ以上のブロック境界をまたぐかもしれません。しかし、距離は、出力ストリームの開始点を超えて参照することはできません。（プリセット辞書を使うアプリケーションは、出力ストリームの一部を捨てるかも知れません。） また、参照されたストリングは、現在の位置と重なるかもしれないことに注意して下さい。例えば、もし復号された最後の 2 バイトが、X と Y という値だったとすると、<長さ = 5, 距離 = 2> のストリング参照によって、出力ストリームに X,Y,X,Y,X が追加されることになります。
我々は今、順を追って各圧縮方式を規定します。
次にくるバイトの境界までのどんな入力ビットも無視されます。ブロックの残りは、次に示す情報から構成されます。
0 1 2 3 4... +---+---+---+---+================================+ | LEN | NLEN |... LEN bytes of literal data...| +---+---+---+---+================================+
LEN は、ブロック内のデータバイトの数です。NLEN は、LEN の補数です。
前述の通り、"deflate" フォーマットで符号化されたデータブロックは、3 つの理論的に区別可能なアルファベットから導き出された記号列から成り立ちます。3 つの理論的に区別可能なアルファベットとは、(0..255) の値を持つリテラルバイト、または<長さ、戻り距離> ペアです。長さは(3..258) から導き出されます。そして距離は (1..32,768) から導き出されます。実際には、下記の通り、リテラルと長さのアルファベットは、単一のアルファベット (0..285) に結合されます。0 〜 255 の値は、リテラルバイトを表し、256 の値は、ブロックの終端を指し示します。そして、257, 285 の値は、長さ符号を表します。（恐らく、記号符号に引き続き拡張ビットに連結して）
符号 拡張
ビット数長さ 符号 拡張
ビット数長さ 符号 拡張
ビット数長さ ---- ---- ------ ---- ---- ------ ---- ---- ------ 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
拡張ビットは、最上位ビットが最初に蓄積されたマシン整数として解釈されるべきです。つまりビット列 1110 は、14 の値を表します。
符号 拡張
ビット数距離 符号 拡張
ビット数距離 符号 拡張
ビット数距離 ---- ---- ------ ---- ---- ------ ---- ---- -------- 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
2 つのアルファベットに対するハフマン符号は、固定されます。そして、データ内で明示的に表現されません。リテラル/長さ アルファベットに対するハフマン符号長は、下表の通りです。
リテラル値 ビット数 符号 --------- ---- ----- 0 - 143 8 00110000 〜
10111111144 - 255 9 110010000 〜
111111111256 - 279 7 0000000 〜
0010111280 - 287 8 11000000 〜
11000111
符号長は、前述の通り、実際の符号を生成するのに十分です。我々は、明確性を加えるために、表に符号を示します。リテラル/長さの値 286-287 は、実際には、決して圧縮データ内に発生することはありませんが、符号生成には参加します。
距離符号 0-31 は、前述の 3.2.5 項で示された表に示されている通り、可能性のある付加ビットとともに、（固定長） 5 ビット符号で表現されます。距離コード 30-31 は、実際には、圧縮データ内には決して発生することがないことに注意して下さい。
2 つのアルファベットに対するハフマン符号は、ヘッダビットの直後そして実際の圧縮データの直前に現れます。第 1 番目は、リテラル/長さ符号です。それから距離符号です。それぞれの符号は、上記の 3.2.2 項での説明の通り、符号長の列によって定義されます。たとえより高い圧縮率だとしても、符号長の列それ自身は、ハフマン符号で圧縮されます。符号長に対するアルファベットは、次の通りです。
0 - 15 : 0 - 15 の符号長を表します。 16 : 直前の符号長値を 3 - 6 回コピーします。
次に現れる 2 ビットは、反復長を表します。
(0 = 3, ... , 3 = 6)
例： 符号 8, 16 (+2 ビット 11), 16 (+2 ビット 10) は、
符号長値 8 が 12 個 (1 + 6 + 5) に拡張されます。17 : 0 の符号長を 3 - 10 回繰返します。
(3 ビット長)18 : 0 の符号長を 11 - 138 回繰返します。
(7 ビット長)
符号長が 0 ということは、リテラル/長さや距離アルファベットの関連シンボルは、ブロック内では発生せず、以前に与えられたハフマン符号生成アルゴリズムに参加すべきではないでしょう。もし一つでも距離符号が使われたなら、それは、0 ビットではなく、1 ビットで符号化されます。この場合、一つの未使用符号を使って、単一の符号長があります。ゼロビットの一つの距離符号は、距離コードが全く存在しないことを意味します。（データは、すべてリテラルである）
我々は、今、ブロックのフォーマットを定義することができます。
5 Bits: HLIT, リテラル/長さ符号の個数 - 257 (257 - 286) 5 Bits: HDIST, 距離符号の個数 - 1 (1 - 32) 4 Bits: HCLEN, 長さ符号の個数 - 4 (4 - 19) (HCLEN + 4) x 3 ビット 前述の符号長アルファベットに対する符号長リストで、次の順番で並びます。:
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
これらの符号長は、3 ビット整数 (0-7) として解釈されます。前述の通り、0 という符号長は、対応している記号（リテラル/長さ、または、距離の符号長）が使われていないことを意味します。HLIT + 257 個のリテラル/長さのアルファベットに対する符号長リスト HLIT + 257 個のリテラル/長さのアルファベットに対する符号長は、符号長のハフマン符号を使って符号化されます。 HDIST + 1 個の距離アルファベットに対する符号長リスト HDIST + 1 個の距離アルファベットに対する符号長は、符号長のハフマン符号を使って符号化されます。 圧縮データ ブロックの実際の圧縮データは、リテラル/長さ、および、距離のハフマン符号を使って符号化されます。 リテラル/長さ記号 256 （データの終端） リテラル/長さ記号 256 （データの終端）は、リテラル/長さのハフマン符号を使って符号化されます。
符号長繰返し符号は、HLIT + 257 から HDIST + 1 までの符号長まで重なることができます。つまり、単一の HLIT + HDIST + 258 の値の列からのすべての符号長です。
圧縮器は、前章で定義された値の範囲を超えるかもしれませんが、それでも尚準拠しているでしょう。例えば、それは、32K より小さいいくつかの値への戻りポインタの範囲を超えるかもしれません。同様に、圧縮機は、圧縮ブロックがメモリーにフィットするように、ブロックサイズを制限するかもしれません。
準拠した解凍器は、前章で定義された可能な値の全範囲を受け入れなければいけません。そして、任意のブロック長を受け入れなければいけません。
どんな特定の圧縮アルゴリズムをも参照せずに、"deflate" 圧縮データフォーマットを定義することが、この文書の目的です。しかし、このフォーマットは、LZ77 （Lempel-Ziv 1977, 下記リファレンス [2] をご覧下さい。）によって生成された圧縮フォーマットに関係しています。多くのLZ77 の派生は特許で保護されているので、圧縮器の実装者はここで説明されている一般的なアルゴリズムに従うことを強く推奨します。それは、それ自体、特許で保護されていないことが分かっています。この章の資料は、これ自体、仕様の定義を成すものではありません。そして、圧縮器は、準拠のために、これに従う必要はありません。
圧縮器は、全く新しい木を使って新しいブロックから開始したほうが良いと決定したときや、ブロックサイズが圧縮器のブロックバッファを一杯にしたときに、ブロックを終端します。
圧縮器は、複製されたストリングを見つけるために、chained ハッシュテーブルを使います。3 バイト列上で実行するハッシュ関数を利用します。圧縮中に得られたどんなポイントにおいてでも、XYZ を、調べるべき次の 3 つの入力バイトにして下さい（もちろん、すべて異なる必要はありません。）。最初に、圧縮器は、XYZ に対してハッシュ chain を調べます。もし、ハッシュ chain が空でなければ、XYZ 列（運が悪いと、同じハッシュ関数値をもったいくつかの他の 3 バイト）がすぐに発生することを示唆しながら、圧縮器は、現在のポイントで始まる実際の入力データ列を使って、XYZ ハッシュ chain 上で、すべてのストリングを比較するのです。そして、最も長い一致を選択するのです。
圧縮器は、短い距離を好みます。そしてそれゆえに、ハフマン符号化をうまく利用するために、最も直近のストリングから開始しているハッシュ chain を検索します。ハッシュ chain は、一つずつ、リンクされます。ハッシュ chain からの削除は一切ありません。このアルゴリズムは、ただ単に、古過ぎる一致を捨てるだけのことです。最悪の場合を避けるために、非常に長いハッシュ chain は、ある一定の長さに、任意に切り詰められ、ランタイムパラメータによって判断されます。
全体の圧縮を改善するために、圧縮器は、状況に応じて、一致 ("lazy matching") の抽出を延期します。長さ N の一致が見つかった後に、圧縮器は、次の入力バイトから始まるもっと長い一致を検索します。もし、もっと長い一致が見つかったなら、先の一致を見つかった一致の長さに切り詰め（だから、単一のリテラルバイトを生成して）、そして、それからさらに長い一致を発行します。そうでなければ、もともとの一致を発行します。そして、前述の通り、継続する前に N バイトを進めます。
ランタイムパラメータは、また、この "lazy match" 生成を制御します。もし、圧縮率がもっとも重要なのであれば、圧縮器は、最初の一致の長さに関係なく、第二の検索を完了しようとします。最も普通の場合においては、もし、現在の一致が "十分に長い" なら、圧縮器は、さらに長い一致の検索を減らします。それゆえに、プロセスのスピードアップが図られるのです。もしスピードがもっとも重要なのであれば、圧縮器は、一致が見つからなかったとき、もしくは、一致が "長すぎる" ときにだけ、ハッシュテーブル内に新しいストリングを挿入します。これは、圧縮率の低下を招きますが、時間は節約できます。なぜなら、挿入が少なくなり、検索も少なくなるからです。
| [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. |
| [2] | Ziv J., Lempel A., "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory, Vol. 23, No. 3, pp. 337-343. |
| [3] | Gailly, J.-L., and Adler, M., ZLIB documentation and sources, ftp://ftp.uu.net/pub/archiving/zip/doc/ から入手できます。 |
| [4] | Gailly, J.-L., and Adler, M., GZIP documentation and sources, ftp://prep.ai.mit.edu/pub/gnu/ から gzip-*.tar として入手できます。 |
| [5] | Schwartz, E. S., and Kallick, B. "Generating a canonical prefix encoding." Comm. ACM, 7,3 (Mar. 1964), pp. 166-169. |
| [6] | Hirschberg and Lelewer, "Efficient decoding of prefix codes," Comm. ACM, 33,4, April 1990, pp. 449-459. |
どんなデータ圧縮方式でも、データ内の冗長性に関係しています。従って、どんなデータの改竄でも、深刻な結果をもたらし、補正するのが難しいようです。一方、非圧縮のテキストは、改竄されたバイトがいくつか存在していたとしても、それでもなお、恐らく、読むことができるだろう。
このデータフォーマットを使うシステムは、圧縮データの完全性を確認する手段をいくつか提供することを、推奨します。リファレンス [3] の例をご覧下さい。
"deflate" 準拠の圧縮器と解凍器の C 言語で書かれたソースコードは、ftp://ftp.uu.net/pub/archiving/zip/zlib/ から zlib パッケージ内で、入手できます。
この文書で引用されている商標は、各所有者の財産です。
Phil Katz は、deflate フォーマットを設計しました。Jean-Loup Gailly と Mark Adler は、この仕様で説明されている関連ソフトウェアを書きました。Glenn Randers-Pehrson は、この文書を RFC と HTML の書式に変換しました。
L. Peter Deutsch
Aladdin Enterprises
203 Santa Margarita Ave.
Menlo Park, CA 94025
Phone: (415) 322-0103 (AM only)
FAX: (415) 322-1734
EMail: <ghost@aladdin.com>
この仕様の技術的な内容に関する質問は、こちらのアドレス宛にメールを送って下さい。
Jean-Loup Gailly <gzip@prep.ai.mit.edu> and
Mark Adler <madler@alumni.caltech.edu>
この仕様に関する編集上のご意見は、こちらのアドレス宛にメールを送って下さい。
L. Peter Deutsch <ghost@aladdin.com> and
Glenn Randers-Pehrson <randeg@alumni.rpi.edu>
 |
||||||||||||||
 |
|
 |
||||||||||||
