余分なビット列

Edit New

DEFLATE (圧縮アルゴリズム)

[148] DELFATE は、圧縮形式の1つです。非常によく用いられています。

仕様書

[152] deflate は RFC 1951 により定義されています。

データ形式

[124] RFC 1591 は、 圧縮された DEFLATE データのことを圧縮データ集合と呼んでおり、 圧縮の前の元のデータのことを入力データ (input data) >>25 と呼んでいます。

[12] DEFLATE の処理において入力データはブロックの連なり >>25 と解釈されます。また圧縮データ集合 (compressed data set) は、 ブロックの系列です >>25。 入力データのブロックを処理したものが、 それぞれ順に圧縮データ集合のブロックとなります。

[8] 圧縮器 (compressor) は、 仕様にすべて従うデータ集合を生成しなければなりません >>7。

[6] 展開器 (decompressor) は、 特に定める場合を除き、 仕様に適合する任意のデータ集合を受理し展開 (decompress) できなければなりません。 >>7

ビット列の表現

[27] DEFLATE の出力はバイト列です。 バイト内のビット順は規定されておらず >>26、 プラットフォームやプロトコルに依存します。

[29] 多バイトの値は、重みの小さなバイトから順に並べたバイト列 >>26 (小エンディアン) とします。

[28] データ要素 (data element) をバイト列にする際には、 バイトの重みの小さなビット (LSB) から順に詰めていきます。 >>26

[30] ハフマン符号以外のデータ要素は、 当該データ要素の LSB から順に詰めていきます。 >>26

[31] ハフマン符号は、重みの大きなビット (MSB) から順に詰めていきます。 >>26

ブロック

[62] 入力データのブロック (block) の大きさは任意に決められますが、 65535 バイト以下でなければなりません。>>25 圧縮器は、ブロックの最大長を制限できます。 しかし展開器は、任意の長さを扱えなければなりません。 >>26

[63] 圧縮データ集合のブロック (block) は、 入力データの各ブロックに対応します。 >>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] ブロックの圧縮されたデータ部分 (compressed data part) は、 要素の系列です。各要素は、 リテラルバイト群 (literal bytes) か、 重複列への指示子 (pointer to duplicated strings) かのいずれかです。 >>25

[21] 重複列への指示子は、 長さ (length) と前方向の距離 (backward distance) との組です。 >>25

[22] 長さは、 258 バイト以下です。 >>25

[17] 距離は、 32KB 以下です。すなわち、指示子は、入力データの 32KB 前までのブロックの列 (string) を参照できます。 >>25 圧縮器は、より小さな距離を上限としても構いません。 しかし展開器は、 32KB まで処理できなければなりません。 >>26

[146] 指示子は、入力データのブロックの境界をまたがることができます >>25。しかし入力データの先頭より前を指すことはできません >>25。 入力データの先頭より前の指示子が与えられた時、どう処理するべきかは不明です。

[157] 距離の上限は、 圧縮器や展開器が探索のために保持しておかなければならないバッファーやリスト (>>129) のサイズに影響します。 DEFLATE を用いるプロトコルは、 これを制限したり、制限を記述できたりする場合があります。

LZ77 sliding window 参照。

[23] リテラルと長さは、そのブロックのリテラル・長さ符号により符号化します。 距離は、そのブロックの距離符号により符号化します。

[147] 不正な符号が現れたときにどう処理するべきかは不明です。

[16] 各ブロックのハフマン木は、互いに独立です。 >>25

予約

[141] BTYPE の値 112 は、予約 (誤り) とされています。 >>26

[14] 112 が出現した時、これをどう処理するべきかは、不明です。

ハフマン符号化

[32] 接頭辞符号化 (prefix coding) は、 事前に与えられた字母 (alphabet) の記号 (symbol) を、 ビット列 (符号) として表現するものです。ここで、ビット列は記号ごとに長さが異なりますが、 構文解析器が常に曖昧無く記号を認識できるようにします。 >>26

[33] 接頭辞符号は、二分木を使って定義します。 枝が 0 または 1 のいずれかを表すこととします。 枝がいずれかの記号を表すこととします。 根から葉までの枝の値を順番に並べたものが、符号を表します。 >>26

[35] 構文解析器は、二分木の根から順に入力のビットに従い進むことで、 記号を得ることができます。 >>26

[34] 次の木は、次の表のような符号を表しています。

                          /\         
                         0  1        
                        /    \       
                       B     /\
                            0  1           
                           /    \          
                          A     /\
                               0  1
                              /    \
                             C      D

記号 符号
A10
B0
C110
D111

[36] ハフマン算法により、字母とその頻度から最適な接頭辞符号を得られます。 頻度が高いほど身近な符号となります。これをハフマン符号といいます。 >>26

[37] ただし DEFLATE では符号長の上限があるので、少し複雑になります。 >>26

[38] DEFLATE では次の2つの制限があります >>26。

