[148] DELFATE は、圧縮形式の1つです。非常によく用いられています。
[152] deflate は RFC 1951 により定義されています。
[124] RFC 1591 は、 圧縮された DEFLATE データのことを圧縮データ集合と呼んでおり、 圧縮の前の元のデータのことを入力データ >>25 と呼んでいます。
[12] DEFLATE の処理において入力データはブロックの連なり >>25 と解釈されます。また圧縮データ集合は、 ブロックの系列です >>25。 入力データのブロックを処理したものが、 それぞれ順に圧縮データ集合のブロックとなります。
[8] 圧縮器は、 仕様にすべて従うデータ集合を生成しなければなりません >>7。
[6] 展開器は、 特に定める場合を除き、 仕様に適合する任意のデータ集合を受理し展開できなければなりません。 >>7
[27] DEFLATE の出力はバイト列です。 バイト内のビット順は規定されておらず >>26、 プラットフォームやプロトコルに依存します。
[29] 多バイトの値は、重みの小さなバイトから順に並べたバイト列 >>26 (小エンディアン) とします。
[28] データ要素をバイト列にする際には、 バイトの重みの小さなビット (LSB) から順に詰めていきます。 >>26
[62] 入力データのブロックの大きさは任意に決められますが、 65535 バイト以下でなければなりません。>>25 圧縮器は、ブロックの最大長を制限できます。 しかし展開器は、任意の長さを扱えなければなりません。 >>26
[63] 圧縮データ集合のブロックは、 入力データの各ブロックに対応します。 >>25
[66] なおブロック境界とバイト境界は一致しないかもしれません。 >>26
[64] 圧縮データ集合の各ブロックは、3ビットのヘッダーから始まります。 >>26
[65] 第1ビット BFINAL は、 それが圧縮データ集合の最後のブロックかどうかを表します。 ビットが設定されていれば、最後です。 >>26
[132] 最終ブロック後に更にビット列が続く時、それをどう処理するべきかは、不明です。
[67] 第2ビットと第3ビットの BTYPE は、圧縮方法を表します。 >>26
[142] 展開器に与えられたデータが3ビットに満たない時、どう解釈するべきかは不明ですが、 壊れた入力と扱うのが自然でしょう。
[133] BTYPE が 002 の時、 無圧縮を表します。 >>26
[134] ヘッダーを含むバイトの残りのビットは、あっても無視します。 >>26
[135] その次の2バイトは、 LEN と呼び、このブロックのデータのバイト数を表します。
>>26
[136] その次の2バイトは、NLEN と呼び、 LEN の1の補数とします。
>>26
[137] その次の LEN バイト分が、このブロックのリテラルデータとします。 >>26
[138] LEN と NLEN が整合しない時、どう処理するべきかは、不明です。
[145] 展開器に与えられたデータが指定された長さに満たない時、どう処理するべきかは不明です。
[139] BTYPE が 012 のとき、固定ハフマン符号圧縮 (>>106) を表します。 >>26
[140] BTYPE が 102 のとき、 動的ハフマン符号圧縮 (>>113) を表します。 >>26
[20] ブロックの圧縮されたデータ部分は、 要素の系列です。各要素は、 リテラルバイト群か、 重複列への指示子かのいずれかです。 >>25
[21] 重複列への指示子は、 長さと前方向の距離との組です。 >>25
[17] 距離は、 32KB 以下です。すなわち、指示子は、入力データの 32KB 前までのブロックの列を参照できます。 >>25 圧縮器は、より小さな距離を上限としても構いません。 しかし展開器は、 32KB まで処理できなければなりません。 >>26
[146] 指示子は、入力データのブロックの境界をまたがることができます >>25。しかし入力データの先頭より前を指すことはできません >>25。 入力データの先頭より前の指示子が与えられた時、どう処理するべきかは不明です。
[157] 距離の上限は、 圧縮器や展開器が探索のために保持しておかなければならないバッファーやリスト (>>129) のサイズに影響します。 DEFLATE を用いるプロトコルは、 これを制限したり、制限を記述できたりする場合があります。
[23] リテラルと長さは、そのブロックのリテラル・長さ符号により符号化します。 距離は、そのブロックの距離符号により符号化します。
[32] 接頭辞符号化は、 事前に与えられた字母の記号を、 ビット列 (符号) として表現するものです。ここで、ビット列は記号ごとに長さが異なりますが、 構文解析器が常に曖昧無く記号を認識できるようにします。 >>26
[33] 接頭辞符号は、二分木を使って定義します。 枝が 0 または 1 のいずれかを表すこととします。 枝がいずれかの記号を表すこととします。 根から葉までの枝の値を順番に並べたものが、符号を表します。 >>26
[35] 構文解析器は、二分木の根から順に入力のビットに従い進むことで、 記号を得ることができます。 >>26
[36] ハフマン算法により、字母とその頻度から最適な接頭辞符号を得られます。 頻度が高いほど身近な符号となります。これをハフマン符号といいます。 >>26
[38] DEFLATE では次の2つの制限があります >>26。
[42] この制限を設けることで、記号に対応するビット長 (符号長) のリストを示すだけで、 符号を記述できます >>26。
[41] 先程の例 (>>34) では、符号は 0 < 10 < 110 = 111
と符号の長さの順が符号の順序と一致しています (>>40)。
また C < D と記号の順序と同じ長さの符号の順序が一致しています。
[43] 記号群 (A, B, C, D) を表すこの符号群は、 各符号のビット長から (2, 1, 3, 3) と表すことができます。 (このビット長の組によって表される符号は一意に定まります。)
[44] N 個の記号について、符号長のリスト長さ群から、 対応する符号を n ビットの整数のリストとして得るには、 次のようにします。 >>26
[102] 符号化されたブロックでは、2種類のハフマン符号を使います。
[118] DEFLATE のハフマン符号は、 実際の各符号の直後に、 いくつかの余剰ビット群が続く場合があります。
[101] 余剰ビット群は、 MSB から順に並べたものと解釈します。 >>26
[117] 1つ目のハフマン符号は、 リテラルバイト (実際に表したいデータのバイト) や長さを表すもので、 リテラル・長さ符号 >>26 (字母は リテラル・長さ字母 >>26) のような呼ばれ方をしています。
[103] リテラル・長さ符号では、 次のように記号の意味を設定します。 >>26
[100] 長さの指定の場合には、続く余剰ビット群によって実際の長さを求めます。 >>26
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[104] 距離の符号でも、同様に余剰ビット群によって実際の距離の値を求めます。 >>26
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[106] BTYPE 012 のブロックの圧縮されたデータ部分は、 固定ハフマン符号を用いて符号化したデータです。
[120] 固定ハフマン符号ブロックのリテラル・長さ符号は、 次のような符号長の持つハフマン符号とします。 >>26
[108] 固定ハフマン符号の距離符号 [ 0, 31 ] は、 そのまま5ビット固定長 (+ 余剰ビット群) で表します。 >>26
[24] 圧縮されたデータ部分の末端は、 256 により表されます。 これが現れないで与えられたデータが終了した時展開器がどう処理するべきかは不明です。
[113] BTYPE 102 のブロックの圧縮されたデータ部分は、 動的ハフマン符号のハフマン木と、 それを用いて符号化したデータです。
[122] 動的ハフマン符号のブロックは、次のもので構成されます >>26。
[123] 使用するハフマン符号のハフマン木は、 その符号長のリストとして記述します。 符号長は、次の字母を持つハフマン符号 (符号長符号) によって記述します >>26。
[114] ここで、符号長 0 は、 該当する記号が字母に現れないため、 ハフマン符号構築アルゴリズムで省くべきことを示します。 >>26
[115] 距離符号が1つだけしか使われない場合には、 1ビットのみを使って符号化し、 0ビットは使いません。 この場合、符号長が1つと未使用の符号が1つとなります。 0ビットの符号1つの場合は、距離符号を使わない (すべてのデータがリテラルである) ことを表します。 >>26
[149] 入出力データの先頭に「preset dictionary」を置くことが DEFLATE では想定されており >>26、 zlib では応用次第で利用できることになっています。 preset dictionary は、出現頻度の高いデータを予め送受信者間で共有することで、 指示子によって参照できるようにするものです。
[150] 圧縮器は、 preset dictionary のバイト列を入力データの初期状態として処理を開始し、 本来の無圧縮データをその続きの入力データとして用います。
[151] 展開器は、 preset dictionary のバイト列を復号済みの入力データの初期状態として処理を開始し、 復号済み入力データのその続きの部分に本来の無圧縮データを得ます。
[158] WebSocket permessage-deflate では、
連続したメッセージの送信で前のメッセージの
LZ77移動窓を再利用することができ、
これを use context takeover と呼んでいます。
[159] 直前のメッセージを preset dictionary として用いるようなものとも言えます。
[127] RFC 1951 は DEFLATE データ形式を定義していますが、 圧縮アルゴリズム自体は定めないこととしています。 しかし DEFLATE 形式は LZ77 により圧縮することを想定したものであり、 強く推奨される、 特許問題が無いと考えられる算法が示されています。 もちろん、それ以外の方法により生成することも認められています。 >>116
[128] 圧縮器は、 新しいハフマン木が有用と考えられる時や、 ブロックサイズが圧縮木のブロックバッファーの末尾に達した時、 ブロックを終えます。 >>116
[129] 圧縮器は、 重複する文字列を探すため、 3バイトの列に対するハッシュ関数を使った連鎖ハッシュ表を使います。 入力の次の3バイトがハッシュ表にあれば、 該当するハッシュ鎖のすべての文字列のうち最長一致のものを選択します。 ハッシュ表にない場合は、リテラルバイトとしてそのまま出力します。 >>116
[130] ハッシュ鎖の探索では、距離を小さくするため、直近の文字列から探していきます。 ハッシュ鎖はどんどん連結していき、削除はしませんが、 古すぎるものは一致しても採用しません。 >>116
[131] 圧縮器は、 一致したものの選択を遅延させても構いません (lazy matching)。 ある位置で一致しても、更に先でより長い一致があるなら、そちらを使うことにできます。 >>116
[68] 入力ストリームの復号は、次のようにします。 >>26 ただし、入力ストリームから読むとは、現在位置から指定された長さのビット列を返し、 現在位置をその次のビットまで進めることをいいます。
[153] zlib と gzip は、 DEFLATE に簡単にラップしたデータ形式です。 zlib はメモリー上や通信での利用を想定した短いヘッダーと高速な整合性検査を採用しており、 gzip はファイルとしての利用を想定したメタデータを格納できるようになっています >>155。
[9] DEFLATE は RFC 1591 によって定義されています。
[10] RFC 1591 は第1.3版となっていますが、第1.1版から技術的内容は変わっていません >>7。
[105] 当時としては一般的なスタイルの仕様書ですが、現代的には読みづらく厳密さが足りないといえます。 細部の規定が不十分だったり、似て非なる用語が (おそらく意図せず) 混在していたり、 同じことを異なる表現で解説しているだけなのか、別個の規定なのかはっきりしない似た記述が複数存在したり。
[2] RFC 6713 - The 'application/zlib' and 'application/gzip' Media Types ( 版) https://tools.ietf.org/html/rfc6713
zlib の圧縮アルゴリズムは PKZIP 2.x の deflate アルゴリズムで, もともとは私と吉崎栄泰さんが LHA のために開発したものをハッシュで高速化したものです(zlib のソースコード中に,ほんのちょっとですが私の名前が入っています)。 その後,LHA もハッシュを使うようになりましたので,LHA と gzip/zlib/Zip の実質的な相違はなくなりました。
[13] Efficient XML Interchange (EXI) Format 1.0 ( ( 版)) http://www.w3.org/TR/2011/REC-exi-20110310/#CompressedStreams
[112] RFC 8054 - Network News Transfer Protocol (NNTP) Extension for Compression () https://tools.ietf.org/html/rfc8054
[156] An Explanation of the DEFLATE Algorithm () http://www.gzip.org/deflate.html