package-merge algorithmを勉強してみる
最大符号長の制限されたハフマン符号表を生成する方法として package-merge algorithm っていうのがあるらしい。気が向いたのでちょっと調べてみる
今回は以下の資料さんを参考にさせていただいた
自身の理解できた範囲でそれぞれ順番に紹介してみる
package-merge algorithm
前述のとおり package-merge algorithm は、最大符号長の制限されたハフマン符号表を生成するために利用できる
ただし、符号表中の符号を ある長さまでに制限するためには、
符号表を生成する元として使う、シンボルの種類の数に制限がかかる
たとえば最大符号長を「2」に制限して符号表を作成した場合、
その中で同時に定義ができる接頭符号の種類は、多くて4つまで
| 00 | 01 | 10 | 11 |
最大符号長を「3」に制限した場合では、
その中で同時に定義できる接頭符号の種類は、多くて8つまでになる
| 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
この通り、最大符号長を と定義した時、
表現できる符号の種類の最大は、 のように表すことができる
シンボルの種類の数を とするとき、
を満たさなければ、最大符号長を L に制限した中で、それぞれのシンボルに対して、きちんと接頭符号を割り当てることができない。
package-merge algorithm は上の制約を満たす各々のシンボルに対して、指定した符号長以下になるよう符号を割り当てて、符号表を作成するのを手助けしてくれる アルゴリズムである。
生成手順
はじめに断っておくと、package-merge algorithm 単体ではハフマン符号を生成することはできない
package-merge algorithm が出力できるのは、各々のシンボルを符号化したときの 符号長 までにとどまる
そこから実際に符号を割り当てて、符号表を求めるには、 カノニカル・ハフマン符号化 を利用する。カノニカル・ハフマン符号化については、以前別の記事で紹介した
符号化対象のデータに含まれる、各々の文字を シンボルデータ中で各々の文字が出現する回数を シンボルの重み として扱い、
[シンボル, 重み] のペアからなるリストと、制限したい符号の長さ情報が与えられたとき、package-merge algorithmを使って符号表を生成する手順を以下に示す
１. ステージの初期化
制限したい符号の長さの数だけのステージを用意し、シンボルのリストの内容物によってそれぞれ初期化する。
ここであらかじめ、一番上のステージのリストはシンボルの重みの昇順にソートしておく。
２. パッケージマージ
一番上のステージにある要素を、先頭から順番に2つずつ選び出し、そのペアからなる パッケージ をそれぞれ作成する。
その後、作成したパッケージを一つ下のステージにマージする
ここで パッケージ はペアとなる要素それぞれへの参照と、その2つの要素の重みの合計値を自身の重みとして持つ。なお、ペアを作れなかった要素に対しては何も行わず無視する
マージ後、そのステージの要素を昇順に並べ替える。
またその後、そのステージで2つずつのペアを作ったとき、ペアを組めず無視されるであろう要素があれば、あらかじめそのステージから除外しておく
ここまでのパッケージマージの流れを、今度は２番目のステージから、その下の３番目のステージに対して行い、最終的に一番下のステージにたどり着くまでこれを繰り返す
３. 符号長を抽出
最終的に、一番下のステージに出揃った各々の要素を一つずつピックアップし、各々の要素が持つシンボル、またはその要素が参照しているシンボルの数だけ該当のシンボルの符号長をインクリメントする
各々のシンボルの符号長は、多くてステージの数までとなり、パッケージマージの過程で、無視され除外された回数の多いシンボルほど、最終的な符号長が小さくなるという仕組みになっている
４. 符号表を作成
後はカノニカル・ハフマン符号化の手順に従って、各々のシンボルの符号長から 符号表を作成する
- 符号長別にグループ分けした後、その中で文字番号の小さい順に並べかえる
- 符号長が短く文字番号の小さなシンボルほど小さな符号になるよう符号を割り当てる
これで、package-merge algorithm によって最大符号長の制限された符号表が完成する
遅延 package-merge
package-merge algorithm は 一番下のステージに出揃った要素をピックアップして、各々のシンボルの符号長を求める
この一番下に出揃う要素について、その数に着目すると、
ステージの数にかかわらず、必ず だけになる。
このあたりなんかうまくそうできてるらしい
これから察するに、最後のステージに対して、 回だけ要素の作成を要求して、その過程で必要になり次第、上のステージの要素を作成してパッケージを貰ってくる...というアルゴリズムが組めそうだ。
実際に必要になるまで上のステージの要素の作成を遅らせる様子から、
このアルゴリズムのことを、
遅延 package-merge (Lazy package-merge) と呼ぶことにする。
生成手順
各々のステージは それぞれ以下の情報を保有する
- 要素1 (先読みツリー)
- 要素2 (先読みツリー)
- シンボルカウンタ
このうち、2つの "要素" は 自身の一つ下のステージで、次にパッケージを作成する元として使われるであろう候補の要素を事前に知っておくために保有しておく
冒頭で紹介した資料さんによれば、
この要素のことを 先読みツリー (lookahead tree) と呼ぶそうだ
なお最下段のステージは、自身の下にパッケージを提供するステージが存在しないため、先読みツリーを持たなくても構わない。
"シンボルカウンタ" は自身のステージで、[シンボル,重み] のリストを いくつだけ読んだかの情報を覚えておくために、その数を保持する。
遅延 package-mergeを使った符号表の生成手順を以下に示す
１. シンボルリストをソート
[シンボル,重み] のリストを、あらかじめ重みの昇順になるように並べ替えておく
２. ステージの初期化
一番下のステージを除いて、各ステージ上の先読みツリー2つを、重みの昇順に並んだ [シンボル,重み] リストの上二つの要素で初期化する。
また、シンボルカウンタには、リストを "2つ" 読み出したことを記録しておく
３. 要素を作成
これから、最下段ステージに要素を作成する次の手順を、 回だけ繰り返す
まず、[シンボル,重み] のリストから次に読み出せる要素の重みと、自身の一つ上の先読みツリー2つの重みの合計のどちらが小さいかを比較する。
リストの要素の重みのほうが小さければ 3.1 の処理、そうではない場合、またはシンボルのリストから読み出せる要素がもうない場合は 3.2 の処理へ進む
3.1 [シンボル,重み] リストの要素を追加
[シンボル,重み] のリストから読み出した要素を自身のステージに追加する。
その後、シンボルカウンタを1つ進める。
なお、１番目、２番目に追加される要素は必ず、[シンボル,重み] のリストの１番目、２番目の要素になるため、２. ステージの初期化 で各ステージを初期化する際に、この要素２つをあらかじめ 最下段ステージに作成しておいてもかまわない。
3.2 先読みツリーのパッケージを追加
一つ上のステージの先読みツリー2つからパッケージを作成し、自身のステージへ追加する。
一つ上の先読みツリーからパッケージが作成されるたび、ここまでの 3.要素を作成 の手順を、今度は一つ上のステージに対して2回行うことで 先読みツリー2つを更新する。
この過程でさらに上のステージの先読みツリーからもパッケージが作られれば、そのステージでも同じ通り、新しい要素を作成する手順を2回行う。
それよりさらに上のステージでも同様、最終的に更新が必要な先読みツリーすべてに対して、新しい要素が補填されるまでこの処理は繰り返される
なお最上段のステージは、上にパッケージを貰ってこれるステージが存在しないため、常に [シンボル,重み] リストの まだ読んでいない新しい要素 2つによって先読みツリーを更新する
最下段のステージに 個の要素がそろえば、あとは通常の package-merge algorithm の時と同様の手順で、各シンボルの符号長を導出し、符号表を作成できる
利点
早いうちに最下段ステージに要素が作成されるというのが、このアルゴリズムの特徴になる。これによる利点は、メモリ空間の再利用ができるということ
符号長を導出する手続きは、なにも最下段のステージに要素がすべて出揃うのを待つ必要はない。 要素が一つ新しく作成されるたびに、その要素がもつシンボル、またはその要素が参照するシンボルの符号長を更新することができる。
符号長の更新後、その要素とそれが参照している要素は、もう扱われることがない。そのため、それらの要素を保持するために使ったメモリ空間は、これより以降に要素を作成するために使いまわすことができる。
要素のプールを作成してこれを実現する場合、
資料さんによれば、プールの "空き要素" は つだけ必要とのこと。
(資料さんに載ってるここの証明がうまく理解できなかった。悔しい)
※ 2017/01/07追記
たまに で空き要素が足りないことがあるっぽい。一番下のサンプルプログラムのほうは、ステージの数を減らしたりして ひとまず対処してみてるけど、理由はよくわかってない
なお、 はシンボルの数、
は制限したい符号の長さを表す。
境界 package-merge
package-merge algorithm で 生成した各ステージ上の要素のうち、実際にシンボルの符号長を求めるために使われた要素に対して色を付けてみる。
最下段のステージを除いて、それより上にある各ステージはともに、ある要素を境にして、実際に符号長の導出のために使われた要素(左側) と使われなかった要素(右側)に分かれるのがわかる。
この色のついた左側にある要素を、以降は "アクティブな要素" と呼んで扱うことにする
さらにこのアクティブな要素のうち、シンボル単体からなる要素 (パッケージではない要素) に着目し、その数を数えてみる
シンボル単体からなる要素は、各ステージともに、その重みの小さい順にもれなく出現している
そのため、アクティブなシンボル単体の要素の数が、その中で ２ であるとするならば、そこには重みの一番小さなシンボルと、2番目に小さなシンボルの 2つ が必ず現れる
アクティブなシンボル単体の要素の出現回数を と定義するならば、重みの昇順に並んだ １～
番目までのシンボル単体からなる要素が、そこには出現することになる
この通り、アクティブなシンボル単体の要素の出現回数だけを ステージごとに覚えておきさえすれば、後から実際に出現したシンボル単体の要素が何であるかを推測できる
出現回数から、実際に出現するシンボルが何であるかを割り出せれば、あとはそのシンボルの符号長をインクリメントする...という方法で同じ通り符号長の導出ができそうだ。
アクティブな要素とアクティブでない要素との境界を ステージごとに形成し、それよりも左側に出現した シンボル単体の要素の数から、各シンボルの符号長を求めるこのアルゴリズムを
境界 package-merge (Boundary package-merge) と呼ぶことにする。
生成手順
各々のステージは それぞれ以下の情報を保有する
- 要素1 (先読みチェーン)
- 要素2 (先読みチェーン)
また、各要素は以下の情報を保有する
- 重み
- シンボルカウンタ
- 要素への参照
このうち "要素への参照" は、自身の要素が作成されたときに、一つ上のステージで、一番最後にパッケージを作成する元として使われていた要素を覚えておくために利用される。以降はこの参照を チェーン と呼ぶことにする
境界 package-mergeを使った符号表の生成手順を以下に示す
１. シンボルリストをソート
[シンボル,重み] のリストを、あらかじめ重みの昇順になるように並べ替えておく
２. ステージの初期化
一番下のステージを除いて、各ステージ上の先読みチェーン 2つを、重みの昇順に並んだ [シンボル,重み] リストの上二つの要素で初期化する。
うち、先読みチェーンの右側 (重みの大きいほう) の要素は、
- シンボルカウンタ ⇒ ２
- チェーン ⇒ なし
の状態でそれぞれ設定しておく。
なお、一番初めの先読みチェーンの左側 (重みの小さいほう) の要素については、重み以外の情報を扱うことがないため、重み以外はテキトウな設定にしておいて構わない。
３. 要素を作成
これから、最下段ステージに要素を作成する次の手順を、 回だけ繰り返す
[シンボル,重み] のリストから次に読み出せる要素の重みと、自身の一つ上の先読みチェーン2つの重みの合計のどちらが小さいかを比較する。
リストの要素の重みのほうが小さければ 3.1 の処理、そうではない場合、またはシンボルのリストから読み出せる要素がもうない場合は 3.2 の処理へ進む
3.1 [シンボル,重み] リストの要素を追加
[シンボル,重み] のリストから読み出した要素を自身のステージに追加する
要素のシンボルカウンタには、ここまでに同じステージ上で [シンボル,重み] のリストからシンボルを読んだ回数の値を設定する
要素のチェーンは、自身の一つ前の要素がチェーンを持っていれば、そのチェーンをそのまま引き継ぐ
遅延 package-merge の時と同様、１番目、２番目に追加される要素は必ず、[シンボル,重み] のリストの１番目、２番目の要素になるため、２. ステージの初期化 で各ステージを初期化する際に、この要素２つをあらかじめ 最下段ステージに作成しておいてもかまわない。
3.2 先読みチェーンのパッケージを追加
一つ上のステージの先読みチェーン2つからパッケージを作成し、自身のステージへ追加する。
要素のシンボルカウンタは、自身の一つ前の要素のシンボルカウンタの値を引き継ぐ
要素のチェーンには、パッケージ作成元の先読みチェーン２つのうち、右側 (重みの大きいほう) の要素の参照を設定する。
この後は、遅延 package-merge の時と同様。3.要素を作成 の手順を、更新が必要な先読みチェーンすべてに、新しい要素が補填されきれるまで繰り返す。
４. 符号長を抽出
最下段のステージに 回、要素を作成する手続きを行ったあと、
番目に作成される要素が、最下段のステージの 境界の要素 になる。
また、その要素がチェーンを持っていれば、そのチェーン先の要素が 一段上のステージの境界の要素となり、それがまたチェーンを持っていれば、そのチェーン先の要素が さらに一段上のステージの境界の要素となる。
それぞれの境界の要素が持つ "シンボルカウンタ" には、自身を含めて 自身の左側に出現したシンボル単体の要素の数を保有するため、この数から 前述した方法で、各シンボルの符号長を求めることができる。
各シンボルの符号長が求まれば、あとは package-merge algorithm と時と同様、カノニカル・ハフマン符号化の手順を利用して符号表を作成できる
利点
境界の要素 よりも左側にある各ステージ上の要素は、それが作成されても、以降扱われることはない。最下段ステージに の要素を作成する過程で、境界の要素が更新されるたびに、それよりも左側にある要素のメモリ空間は、ほかの要素を作成するために使いまわすことができる。
この通り、境界 package-merge でも 要素に使ったメモリ空間の再利用が行える。
遅延 package-merge との違いは、プールにあらかじめ確保しておくべき "空き要素" の数が であるということ。 遅延 package-mergeの
よりも、その数が少なくなることを期待できる
※Deflateのカスタムハフマン符号 (シンボル数=286, 制限符号長
=15) の場合を例とするならば、遅延 package-merge を利用したとき、最大で
4,290 の空き要素が必要であるのに対し、境界パッケージマージを利用した時は、最大でも
240 の空き要素だけ用意すれば事足りる。
遅延 package-merge のパッケージ要素が持つ要素への参照が2つであるのに対し、境界 package-merge の要素が持つ要素への参照 (チェーン) は１つだけ
これによって、要素の利用がピークになるとき、同時に生存していないといけない要素の 全体的な数を減らすことができるため、遅延 package-merge と比べて、はじめに準備しておくべき空き要素の数をその分だけ抑えられる
サンプル
ここまでのサンプルプログラム。VC2015でのみ動作確認済み。
参考にしたサイトさん
Package-merge algorithm - Wikipedia
sfnt2woff-zopfli/katajainen.c at master · bramstein/sfnt2woff-zopfli · GitHub
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圧縮)処理の概要 - ウェブで用いられる画像形式。
PNG イメージを自力でパースしてみる ～1/6 予備知識編～
DirectX12でなにか作りたいと思って、じゃあとりあえず、まずはその辺のサンプルを読み漁ろうと、上のサイトさんからサンプルプログラムを拝借していろいろ見ていたとき、
"HelloTexture"
テクスチャを画面に表示させるサンプルを見つけて、たぶんここで画像ファイルをロードする機能とか、紹介してるんじゃないかな.. と思ってたのだけど、どうやら違った。
HelloTextureサンプルのテクスチャ元の画像ファイルが見つからない..?
— ﾛｳﾞｽﾀﾝｸﾞ=ﾊﾟｼﾌｨｹｲﾅｽ (@DarkCrowCorvus) 2016年6月4日
もしかしてソース内で動的に作ってる..?
代わりにテキトウなイメージを実行中に作っていた様子。画像ファイルをロードするためには、自身でそのまわり、なにかしらの準備をしないといけないみたい。
どこかのライブラリを拝借してきてもよかったものの、自身の勉強になるかと思い、じゃあ自作しましょうと、
自身が比較的よく使ってたフォーマットがPNGだから、じゃあPNGのパーサーを作ってみようかなと―――..
ということで、タイトルの通りに至る。
泥沼のはじまり
でふれーと圧縮とは。。。
— ﾛｳﾞｽﾀﾝｸﾞ=ﾊﾟｼﾌｨｹｲﾅｽ(@DarkCrowCorvus) 2016年6月19日
解説してるサイトさんとか探せばすぐに終わるかな...
なんて思ってたけど、そうも甘くなかった。 PNGが圧縮を使用していて..ということまでは知っていたものの 、実際にその正体が何でどんな圧縮方法なのかまでは知らない。
C++の標準で ”デフレート” なんて機能は提供されていない様子。後で調べたら linuxだとそれに相当するライブラリがデフォルトで使えるらしい、ただ自分のPCはwinだしなぁ..
ないなら作ればいいじゃない
いや...標準とか、デフォルトで提供されていないだけで、
google先生を使えば、そこらへんにライブラリが転がってたりはするのだけど...
中途半端に他人のライブラリを使いたくないだとかなんだとか...いつもの自前主義精神(？) がはたらいてしまって、結局自身で作ってみるに至る。
じゃあとりあえず ”デフレート” に関して調べてみる。よく見た回答は、wiki先生から言葉を拝借すると次の通り
Deflate（デフレート）とはLZ77とハフマン符号化を組み合わせた可逆データ圧縮アルゴリズム。
"可逆圧縮" なら知ってる、でもそのほかがよくわからない。"ハフマン符号化" は言葉だけ、どこかで聞いたことあるなぁ...ってレベル。
まずはその辺、調べてみるところから始めた。
調べたことを自分なりに整理して、以下に書き並べてみる。
以上。前置き終わり。
ハフマン符号化
データ圧縮アルゴリズムの一つ。
ハフマン符号化では、圧縮したいデータに含まれている各々の文字を、それぞれ別の ビット並び に置き換える、ということを行う
以降、この置き換えたビット並びのことを 符号 とよぶ。
この符号化のとき 元のデータの中で出現回数の多い文字にほど
短い符号を割り当てることで、全体的なデータサイズを減らそう
というのがハフマン符号化の基本的な圧縮の仕組み
同じ考え方の圧縮方法は、これ以外にもいくつかの種類があるのだけれど、ハフマン符号化はその中でも、符号化後のデータに含まれる符号の長さの平均が最小になるのだとか。
ハフマン符号化によって割り当てられた符号は、そのビット並びが、他のどの符号の頭の部分とも一致しないという特性を持つ。
この特性のことを 語頭条件 とよび、
語頭条件の特性を持つ符号は 接頭符号(Prefix code) とよばれる。
この通りに符号化することで、元のデータに戻すとき、その符号と同じビット並びが読み出せれば、それより後ろのビット並びに依存することなく、元の文字へ一意に復号することができるようになる。
この特性は 瞬時復号可能 と呼ばれる。
ハフマン符号は 接頭符号 であり、瞬時復号可能 な特性を持つ。
ただ単純に短い符号を割り当てればいい、っていうわけではないみたい。
カノニカル・ハフマン符号化（ハフマン符号の正規化）
ハフマン符号化でデータサイズを小さくできても、元の文字との対応がわからなければ、送った先でデータを復元することができない。
そのため圧縮したデータに、符号表を埋め込む必要があるのだけど、ここでの 符号 という存在が わりと厄介。
符号 はそれと対応する文字ごとに、長さの異なる ”可変長” なデータなのだけれど、データを復元する側では、各々の 符号 の情報を抽出するとき、何ビット分だけデータを読めばいいのか、わかっていないといけない。
パッと思いつく方法は 例えば上の通り、いっしょに 符号の長さ情報を持たせるなど。ただし、長さの情報を含むことによって、符号表全体のサイズが膨らんでしまう。
また、符号自体のサイズが大きくなりうる、というのも問題。
0x00 ～ 0xFF まで 256種類すべての文字に符号を割り当てる場合、一番長い符号は、最悪で255ビットにもなる（圧縮しないままの文字32コ分ぐらい）
※ここでは本来、アルファベットなどの文字として表すことのできない バイナリデータ中の8ビット並びも "文字" として扱うことにする。
そんなに大きな符号が生成されることはめったにないらしいのだけれど、万が一、そんな符号があると、符号表はその分だけ大きくなる、
符号表のサイズが膨らむと、それだけ全体のサイズも膨らんでしまうため、
符号化したら、前よりもデータサイズが増えたんだけど！？
なんてことが起こりうる。
こんなことじゃハフマン符号化を利用する意味がなくなってしまう。データの圧縮効果を上げるためには、この符号表をできる限り小さく保つ必要がある。
そこで カノニカル・ハフマン という手法を利用する。
これを利用すると、符号表のサイズを小さくするうえで悩みの種である 符号 を、
そのまま符号表の中に納めなくても済むようになる。
代わりに符号表には、各文字に対応する符号の 長さの情報だけ を納める。
カノニカル・ハフマン符号化 による 符号化の手順は以下の通り。
- 一度ふつうにハフマン符号化された符号を、
符号の長さ別 にグループ分けして、
そのグループ内で 文字番号の昇順 になるように並べる - 符号の長さが短く、文字番号の小さい文字ほど、
小さな符号になるように符号を割り当てなおす - 割り当てなおした符号表を使ってデータを符号化（圧縮）
- 符号の長さだけを納めた表を、符号化したデータの前に付加する
ポイントは、ある符号長グループへの 符号の再割り当てが終わって、次の符号長のグループに移るとき。
ひとつ前の符号長グループで一番最後に割り当てた符号に +1 したあと、その後ろに 0 ビットを付加したものを、次の符号長グループの再割り当てに利用する、ということ
この通りにすることで、再割り当てされた符号は 接頭符号 になり、瞬時復号可能な特性を持つようになる。
一方で、復号の手順は以下の通り。
- 符号の長さ表を読み出した後、
それを 符号の長さ別 にグループ分けして、
そのグループ内で 文字番号の昇順 になるように並べる - 符号の長さが短く、文字番号の小さい文字ほど、
小さな符号になるように符号を割り当て、符号表を復元する - 得られた符号表を使ってデータを復号する
LZ77符号化
データ圧縮アルゴリズムの一つ
Lempel さんと Ziv さんが 1977年に作ったからこんな名前
データ中の ある文字列が、それよりも以前に同じ形で現れているならば、文字列をその "位置" と "一致した長さ" という情報に置き換えてしまうことで、全体的なデータサイズを減らそう、というのが LZ77の大まかな圧縮の仕組み
"位置" と "一致した長さ" に置き換えるために、”以前に同じ形があるか” を検索できる範囲は有限で、直前に読みだせた文字から、何文字前まで...というのが事前に決められている。
これは 検索にかかる時間や 使用メモリ量、置換後の "位置" を表す数値が、巨大になり過ぎないように制限するため。
たとえばDeflateなら、直前に読み出した文字から、最大で 32,768文字前までが検索範囲。
新しい文字を読み出すたびに、検索できる範囲がスライドするため、この範囲のことを スライド窓(Sliding Window) と呼んだりする。
LZ77では、圧縮対象のデータを 先頭から順番に読み込み、
そのときに現れた文字、または文字列を
（位置 , 一致した長さ , 直近の不一致文字）
というフォーマットに置き換えることでデータの圧縮を行う。
圧縮元のデータが大きいほど、スライド窓の中に同じ文字列があるという機会が増えるため、圧縮効率が良くなるのだけれど、
上の例だと、対象のデータが短すぎるせいか、逆にサイズが増えてしまってる。
なんてこというと、ハフマン符号の時に提示した例も、圧縮後のデータに符号表を含めると、元のデータよりもサイズが大きくなってしまうのだけれど...
LZ77では何が何でも（位置, 一致した長さ, 直近の不一致文字）というフォーマットへ置き換えようとするため、スライド窓に同じ文字列が見つからなかった場合は、むしろ置換前よりもデータが大きくなってしまう という欠点がある。
LZ77には、それを基本形とするさまざまな亜種が存在する。
LZSS符号化
データ圧縮アルゴリズムでLZ77の亜種のうちの一つ。
StorerさんとSzymanskiさんが改良を行ったからこんな名前。
現在 普及している圧縮プログラムで LZ77 符号と呼ばれているもののほとんどは、じつは LZSS 符号になっている。とのこと ※1
実際、”LZ77を利用している” と言っていたDeflateも、その実装は、どちらかといえばLZSSのものに近い。
LZSS ではスライド窓の中を検索して、同じ文字列が存在し、さらに置換することで圧縮効果が得られる場合に限ってそれを "位置" と "一致した長さ" の情報に置き換る。それ以外の場合は置き換えを行わない。
この通りに作られた圧縮データは、復号のとき先頭から順番に読み出されたそれが "位置"と"一致した長さ" を表すのか、置換されなかった文字そのままを表すのかを判断できなければ、データを正しく復元することができない。
これの解決には、記録する各々の要素の先頭に 1ビットを付加する、という方法を用いる。
これによって 復号時には、各々の要素ごとに先頭の 1ビットを読んで、
それが "1" ならばその直後に続くデータは "位置" と "一致した長さ"
"0" ならば1文字そのまま..という具合に識別することができる。
識別のため、各々の要素に それぞれ 1ビットずつ付与されるため、"位置" と ”一致した長さ” の情報に 置換が行われなかった文字は、圧縮前よりも 1ビット分だけ大きくなるのだけれど、
それでもLZ77と比べると、スライド窓に同じ文字列が見つからなかったときにデータが膨らんでしまう規模を、だいぶん抑えることができる。
参考にしたサイトさん
全般
ハフマン符号
データ圧縮の基礎『ハフマン符号化』の仕組みを見てみよう - 道すがら講堂
圧縮アルゴリズム (3) ハフマン符号化 - 静的ハフマン圧縮
瞬時復号可能な符号 — Computer Science Textbook (under construction)
カノニカル・ハフマン符号化
圧縮アルゴリズム (4) ハフマン符号化 - 適応型ハフマン圧縮
Canonical Huffman code - Wikipedia, the free encyclopedia
LZ77
デフレート圧縮(LZ77圧縮)処理の概要 - ウェブで用いられる画像形式。
Data Compression/data differencing - Wikibooks, open books for an open world
LZSS
