図解Deflateアルゴリズム 2/2 ー 圧縮の流れとDeflateブロックの構造
導入
前回の記事ではDeflateを構成するハフマン符号とLZ77アルゴリズムについて解説しました。
今回はDeflate圧縮におけるハフマン符号、LZ77アルゴリズムの使われ方や出力結果のビット表現について解説します。
Deflate圧縮の流れ
DeflateではまずLZ77で圧縮を行い、パターンに一致する長さ（一致長）・オフセット・最初の不一致文字の組を出力します。
そして、その出力をハフマン符号化で圧縮を行うことで最終的な圧縮結果が算出されます。
出力はブロック単位で行われ、構造は以下の通りとなります。
第一ビットBFINALは、それが圧縮データ集合の最後のブロックかどうかを表します。 ビットが設定されていれば、最後です。
第2ビットと第3ビットのBTYPEは、圧縮方法を表します。
BTYPEが00であれば圧縮しないことを表します。01であれば固定ハフマン符号を用いて圧縮され、10であればカスタムハフマン符号を用いて圧縮されます。11の場合は定義されていません。
データの部分には上記のLZ77とハフマン符号化により圧縮されたデータが格納されます。
LZ77の出力表現
まずハフマン符号で符号化する対象を知る必要があるため、LZ77の出力結果がDeflateにおいてどのようなビット列で表現されているかを解説します。
LZ77の出力はパターンに一致する長さ（一致長）・オフセット・最初の不一致文字の組です。
Deflateにおいて一致長は長さ符号、オフセットはオフセット符号により表現されます。不一致文字は文字コードでエンコードされます。
長さ符号
Deflateの仕様上、パターンに一致する長さは3~258の間に制限されています。
この長さが0x101 ~ 0x11Dの値で表現されます。
以下に符号と一致長の対応表を提示します。
完全な対応表はこちらを参照してください。
| 符号 | 余剰ビット | 長さ |
|---|---|---|
| 0x101 | 0 | 3 |
| 0x102 | 0 | 4 |
| ... | ... | |
| 0x109 | 1 | 11~12 |
| 0x10A | 1 | 13~14 |
| ... | ... | |
| 0x11B | 5 | 195~226 |
| 0x11C | 5 | 227~257 |
| 0x11D | 0 | 258 |
長さ３から符号が始まっていますが、これは長さが3~258に制限されているため2以下の長さが不要であるためです。
上の表には一つの符号で複数の長さを表しているものがありますが、これは符号に後続する余剰ビットによって値を確定します。
例えば長さが197の場合を考えます。上の表で197に対応する符号は0x11Bです。
符号0x11Bの余剰ビットは5bit分あります。この余剰ビットで197 - 195 = 2を表現します。つまり、0b00010が余剰ビットとなります。
197 = 195 + 2 → 0x11B, 0b00010
この長さ符号はさらにハフマン符号化されて格納されます。
オフセット符号
オフセットは1 ~ 32768に制限されています。
この長さを0x00~0x1Dの値で表現します。
| 符号 | 余剰ビット | オフセット |
|---|---|---|
| 0x00 | 0 | 1 |
| 0x01 | 0 | 2 |
| ... | ... | |
| 0x04 | 1 | 5~6 |
| 0x05 | 1 | 7~8 |
| ... | ... | |
| 0x1B | 12 | 12289~16384 |
| 0x1C | 13 | 16385~24576 |
| 0x1D | 13 | 24577~32768 |
長さ符号と同様に余剰ビットが後続します。
余剰ビットの扱いについては長さ符号と同様です。
オフセット符号もさらにハフマン符号化されますが、Deflate圧縮においてオフセット符号は長さ符号や不一致文字を符号化するための符号表とは異なる符号表で符号化されます。
例
以下は文字列ABRACADABRAをLZ77で圧縮した出力例です。
ABRACADABRAの末尾のABRAがスライディングウィンドウの参照部のパターンと一致していることがわかります。
一致長は4で、一致パターンのオフセットは7です。
これを長さ符号、オフセット符号で符号化すると一致長258、オフセットは5+0(太字は余剰ビット)となります。
その他の不一致文字はASCIIでエンコードされます。圧縮データの末尾にはブロック終端を示す256が配置されます。
LZ77の出力のハフマン符号化
DeflateにおいてLZ77の出力結果はハフマン符号化されます。
ここで使用するハフマン符号はあらかじめ定義されたもの（固定ハフマン符号）を使用するか、カスタムの符号（カスタムハフマン符号）を使用するかを選択できます。
固定ハフマン符号では符号表が固定であるため符号表を圧縮データに含める必要がありません。そのため符号表分のサイズを削減できますが、その一方で符号表は最適ではない可能性があります。
カスタムハフマン符号では符号表が可変のため符号表を圧縮データに含めなければなりませんが、実際の出現頻度に基づいて符号表が作成されるため最適な圧縮が可能です。
また、前述した通り、ハフマン符号化の符号表は２種類使用されます。
LZ77の出力のうち、オフセットの符号化に一つ目のハフマン符号表を使い、パターンに一致する長さ、パターンに一致しない文字の符号化にもう一つの符号表を使用します。
固定ハフマン符号
固定ハフマン符号では、あらかじめ用意された符号表に従って、データの符号化と復号を行います。
不一致文字、一致長を符号化するための符号表は以下の通りです。
| 値 | ビット数 | 符号 | 符号と値の変換方法 |
|---|---|---|---|
| 0 - 143 | 8 | 00110000 - 10111111 | (符号を10進数に変換したもの) - 48 = 値 |
| 144 - 255 | 9 | 110010000 - 111111111 | (符号を10進数に変換したもの) - 256 = 値 |
| 256 - 279 | 7 | 0000000 - 0010111 | (符号を10進数に変換したもの) + 256 = 値 |
| 280 - 287 | 8 | 11000000 - 11000111 | (符号を10進数に変換したもの) + 78 = 値 |
距離符号は5bitの固定長です。0b00000～0b11111までの連番で0から31までの値を表現思案す。
カスタムハフマン符号
カスタムハフマン符号の符号表は以下の流れで作成されます。
- LZ77でデータを圧縮
- カノニカル・ハフマン符号化
- 符号長表を符号化
- 圧縮データを配置
カノニカルハフマン符号化
カノニカルハフマン符号とは特殊なハフマン符号で、符号長を定めれば一意に符号を定めることができるという特性があります。
この特性のため、符号表には符号長のみを含めれば良くなるので符号表のサイズを削減することが可能です。
ABRACADABRAをLZ77圧縮した圧縮結果をカノニカルハフマン符号化する例を以下に提示します。
符号長表の圧縮
このカノニカルハフマン符号の符号長表自体がさらに圧縮して格納されます。
まず符号長表を、値の昇順に連続して連なるリスト構造に展開します。このうち、符号長表内に存在しない値に対しては符号長：0が割り当てられます。
上記の表の中で符号長表に存在する値の最大値以下の部分が圧縮の対象となります。図の肌色の部分です。
符号長表の圧縮手順は以下のとおりです。
- 符号長表の同じ値が連続する部分を以下の表に従ってランレングス符号化する
| 値 | 符号 |
|---|---|
| ひとつ前に出現した値が3～6回繰り返される | 16 (余剰ビット：2) |
０が3～10回繰り返される |
17 (余剰ビット：3) |
０が11～138回繰り返される |
18 (余剰ビット：7) |
以下がランレングス符号化の例です。
上の符号長表では0~64までの値で符号長が全て0になっています。つまり65回分0が連続しています。
表に従うと符号は18となります。そして65 - 11 = 54であるため7bitの余剰ビットで54を表します。
つまり、余剰ビットは0b110110となります。
同様に同じ値の連続を符号化していきます。
- ランレングス符号化した符号長表をカノニカルハフマン符号で符号化する
ランレングス符号化を終えたら、不一致文字/一致長の符号表とオフセット符号表を合わせて出現頻度を算出し、カノニカルハフマン符号化を行います。
圧縮データの配置
カスタムハフマンブロックは以下の構造となっています。
| 項目名 | サイズ | 説明 | 値 |
|---|---|---|---|
| HLIT | 5bit | 文字/長さ符号の符号表に含めた符号の個数 (257 ～ 286) を表す値が設定される | 個数-257した 0～29までの範囲の値が５ビット長の中に収められる |
| HDIST | 5bit | 距離符号表に含めた符号の個数 (1 ～ 32) を表す値が設定される | 個数-1した0～31までの範囲の値が５ビット長の中に収められる |
| HCLEN | 4bit | 符号長表の符号長表のサイズ | 符号長表の符号長表に、符号長がいくつ含まれているか(<19)を表す値が設定される |
| 可変サイズ | 符号長表の符号長表 | 詳細下記 | |
| 可変サイズ | 文字/長さ符号の符号表 | ||
| 可変サイズ | 距離符号の符号表 |
符号長表の符号長表
符号長表の符号長表は以下のような変則的な順番で並べられます。
16、 17、 18、 0、 8、 7、 9、 6、 10、 5、 11、 4、 12、 3、 13、 2、 14、 1、 15
各符号長値は3bitの幅で収められます。
以下が符号長表の符号長表の例です。
Deflate出力のビット表現(Deflateストリーム)
Deflateの出力はバイト列です。出力データはリトルエンディアン（アドレスが小さいバイトから順に）並べられます。
数値は下位ビット（LSB）から順に詰めていきます。
以下は数値データ1,3,7をストリームに配置した例です。アドレスの小さいバイトから順にデータのLSBから配置されているのが確認できます。
一方、ハフマン符号を処理するときは、上位ビット（MSB）から順に詰めていきます。
以下は符号011,1011,11011をストリームに配置した例です。アドレスの小さいバイトから順にデータのMSBから配置されているのが確認できます。
実際のDeflateブロックを解析
pythonのzlibモジュールを例にDEFLATE圧縮されたデータのバイナリを解析しましょう。
zlib.compressの出力から先頭２バイトのヘッダと末尾４バイトのチェックサムを取り除くことにより生の DEFLATEデータを得ることができます。
簡単のため、aaaaaという文字列を例に見ていきます。
>>> zlib.compress(b"aaaaa")[2:-4]
b'KL\x04\x02\x00' ('\x4b\x4c\x04\x02\x00')
以下にビットレベルで解析した図を提示します。
最初の1bitは最終フラグを表しています。最終フラグは1であり、このブロックが最終であることを意味します。
次の2bitはブロックの種類を表します。これは10ですが、下位ビットから配置されているため実際の値は01になります。 これはこのブロックが固定ハフマン符号で圧縮されていることを表しています。
残りの部分はデータ領域です。固定ハフマン符号の符号表に基づき、デコードしていきます。
最初のデータは10010001です。これはaを表すハフマン符号です。ハフマン符号のため、上位ビットから配置されます。そのため、実際の値も10010001となります。
次も10010001です。同様にaを表します。
その次は0000001です。固定ハフマン符号表を参照すると0x101であることが確認できます。これは長さ符号であり、長さ符号の符号表を参照すると長さ3を表すことが確認できます。
次は00000です。オフセット符号であり、5bitの固定長です。オフセット符号は5bitの連番であるため、00000は0x00を表します。
オフセット符号表を参照すると0x00はオフセット１を表します。
最後が0000000です。固定ハフマン符号表を参照すると0x100を表します。0x100は最終フラグです。
以上でDeflateブロックの解析は終了です。
最初にa,その次もaでその後にaが３連続で続くことを表していることが確認できました。
まとめ
Deflate圧縮の流れとDeflate圧縮結果のbit表現について解説しました。
この記事が参考になった方はいいねを押してもらえると嬉しいです。よろしくお願いします。
参考資料
Discussion