PNG イメージを自力でパースしてみる ～2/6 Deflateの基本と固定ハフマン編～
ここまでのあらすじ
PNG イメージを自力でパースしてみる ～1/6 予備知識編～
周辺知識に おおかた整理がついてきたところで、いよいよDeflateに手を出してみる
なお、今回はパースが目的なので、圧縮を実装するうえで必要になる、詳細なところにまでは首を突っ込まない
Deflate圧縮
改めておさらい
Deflate（デフレート）とはLZ77とハフマン符号化を組み合わせた可逆データ圧縮アルゴリズム。
ほんの少しだけ具体的には、つぎのとおりに利用している。
- 圧縮元データを LZ77 を使って圧縮
- LZ77で圧縮したデータを、ハフマン符号化 を使ってさらに圧縮
Deflateの ”LZ77” の実装は、
どちらかといえば、LZSS のほうが それに近い。
"近い" とはどういうことなのか、
圧縮の考え方は、前の記事で紹介したLZSSとそのまま同じなのだけど、圧縮の結果、出力される各々の要素のフォーマットが、元のLZSSとは異なる。
元のLZSSでは、それが "距離" と ”一致した長さ” に置換されたか、識別できるようにするために、要素の先頭に1ビットを付加する方法を使っていた
Deflateではこの仕様が変更されている。
各々の要素は以下のいずれかの 値 で出力される。
0 ～ 255 ： 置換されなかった 0x00 ～0xff までの文字そのまま
256 ： ブロックの終端 （後で説明）
257 ～ 285 ： ”一致した長さ” & "距離"
仮に 0～285の数値を、固定長のビット並びで取り扱うならば、一応、9ビットだけあれば事足りる ( 0 ～511 まで表現可能)
ただしそのままを出力するわけではなく、それをさらにハフマン符号化によって可変長な符号へ置換するため、0～285に置換した結果、出現する値に偏りがあれば、ハフマン符号化の特性によって、普通にLZSS圧縮を行ったときよりも、データが小さくなることを期待できる。
Deflate の LZSSでは、スライド窓に同じ文字列を見つけた場合、置換された結果は "一致した長さ" → "距離" の順番になる。
※ 前の記事では "距離" → ”一致した長さ” の順番だった
257 ～ 285 の数値は "一致した長さ" を表し、その後ろに "距離" の情報が、連なって記録される。
拡張ビット
さて、"一致した長さ" は 257 ～ 285 の数字で表される。
一方で、Deflateでは ”一致した長さ” には 最小で3、最大で258まで使えると定められている。
いや...どう見ても 257 ～ 285 までの 28パターンだけでは 3 から 258 までの数値を表現することはできない。
ではどうしているのか...というと、
拡張ビット(extra bit) という方法を使っている。
257 ～ 285 までの値にはあらかじめ、それ単体が表す "一致した長さ" の数値と、
拡張ビットの数が定められている。
復号時、 257 ～ 285 の値を見つけたら、そのすぐ後ろに付随する拡張ビットを読み出し、
値が表す "一致した長さ" のベース値
＋ 拡張ビット内の値
＝ この要素があらわす本来の ”一致した長さ”
の通りに 本来の "一致した長さ" を求める。これも元の LZSS にはない Deflate独自の仕様っぽい。
257 ～ 285 までの値と、
"一致した長さ" のベース値、拡張ビット数 の対応は 以下の表のとおり
| 値 | 一致した長さ | 拡張ビット数 | 表現できる範囲 |
|---|---|---|---|
| 257 | 3 | 0 | 3 |
| 258 | 4 | 0 | 4 |
| 259 | 5 | 0 | 5 |
| 260 | 6 | 0 | 6 |
| 261 | 7 | 0 | 7 |
| 262 | 8 | 0 | 8 |
| 263 | 9 | 0 | 9 |
| 264 | 10 | 0 | 10 |
| 265 | 11 | 1 | 11 - 12 |
| 266 | 13 | 1 | 13 - 14 |
| 267 | 15 | 1 | 15 - 16 |
| 268 | 17 | 1 | 17 - 18 |
| 269 | 19 | 2 | 19 - 22 |
| 270 | 23 | 2 | 23 - 27 |
| 271 | 27 | 2 | 27 - 30 |
| 272 | 31 | 2 | 31 - 34 |
| 273 | 35 | 3 | 35 - 42 |
| 274 | 43 | 3 | 43 - 50 |
| 275 | 51 | 3 | 51 - 58 |
| 276 | 59 | 3 | 59 - 66 |
| 277 | 67 | 4 | 67 - 82 |
| 278 | 83 | 4 | 83 - 98 |
| 279 | 99 | 4 | 99 - 114 |
| 280 | 115 | 4 | 115 - 130 |
| 281 | 131 | 5 | 131 - 162 |
| 282 | 163 | 5 | 163 - 194 |
| 283 | 195 | 5 | 195 - 226 |
| 284 | 227 | 5 | 227 - 257 |
| 285 | 258 | 0 | 258 |
最大で258までの "一致した長さ" を扱えるものの、そんな長さで一致する文字列を見つけられる機会は、そう頻繁にはない。
一般的によく出現する 小さな "一致した長さ" は、”一致した長さ” のベース値のみによって表現し、大きな "一致した長さ" の表現が必要な場合に、拡張ビットを使うようにすることで、圧縮後のサイズをできる限りコンパクトにすることができる。
”一致した長さ” 情報の直後には "距離" の情報が来るのだけど、"距離" の情報も、同じ通り 拡張ビット を利用して記録される。
"距離" を表す値には 0 ～ 29 までが扱われる。この値もハフマン符号化されているため、元の値に復号したのち、それに必要な拡張ビットを読み込んで、本来の "距離" を求める。
0 ～ 29 の値と、
"距離" のベース値、拡張ビット数 の対応は 以下の表のとおり
| 値 |
距離 | 拡張ビット数 | 表現できる範囲 |
|---|---|---|---|
| 0 | 1 | 0 | 1 |
| 1 | 2 | 0 | 2 |
| 2 | 3 | 0 | 3 |
| 3 | 4 | 0 | 4 |
| 4 | 5 | 1 | 5 - 6 |
| 5 | 7 | 1 | 7 - 8 |
| 6 | 9 | 2 | 9 - 12 |
| 7 | 13 | 2 | 13 - 16 |
| 8 | 17 | 3 | 17 - 24 |
| 9 | 25 | 3 | 25 - 32 |
| 10 | 33 | 4 | 33 - 48 |
| 11 | 49 | 4 | 49 - 64 |
| 12 | 65 | 5 | 65 - 96 |
| 13 | 97 | 5 | 97 - 128 |
| 14 | 129 | 6 | 129 - 192 |
| 15 | 193 | 6 | 193 - 256 |
| 16 | 257 | 7 | 257 - 384 |
| 17 | 385 | 7 | 385 - 512 |
| 18 | 513 | 8 | 513 - 768 |
| 19 | 769 | 8 | 769 - 1024 |
| 20 | 1025 | 9 | 1025 - 1536 |
| 21 | 1537 | 9 | 1537 - 2048 |
| 22 | 2049 | 10 | 2049 - 3072 |
| 23 | 3073 | 10 | 3073 - 4096 |
| 24 | 4097 | 11 | 4097 - 6144 |
| 25 | 6145 | 11 | 6145 - 8192 |
| 26 | 8193 | 12 | 8193 - 12288 |
| 27 | 12289 | 12 | 12289 - 16384 |
| 28 | 16385 | 13 | 16385 - 24576 |
| 29 | 24577 | 13 | 24577 - 32768 |
Deflateの "距離" の情報には 最大で 32,768 までが扱える。
これは前の記事の LZ77の項でも紹介した
まとめると、257 ～ 285 の値に遭遇したとき、
"一致した長さ" と "距離" の本来の値を復元する手順は次の通り
- 257 ～ 285 の値に遭遇
- 必要な追加ビットを読み出し、本来の "一致した長さ" を算出する
- 0 ～ 29 を表す符号を読み出す
- 必要な追加ビットを読み出し、本来の "距離" を算出する
読み書き方向
コンピュータのメモリは バイト(Byte) という単位で区切られている。
1バイト(Byte) は 8ビット(bit) から成るのが一般的。
メモリ上の各バイトには、それぞれを識別するためのアドレス という番号が割り振られている。また、バイト内のビットにもそれぞれ番号が振られている。
これを踏まえて、Deflateで圧縮されたデータは、メモリに置かれるとき、先頭から、アドレスが小さい順の、ビット番号が小さい順 に並べられる。
また、Deflate圧縮データの中で複数ビットを使って表されるような要素は、それが何であるかによって、各々のビットの並びかたが異なる。
ハフマン符号
ハフマン符号は、先頭から1ビットずつ順番に読み出す必要があるため、符号の先頭（最上位ビット）から順番にパックされる。メモリ上に配置された場合、次の通りに並ぶ
それ以外
一方で、符号ではない、それそのままが 何らかの "数" を表すものは一番小さい桁のビット（最下位ビット）から順番にパックされる。メモリ上に配置された場合、次の通りに並ぶ
"符号ではないそれ以外" というのは例えば、拡張ビットや ブロックタイプ（後で説明）などの要素がこれにあたる。
Deflateの解凍のプログラムを作るとき、要素のビットが並ぶ方向 に注意すること。さもなければ、
なんか入っている数がおかしい ！ 読み出すビット数はあっているはずなのに！
なんてことが起こる（起こった）
ブロック
実際に Deflate圧縮されたデータは、ひとつ、もしくは複数の ブロック の集合で構成されている。
複数ブロックから構成されている場合は、解凍時、各々のブロックを復号した結果を、先頭から順番に連結することで、圧縮前のデータを復元できる
ブロック別に、圧縮のルールが定められている。主には次の3パターン
- 無圧縮
- 固定ハフマン
- カスタムハフマン
このうち、上で説明した LZ77とハフマン符号を使って圧縮 を実際に行うのは、固定ハフマンブロックと、カスタムハフマンブロック になる。これらについては、この次の項からひとつずつ解説してみる。
各ブロックの先頭には、3ビットからなる ヘッダー情報が付加されている。
- 最初の１ビット： BFINAL (最終ブロック判定ビット)
- 次の２ビット： BTYPE（ブロックタイプ）
BFINAL には 自身のブロックがDeflate圧縮データ中で
一番最後のブロックである場合には 1
ほかのブロックが後に続く場合には 0 が設定される
BTYPE は 自身のブロックの圧縮のルールを示す。
設定されるパターンとそれに対応する圧縮のルールは以下の通り
- 00 無圧縮
- 01 固定ハフマン
- 10 カスタムハフマン
- 11 エラー (予約域)
ここまでを踏まえて、Deflate圧縮データの解凍は、大まかには次の流れで行う
- ヘッダー情報を読み出す
- BTYPE の圧縮のルールを確認し、その後ろに続く圧縮データを復号
- BFINAL の値が 0なら繰り返し。1 なら終了。
ブロックの終端
固定ハフマンブロック と カスタムハフマンブロックでは 256 を表す符号を読み出せた地点が、そのブロックの終端になる。
無圧縮ブロックの場合は、ブロックの先頭に無圧縮データの長さ情報が、追加で付加されるため、その分のデータを最後まで読み切った地点が、そのブロックの終端になる。
符号表とスライド窓
ハフマン符号の符号表は、各々のブロックごとに用意される。
一方、LZ77のスライド窓は、前のブロックで出現した文字列を、次のブロックにも引き継ぐことができる。
固定ハフマン符号化 (BTYPE:01)
ここから、各ブロックの圧縮ルールについて紹介
固定ハフマン では、あらかじめ用意された符号表に従って、データの符号化と復号を行う。符号表が事前に定められているため、圧縮データの中に符号表は埋め込まれない。
文字 または 一致した長さ を表す、0 ～285 までを収める符号表と、距離 を表す、0 ～ 29 までを収める符号表は、それぞれ別に定義される。
文字と一致した長さの符号表は、次の通りに定義される
| 値 | ビット数 | 符号 |
|---|---|---|
| 0 - 143 | 8 | 00110000 - 10111111 |
| 144 - 255 | 9 | 110010000 - 111111111 |
| 256 - 279 | 7 | 0000000 - 0010111 |
| 280 - 287 | 8 | 11000000 - 11000111 |
表の符号間の値は連番になっている。
よく見ると 286 と 287 が符号表に含まれることになっている。ただし、この値が圧縮データ中に出現することはない
あくまで使用されるのは 0 ～ 285まで。符号のキリがいいから、符号表には含まれたのかもしれない
距離 の符号表は、次の通りに定義される
| 値 | ビット数 | 符号 |
|---|---|---|
| 0 - 31 | 5 | 00000 - 11111 |
すべての符号が 5ビットの固定長で、0からの連番になっているため、5ビットの長さで読み出した符号そのままを 0 ～ 29 を表す値としてみなすことができる。
ただし、あくまで扱いは "数値" ではなく "符号" なので、5ビットいっぺんに読み出す場合は、それが 符号のビット並びに なっていることに注意すること。
ここでも符号のキリがいいからか、 30 と 31 が符号表に含まれる。例によってこの値も、圧縮データ中に出現することはない
固定ハフマンブロックは、 符号表を圧縮データ中に含まないため、その分だけ 圧縮データのサイズを節約できる。
ASCII文字からなるテキストなど、主に144 - 255 の範囲の文字が出現しにくいデータの圧縮に向く。ただし圧縮効果は、それほどよろしくはないとのこと
そもそもデータ中の文字の出現率によらず、あらかじめ用意された符号表を使うこのアルゴリズムを"ハフマン符号" と呼んでもいいのかどうかが 自分の中でちょっと疑問だったりする...
サンプル
ここまでのサンプルプログラム
VC2015でのみ動作確認済み。
参考にしたサイトさん
RFC 1951 DEFLATE Compressed Data Format Specification version 1.3 日本語訳 - futomi's CGI Cafe
デフレート圧縮(LZ77圧縮)処理の概要 - ウェブで用いられる画像形式。