[42] この制限を設けることで、記号に対応するビット長 (符号長 (code length) ) のリストを示すだけで、 符号を記述できます >>26。

[41] 先程の例 (>>34) では、符号は 0 < 10 < 110 = 111 と符号の長さの順が符号の順序と一致しています (>>40)。 また C < D と記号の順序と同じ長さの符号の順序が一致しています。

[43] 記号群 (A, B, C, D) を表すこの符号群は、 各符号のビット長から (2, 1, 3, 3) と表すことができます。 (このビット長の組によって表される符号は一意に定まります。)

[44] N 個の記号について、符号長のリスト長さ群から、 対応する符号を n ビットの整数のリストとして得るには、 次のようにします。 >>26

  1. [45] 符号群を、空リストに設定します。
  2. [46] 個数群を、空リストに設定します。
  3. [49] [ 0, n ] の各長さについて、
    1. [50] 個数群 [ 長さ ] を、 0 に設定します。
  4. [47] 長さ群の各長さについて、
    1. [48] 個数群 [ 長さ ] を、 1 インクリメントします。
  5. [51] 符号を、 0 に設定します。
  6. [55] 次符号群を、空リストに設定します。
  7. [52] [ 1, n ] の各長さについて、順に、
    1. [53] 符号を、 (符号 + 個数群 [ 長さ - 1 ]) << 1 に設定します。
    2. [54] 次符号群 [ 長さ ] を、符号に設定します。
  8. [56] [ 0, N ] の各記号について、
    1. [57] 長さを、長さ群 [ 記号 ] に設定します。
    2. [58] 長さが 0 以外なら、
      1. [59] 符号群 [ 記号 ] を、次符号群 [ 長さ ] に設定します。
      2. [60] 次符号群 [ 長さ ] を 1 インクリメントします。
  9. [61] 符号群を返します。

ブロックで用いるハフマン符号の記号

[102] 符号化されたブロックでは、2種類のハフマン符号を使います。

[118] DEFLATE のハフマン符号は、 実際の各符号の直後に、 いくつかの余剰ビット群 (extra bits) が続く場合があります。

[101] 余剰ビット群は、 MSB から順に並べたものと解釈します。 >>26

[117] 1つ目のハフマン符号は、 リテラルバイト (実際に表したいデータのバイト) や長さを表すもので、 リテラル・長さ符号 (literal/length code) >>26 (字母は リテラル・長さ字母 (literal/length alphabet) >>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

[119] 2つ目のハフマン符号は、距離を表すものです。

[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 のブロックの圧縮されたデータ部分は、 固定ハフマン符号 (fixed Huffman code) を用いて符号化したデータです。

[120] 固定ハフマン符号ブロックのリテラル・長さ符号は、 次のような符号長の持つハフマン符号とします。 >>26

[107] ただし、 286 と 287 は実際には使われません。 >>26

[108] 固定ハフマン符号の距離符号 [ 0, 31 ] は、 そのまま5ビット固定長 (+ 余剰ビット群) で表します。 >>26

[109] 30 と 31 は実際には使われません。 >>26

[24] 圧縮されたデータ部分の末端は、 256 により表されます。 これが現れないで与えられたデータが終了した時展開器がどう処理するべきかは不明です。

動的ハフマン符号

[113] BTYPE 102 のブロックの圧縮されたデータ部分は、 動的ハフマン符号 (dynamic Huffman code) のハフマン木と、 それを用いて符号化したデータです。

[122] 動的ハフマン符号のブロックは、次のもので構成されます >>26。

5ビット (HLIT)
リテラル・長さ符号の数 - 257
5ビット (HDIST)
距離符号の数 - 1
4ビット (HCLEN)
符号長符号の数 - 4
((HCLEN + 4) × 3) ビット
符号長字母の符号長を 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 の順に並べたもの。 各符号長は3ビット整数で表す。
(HLIT + HDIST + 258) ビット
次のもの:
(HLIT + 257) ビット
リテラル・長さ符号の字母ごとの符号長を並べたもの。
(HDIST + 1)
距離符号の字母ごとの符号長を並べたもの。
符号長符号で符号化する。リテラル・長さ符号部分と距離符号部分の境界をまたがって符号化される場合もある。
任意長
リテラル・長さ符号および距離符号により圧縮されたデータ (末端は 256)

[123] 使用するハフマン符号のハフマン木は、 その符号長のリストとして記述します。 符号長は、次の字母を持つハフマン符号 (符号長符号 (code length code) ) によって記述します >>26。

[114] ここで、符号長 0 は、 該当する記号が字母に現れないため、 ハフマン符号構築アルゴリズムで省くべきことを示します。 >>26

[115] 距離符号が1つだけしか使われない場合には、 1ビットのみを使って符号化し、 0ビットは使いません。 この場合、符号長が1つと未使用の符号が1つとなります。 0ビットの符号1つの場合は、距離符号を使わない (すべてのデータがリテラルである) ことを表します。 >>26

[19] 展開器に与えられたデータが記述された長さと矛盾する時、 どう処理するべきかは不明です。

[121] 末端に 256 が現れないで与えられたデータが終了した時展開器がどう処理するべきかは不明です。

辞書

[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 により圧縮することを想定したものであり、 強く推奨 (strongly recommended) される、 特許問題が無いと考えられる算法が示されています。 もちろん、それ以外の方法により生成することも認められています。 >>116

[128] 圧縮器は、 新しいハフマン木が有用と考えられる時や、 ブロックサイズが圧縮木のブロックバッファーの末尾に達した時、 ブロックを終えます。 >>116

[129] 圧縮器は、 重複する文字列を探すため、 3バイトの列に対するハッシュ関数を使った連鎖ハッシュ表 (chained hash table) を使います。 入力の次の3バイトがハッシュ表にあれば、 該当するハッシュ鎖のすべての文字列のうち最長一致のものを選択します。 ハッシュ表にない場合は、リテラルバイトとしてそのまま出力します。 >>116

[130] ハッシュ鎖の探索では、距離を小さくするため、直近の文字列から探していきます。 ハッシュ鎖はどんどん連結していき、削除はしませんが、 古すぎるものは一致しても採用しません。 >>116

[131] 圧縮器は、 一致したものの選択を遅延させても構いません (lazy matching)。 ある位置で一致しても、更に先でより長い一致があるなら、そちらを使うことにできます。 >>116

復号 (展開)

[68] 入力ストリームの復号は、次のようにします。 >>26 ただし、入力ストリームから読むとは、現在位置から指定された長さのビット列を返し、 現在位置をその次のビットまで進めることをいいます。

  1. [74] 出力を、空バイト列に設定します。
  2. [90] 繰り返し、
    1. [69] BFINAL を、入力ストリームから1ビット読んだ結果に設定します。
    2. [70] BTYPE を、入力ストリームから2ビット読んだ結果に設定します。
    3. [92] BTYPE が 112 なら、
    4. [71] BTYPE が 002 なら、
      1. [72] 入力ストリームの現在のバイトの残りのビットをすべて読みます。
      2. [73] LEN と NLEN を得ます。
      3. [75] 入力ストリームから LEN バイト読んだ結果を、 出力の末尾に追加します。
    5. [76] それ以外なら、
      1. [77] BTYPE が 102 の場合、
        1. [78] 符号を、符号木の表現を読んだ結果に設定します。
      2. [125] それ以外の場合、
        1. [126] 符号を、固定ハフマン符号に設定します。
      3. [79] 繰り返し、
        1. [80] 値を、入力ストリームからリテラルと長さの値を復号した結果に設定します。
        2. [81] 値 < 256 なら、
          1. [82] 出力の末尾に値を追加します。
        3. [83] それ以外なら、
          1. [84] 値 = 256 (end of block) なら、
            1. [85] 繰り返し (>>79) を終えます。
          2. [86] それ以外なら [ 257, 285 ]、
            1. [87] 入力ストリームから距離を復号します。
            2. [93] 位置を、出力の長さ - 距離に設定します。
            3. [94] 位置が負の時、...
            4. [95] 繰り返し、
              1. [98] 出力 [ 位置 ] を、出力の末尾に追加します。
              2. [99] 位置を 1 インクリメントします。
              3. [88] 距離を 1 デクリメントします。
              4. [96] 距離が 0 なら、
                1. [97] 繰り返し (>>95) を終えます。
    6. [89] BFINAL が設定されていれば、繰り返し (>>90) を終えます。
  3. [91] 出力を返します。

文脈

[1] DEFLATE は次の場面で用いられています。

[154] DEFLATE の応用

[153] zlib と gzip は、 DEFLATE に簡単にラップしたデータ形式です。 zlib はメモリー上や通信での利用を想定した短いヘッダーと高速な整合性検査を採用しており、 gzip はファイルとしての利用を想定したメタデータを格納できるようになっています >>155。

関連

[3] HTTP の内容符号化 deflate については、 zlib を参照。

歴史

[9] DEFLATE は RFC 1591 によって定義されています。

[10] RFC 1591 は第1.3版となっていますが、第1.1版から技術的内容は変わっていません >>7。

[11] 第1.0版には言及がなく、存在したのか不明です。

[105] 当時としては一般的なスタイルの仕様書ですが、現代的には読みづらく厳密さが足りないといえます。 細部の規定が不十分だったり、似て非なる用語が (おそらく意図せず) 混在していたり、 同じことを異なる表現で解説しているだけなのか、別個の規定なのかはっきりしない似た記述が複数存在したり。

[2] RFC 6713 - The 'application/zlib' and 'application/gzip' Media Types ( 版) https://tools.ietf.org/html/rfc6713

[4] zlib 入門 ( 版) https://oku.edu.mie-u.ac.jp/~okumura/compression/zlib.html

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

Updated: