2017-01-09

PNG イメージを自力でパースしてみる～4/6 非圧縮とzlib編～

PNG

ここまでのあらすじ

PNG イメージを自力でパースしてみる～1/6 予備知識編～
PNG イメージを自力でパースしてみる～2/6 Deflateの基本と固定ハフマン編～
PNG イメージを自力でパースしてみる～3/6 カスタムハフマン編～

前回、前々回でDeflateの「固定ハフマン」と「カスタムハフマン」について触れた。ここでは残るブロックタイプの「非圧縮」と、Deflateを利用した圧縮フォーマットの「zlib」についてを紹介。

予備知識
- バイトオーダー
  - リトルエンディアン
  - ビッグエンディアン
非圧縮 (BTYPE:00)
zlib
サンプル
参考にしたサイトさん

予備知識

これからの説明を読む前に予備知識が必要かも

バイトオーダー

あたりまえとは存ずるものの...
１バイト (8ビット) 単体では、256種類までの数値を表現できる。それより広い範囲の数値を扱いたい場合には、一般的に連続した複数のバイト並びを利用することで、それを実現する

ここで、表現したい値をその連続したバイト並びに対して、
どのような順で収めるのかを、ルールとして定めたものを
バイトオーダー または エンディアン と呼ぶ。

うち、実際によく利用されるのは以下の２つ

リトルエンディアン

0x1234ABCD (305,441,741)
0x12	0x34	0xAB	0xCD
↓	↓	↓	↓
0xCD	0xAB	0x34	0x12

この並びの規則に従う場合、数値の下位バイトほど、先頭に出現するよう収められる。

Deflate 圧縮データ中に含まれる多バイト長データは、このリトルエンディアンの並びの規則に従って出現する。

ビッグエンディアン

0x1234ABCD (305,441,741)
0x12	0x34	0xAB	0xCD
↓	↓	↓	↓
0x12	0x34	0xAB	0xCD

ネットワークバイトオーダーとも呼ばれる。
この並びの規則に従う場合、数値の上位バイトほど、先頭に出現するよう収められる。

後に解説する zlibデータ中に含まれる多バイト長のデータは、このビッグエンディアンの並びの規則に従って出現する。

非圧縮 (BTYPE:00)

Deflate で定義されている圧縮タイプのうちの一つ。

このブロックに含まれるデータは圧縮されない。圧縮がむしろ逆効果になってしまうような小さなデータに対しては、このタイプを使う。

非圧縮ブロック中には、以下の要素が順番に整列している。

ヘッダー情報 (前々回の記事で紹介済み)
パディング
LEN：非圧縮データのバイト数 (2バイト)
NLEN：LENの補数 (2バイト)
非圧縮データ (～65,535バイト?)

f:id:DarkCrowCorvus:20170108132252j:plain

2. パディング

メモリ上に展開されたとき、LENより以降のデータは、必ずバイト境界から始まるようになっている。パディングは、ヘッダー情報 (BFINAL、BTYPE) を読み出してから、それより後に現れる直近のバイト境界位置までの間に詰められる。

このデータにそれ以上の役割はないので、読み飛ばすか、読んでそのまま捨ててしまって構わない。

3. LEN：非圧縮データのバイト数

このブロックに含まれている非圧縮データの、バイト数を表す値がこの中に収められる。最大で 65,535 (0xffff) まで設定可能。

このデータはリトルエンディアンの並びで記録されている

4. NLEN：LENの補数

ここには LENの全ビットの0,1を反転した"補数"の値が設定される。

データが壊れていないかをチェックするためのものなんだろうか...?

NLENの全ビットの0,1を反転させたものが LENと一致するか、
LEN + NLEN = 0xffff になるか、

一応、このどちらかで、バイト長の値に誤りがないかをチェックできる。

このデータもリトルエンディアンの並びで記録されている

5. 非圧縮データ

ここに非圧縮状態のデータがそのまま収められる。データサイズはLENに設定されている通り。

zlib

あぁ、なんかうまくいかないと思った... pngのIDATの中身って、Deflate圧縮のデータがそんまま入ってるわけじゃないのか、zlibのヘッダとフッタを取り除かなければならぬ、
— ﾛｳﾞｽﾀﾝｸﾞ=ﾊﾟｼﾌｨｹｲﾅｽ (@DarkCrowCorvus) 2016年7月9日

PNGの圧縮データ部には、Deflateではなく、zlib というのを使っているそうだった。ここにきてようやく気付く。

実際にはそのzlibの中で、Deflateが扱われているので、「PNGはDeflate圧縮を使っている」といっても、あながち間違いではないとは思うのだけど...

構成

zlib 中には以下の要素が順番に整列している

CMF (Compression Method and flags)
1.1. CM：圧縮方式 (4ビット)
1.2. CINFO ：圧縮情報 (4ビット)
FLG (FLaGs)
2.1. FCHECK：CMF/FLGチェックビット (5ビット)
2.2. FDICT：プリセット辞書の利用有無 (1ビット)
2.3. FLEVEL：このデータの圧縮レベル (2ビット)
DICTID：プリセット辞書識別ID (存在しない場合あり 4バイト)
圧縮データ
Adler-32 (4バイト)

f:id:DarkCrowCorvus:20170109143630j:plain

なお、データ中の各々の要素はDeflateと同様、
アドレスの小さい順のビット番号の小さい順に並ぶ。

また、前述していたとおり、圧縮データ部を除く、zlib中の多バイトで表現される数値はすべてビッグエンディアンの並びで記録されているということに注意すること。

1.1. CM：圧縮方式
CM：Compression method

ここには、zlibがどの圧縮方式を利用しているかの情報が 4ビット長で収められる。
CM = 8 だった場合、それがDeflate圧縮を利用したzlibであるということを示す。

なお、CM = 8 以外の値は、現状扱われていない。とりあえず今は「8を読み出せれば正しい」とだけ覚えておけば問題ないはず..

1.2. CINFO：圧縮情報
CINFO：Compression info

CM = 8 のとき、ここには Deflate 圧縮で使用したスライド窓のサイズを表す値が設定される。

実際にはスライド窓のサイズを $n$ としたとき、
$log_2(n)-8$ によって求まる値を、この 4ビット長の中に収める。

なお、ここに設定できる値は 0～7 の値のうちいずれかで、利用できるスライド窓のサイズは最小で256バイト、最大で32,768バイトというのが決められている。

ちなみに、符号化時にどのサイズのスライド窓を利用したとしても、復号時には最大サイズ (32,768) のスライド窓が用意できれば困ることはない。細かな実装が面倒なら CINFO ≤ 7 であるかだけをチェックすれば、後は考慮しなくてもかまわない。

2.1. FCHECK：CMF/FLGチェックビット
FCHECK：Flag check bits?

1. CMF と 2. FRG を連結した計16ビット長からなるデータの表す値が、31の倍数になるよう、調節するために設定される。復号するとき、この結果が31の倍数にならない場合は、データが壊れていることを示唆する。

2.2. FDICT：プリセット辞書の利用有無
FDICT：Flag dictionaly?

このビットに「1」が設定されている場合は、プリセット辞書 (後述) を利用して解凍を行うべきであることを示す。またこれが「1」に設定されている場合は、後に 3. DICTID が出現する。

2.3. FLEVEL：このデータの圧縮レベル
FLEVEL：Flag level?

データの圧縮がどの程度の精度で行われたかを表す値が、2ビット長で収められる。
CM = 8 の場合、以下のいずれかの値が設定される。

０ - 最速のアルゴリズムを使った
１ - 速めのアルゴリズムを使った
２ - デフォルトのアルゴリズムを使った
３ - 最遅だが、最大限に圧縮するアルゴリズムを使った

基本的に圧縮アルゴリズムは、圧縮が完了するまでの速さを重視すると圧縮率が落ち、逆に圧縮率を重視すると、圧縮が完了するまでに時間がかかる。

ここに設定される値は例えば、あるzlibのデータの圧縮率を上げるために、そのデータへの再圧縮を試みたいとき、それの結果、圧縮率が上がるかどうかを評価するための指標となる。

ちなみにデータを解凍する上でこのデータは役に立たないため、読み飛ばしてしまっても構わない。

3. DICTID：プリセット辞書識別ID
DICTID：Dictionaly identifier

前述の FDICT に「1」が設定されている場合に限り、4バイトの長さで出現する。

ここには、プリセット辞書 (後述) に対してAdler-32 (後述) を施した結果、得られた値が設定される。解凍するプログラムはこれを見て、圧縮に使われたプリセット辞書を、自身が持っているかをチェックする。

4. 圧縮データ

CM = 8 であるとき、ここには Deflate 圧縮されたデータが収められる。解凍方法は、これまでの記事で紹介してきた通りだ。

プリセット辞書

LZ77 はその仕様により、圧縮のはじめはスライド窓の中身が空の状態である。そのため通常は、圧縮元のデータが小さかったり、または大きくても、はじめのほうに出現する羅列の圧縮には、あまり期待ができない。

しかし、特定のアプリケーションにおいて、どのような羅列が出現しやすいか事前にわかっていたならば、あらかじめその羅列をスライド窓にセットしておけば、それらのデータを圧縮できる機会が生まれ、結果的に全体的なデータサイズを減らすことができそうだ。

この通り、圧縮前に事前にスライド窓へ渡されるこの羅列のことを プリセット辞書 (Preset dictionary) と呼ぶ。

f:id:DarkCrowCorvus:20170108215754j:plain

zlibの圧縮プログラムと解凍プログラムはそれぞれ、自身のアプリケーションに合った任意の数のプリセット辞書を保有する。

圧縮時にプリセット辞書を使ったならば、FDICTに「１」を設定し、DICTIDに使ったプリセット辞書を識別するためのIDを設定する。通常ここには、プリセット辞書に対して、後述のAdler-32を施した結果の値を使用する。

解凍時には、FDICTを見て「１」であるならば、後に現れるDICTIDから、使われたプリセット辞書を特定し、そのプリセット辞書を使って解凍を行う。

Adler-32

任意のデータ列を「数値の並び」であるとみなしてこれの和を求め、結果をデータ列の末尾などに付与する。そのデータを受け取った側では同じ通り、データ列から和を求め、付与されていた和の値と一致するかをチェックする

これによって受け取るまでの途中でデータが壊れたりしていないかを、簡易的にチェックすることができる。

この考え方をベースとしたアルゴリズム、またはそれにより求まるチェック用の値のことを チェックサム (check sum) と呼ぶ。Adler-32 はそのチェックサムアルゴリズムの一種。 Mark Adlerさんが考案した

Adler-32は 2つの和の値 s1(2バイト)、s2(2バイト) からなる。
s1 は最初に「1」で初期化され、データ列の各値を先頭から順番に加算した結果を保持する。
s2 は最初に「0」で初期化され、s1にデータ列の値が加算されるたびに、そのs1の値を自身に加算した結果を保持する。

また双方ともに、加算されるたびに 65,521 との剰余によって上書きされ、計算の途中で桁あふれが起こらないようにされる。

結果的に求まる s1、s2を [s2, s1] の順番に連結することで、本来のAdler-32によるチェックサムが求まる。

zlibの解凍においては、4. 圧縮データ部を使って、Adler-32 チェックサムを算出する。その直後に現れる、圧縮データに含まれる 5. Adler-32 のチェックサムと比較し、値が一致していれば、"圧縮データが壊れていない" ということを確認することができる。

サンプル

ここまでのサンプルプログラム
VC2015でのみ動作確認済み。

残念ながらプリセット辞書には対応できてない。

参考にしたサイトさん

RFC 1950 ZLIB Compressed Data Format Specification version 3.3 日本語訳 - futomi's CGI Cafe

RFC 1951 DEFLATE Compressed Data Format Specification version 1.3 日本語訳 - futomi's CGI Cafe

SWFバイナリ編集のススメ番外編 (zlib 伸張) 前編 | GREE Engineers' Blog

Improving compression with a preset DEFLATE dictionary

Adler-32 - Wikipedia

2017-01-07

PNG イメージを自力でパースしてみる～3/6 カスタムハフマン編～

PNG

ここまでのあらすじ

PNG イメージを自力でパースしてみる～1/6 予備知識編～
PNG イメージを自力でパースしてみる～2/6 Deflateの基本と固定ハフマン編～

ここでは Deflateのカスタムハフマンについてを解説

カスタムハフマン符号化 (BTYPE:10)
- 圧縮
- 解凍
サンプル
参考にしたサイトさん

カスタムハフマン符号化 (BTYPE:10)

Deflate で定義されている圧縮タイプのうちの一つ

個人的にここのブロックの圧縮ルールが結構ややこしかった。
まずはどんなふうに圧縮されているかを見てから復号の解説を行いたいと思う

圧縮

カスタムハフマンのブロックは、以下の手順で作成される (たぶん)

Deflateの LZ77 でデータ圧縮
カノニカル・ハフマン符号化
符号長表を符号化
配置

符号長表を符号化とかいうパッと見なんかよくわからないことをしていらっしゃるけど、まずは一番上から順を追って解説してみる

1. Deflateの LZ77 でデータ圧縮

Deflate仕様の LZ77 で元データを圧縮する。
実際の圧縮方法については、これのひとつ前の記事で解説した

この結果、"文字" または "一致した長さ" (それと終端符号) は 0 ～ 285 (+拡張ビット)
"距離" は 0 ～ 29 (+拡張ビット) のかたちになって出力される

f:id:DarkCrowCorvus:20170105224856j:plain

2. カノニカル・ハフマン符号化

LZ77で置換された各値の出現回数を調べる
各値に対する符号の長さを求め、符号長表を作成する
得られた符号長表から、カノニカル・ハフマンを使って符号表を作成する。
得られた符号表を使って、LZ77符号化されたデータをさらに符号化する

カノニカル・ハフマンについては、これのふたつ前の記事で解説した。これによって、圧縮後のデータに符号長表だけを収めれば、符号表と元データを間違いなく復元できる。

符号の長さを求めるときにひとつ注意するべきことがある。Deflateのカスタムハフマンで扱うハフマン符号は、仕様によりその符号長が 15 以下にならなければならない

一応、長さの制限されたハフマン符号を作成する方法がきちんとあるらしい。長くなるためこっちの記事で解説することにする

なお、文字/一致した長さの値 (0～285) の出現回数と、距離の値 (0～29) の出現回数の 2つは、それぞれ別々に統計され、それぞれ別々の符号表として作成される。

また、LZ77符号化されたデータは、その中に現れる値が文字/一致した長さの値か、距離の値かによって、その都度2つの異なる符号表を使って符号化される。

f:id:DarkCrowCorvus:20170105224953j:plain

3. 符号長表を符号化

直前の手続きによって得られた 2つの符号長表は、表中の "符号長" を表す値の偏り具合によって、それ自体、一度ハフマン符号化される

まず、2つの符号長表は、値の昇順に連続して連なるリスト構造に展開されているものとする。このうち、本来出現しない値に対しては符号長：0 が充てられる。

f:id:DarkCrowCorvus:20170106201614j:plain

符号長表中の圧縮データ化される範囲は「可変」である。

文字/一致した長さの符号長表 の場合、利用されている一番大きな一致した長さの値に合わせて、0から最小で256(257個)、最大で285(286個) までの範囲の符号長を対象とする。

距離の符号長表 については、最小で0のみ(1個)、最大で0～31(32個) までの範囲の符号長を対象とする。こちらも利用されている距離の最大値によって、圧縮データ中に含める範囲が変化する。

この2つの表中の圧縮範囲に対しては、次の２つの圧縮が施される

3.1 ランレングス符号化

表中の符号長の値を連ねたとき、同じ値が連続する箇所があれば、それをいくつ連続したかを表す数のデータに置き換えることで圧縮を行う。
このアプローチは通常、ランレングス符号化 と呼ばれる

Deflate仕様のランレングス符号化では、符号長表の圧縮範囲の値が連続する場所に対して、以下の通りに置き換えを行うものとしている

・ひとつ前に出現した値が 3 ～ 6 回繰り返される	16 ( 拡張ビット：2 )
・"０" が 3 ～10 回繰り返される	17 ( 拡張ビット：3 )
・"０" が 11 ～ 138 回繰り返される	18 ( 拡張ビット：7 )

f:id:DarkCrowCorvus:20170107163645j:plain

拡張ビットには、"どれだけ連続するか" を調整する値が設定され、
ベース値 + 拡張ビットによって本来の連続した長さを求められるようになっている

3.2 カノニカル・ハフマン符号化

ランレングス符号化が終わった2つの符号長表に対して、その表中の値の出現回数を調べ、符号長表を作成し、それから符号表を作成し、それから符号化を行う。

f:id:DarkCrowCorvus:20170107163725j:plain

値の出現回数は、表2つを合わせて集計される。

各値の出現回数が分かれば、次にその各値に対する符号長を求める。
ここでも求める符号長の、その長さに注意すること。LZ77符号化済みデータに対する符号長制限が 15以下だったのに対し、こちらでは 7以下になっていなければならない

得られた各値に対する符号長から 符号長表の符号長表 を作成すれば、あとはそれから、符号表を作成し、2つの符号長表を圧縮する。

f:id:DarkCrowCorvus:20170107163737j:plain

ここまでの手続きで、ひとまずカスタムハフマンブロックに含む各データの符号化が完了する

4. 配置

最終的にカスタムハフマンブロック中には、以下の要素が順番に整列することになる

ヘッダー情報 (前回の記事で紹介済み)
HLIT：文字/一致長符号の個数 (５ビット)
HDIST：距離符号の個数 (５ビット)
HCLEN：符号長表の符号長表のサイズ (４ビット)
符号長表の符号長表
符号化された文字/一致長の符号長表
符号化された距離の符号長表
圧縮データ

2. HLIT：文字/一致長符号の個数
HLIT ...header literalの略？

ここには、文字/一致長の符号長表に含めた符号長の個数 (257 ～ 286) を表す値が設定される。実際には個数 -257 した 0 ～ 29 までの範囲の値が５ビット長の中に収められる

3. HDIST：距離符号の個数
HDIST ...header distanceの略？

ここには、距離符号長表に含めた符号長の個数 (1 ～ 32) を表す値が設定される。実際には個数 -1 した 0 ～ 31 までの範囲の値が５ビット長の中に収められる

4. HCLEN：符号長表の符号長表のサイズ
HCLEN ...header code lengthの略？

ここにはカスタムハフマンブロックに収められる符号長表の符号長表に、符号長がいくつ含まれているか (～19) を表す値が設定される。実際には個数 -4 した 0 ～ 15 までの範囲の値が４ビット長の中に収められる

5. 符号長表の符号長表

符号長表の符号長表は、カスタムハフマンブロックに対して、以下のような変則的な並びになった状態で記録される。

各符号長値 (0～7) は、それぞれ３ビット長の中に収められる。
また、このうち本来出現しない値に対しては、符号長：０が充てられる

この並びの中に各符号長を収めた時、最後尾「15」の符号長が０で、なおかつそこから先頭方向に連続して０が続く場合、カスタムハフマンブロックに並びを収めるとき、その０が続く部分を省略することができる。

ただし省略できる符号長は15個まで。
並びの中の符号長の個数は 4未満にはならない

f:id:DarkCrowCorvus:20170107144210j:plain

この結果、並びの中に残った符号長の個数 -4 した値が、
前述の HCLEN に実際に設定される数になる。

それ以降にようやく

6. 符号化された文字/一致長の符号長表
7. 符号化された距離の符号長表
8. 圧縮データ

のデータが順番に現れるようになっている

解凍

上で説明した構築の手順を逆にたどれば、カスタムハフマンブロックの解凍が行える

ヘッダー情報を読み出す(前回の記事で紹介済み)
HLIT (5ビット) 、HDIST (5ビット) 、HCLEN (4ビット) をそれぞれ読み出す。
HCLEN + 4 によって並びの中の符号長の数がわかれば、後に続く符号長(3ビット) をその数だけ読み出し、本来の符号長表の符号長表を復元する
符号長表の符号長表から、符号長表の符号表を作成する。
HLIT + 257 によって、このブロックに含まれている文字/一致長の符号長値の数がわかれば、先ほど作成した符号長表の符号表を使って、その数だけの符号長を読み出して復号し、本来の文字/一致長の符号長表を復元する
HDIST + 1 によって、このブロックに含まれている距離の符号長値の数がわかれば、同じく符号長表の符号表を使って、その数だけの符号長を読み出して復号し、本来の距離の符号長表を復元する
復元した2つの符号長表から文字/一致長の符号表と、距離の符号表をそれぞれ作成する
作成した2つの符号表を使って、残りの圧縮データを読み出して復号する

なお、HLIT、HDIST、HCLEN、符号長表の符号長表、拡張ビットは "値のデータ" なので、読み出すときにはその値がそれぞれ、最下位ビットから順番にパックされたビット並びになっていることに注意すること。

サンプル

ここまでのサンプルプログラム
VC2015でのみ動作確認済み。

参考にしたサイトさん

RFC 1951 DEFLATE Compressed Data Format Specification version 1.3 日本語訳 - futomi's CGI Cafe

カスタムハフマン符号 - 七誌の開発日記（旧）

デフレート圧縮(LZ77圧縮)処理の概要 - ウェブで用いられる画像形式。

2017-01-04

package-merge algorithmを勉強してみる

最大符号長の制限されたハフマン符号表を生成する方法として package-merge algorithm っていうのがあるらしい。気が向いたのでちょっと調べてみる

今回は以下の資料さんを参考にさせていただいた

"A Fast and Space-Economical Algorithm for Length-Limited Coding Jyrki Katajainen, Alistair Moffat, Andrew Turpin".

自身の理解できた範囲でそれぞれ順番に紹介してみる

package-merge algorithm
- 生成手順
遅延 package-merge
- 生成手順
- 利点
境界 package-merge
- 生成手順
- 利点
サンプル
参考にしたサイトさん

package-merge algorithm

前述のとおり package-merge algorithm は、最大符号長の制限されたハフマン符号表を生成するために利用できる

ただし、符号表中の符号をある長さまでに制限するためには、
符号表を生成する元として使う、シンボルの種類の数に制限がかかる

たとえば最大符号長を「2」に制限して符号表を作成した場合、
その中で同時に定義ができる接頭符号の種類は、多くて4つまで

最大符号長を「3」に制限した場合では、
その中で同時に定義できる接頭符号の種類は、多くて8つまでになる

000

001

010

011

100

101

110

111

この通り、最大符号長を $L$ と定義した時、
表現できる符号の種類の最大は、 $2^L$ のように表すことができる

シンボルの種類の数を $n$ とするとき、

$n ≤ 2^L$

を満たさなければ、最大符号長を L に制限した中で、それぞれのシンボルに対して、きちんと接頭符号を割り当てることができない。

package-merge algorithm は上の制約を満たす各々のシンボルに対して、指定した符号長以下になるよう符号を割り当てて、符号表を作成するのを手助けしてくれるアルゴリズムである。

生成手順

はじめに断っておくと、package-merge algorithm 単体ではハフマン符号を生成することはできない

package-merge algorithm が出力できるのは、各々のシンボルを符号化したときの符号長までにとどまる

そこから実際に符号を割り当てて、符号表を求めるには、 カノニカル・ハフマン符号化 を利用する。カノニカル・ハフマン符号化については、以前別の記事で紹介した

符号化対象のデータに含まれる、各々の文字をシンボルデータ中で各々の文字が出現する回数をシンボルの重みとして扱い、

[シンボル, 重み] のペアからなるリストと、制限したい符号の長さ情報が与えられたとき、package-merge algorithmを使って符号表を生成する手順を以下に示す

f:id:DarkCrowCorvus:20161224172840j:plain

１. ステージの初期化

制限したい符号の長さの数だけのステージを用意し、シンボルのリストの内容物によってそれぞれ初期化する。

ここであらかじめ、一番上のステージのリストはシンボルの重みの昇順にソートしておく。

f:id:DarkCrowCorvus:20161224191534j:plain

２. パッケージマージ

一番上のステージにある要素を、先頭から順番に2つずつ選び出し、そのペアからなる パッケージ をそれぞれ作成する。

その後、作成したパッケージを一つ下のステージにマージする

f:id:DarkCrowCorvus:20161224191941j:plain

ここで パッケージ はペアとなる要素それぞれへの参照と、その2つの要素の重みの合計値を自身の重みとして持つ。なお、ペアを作れなかった要素に対しては何も行わず無視する

マージ後、そのステージの要素を昇順に並べ替える。

またその後、そのステージで2つずつのペアを作ったとき、ペアを組めず無視されるであろう要素があれば、あらかじめそのステージから除外しておく

f:id:DarkCrowCorvus:20161225003416j:plain

ここまでのパッケージマージの流れを、今度は２番目のステージから、その下の３番目のステージに対して行い、最終的に一番下のステージにたどり着くまでこれを繰り返す

f:id:DarkCrowCorvus:20161225021548j:plain

３. 符号長を抽出

最終的に、一番下のステージに出揃った各々の要素を一つずつピックアップし、各々の要素が持つシンボル、またはその要素が参照しているシンボルの数だけ該当のシンボルの符号長をインクリメントする

f:id:DarkCrowCorvus:20161225115930g:plain

各々のシンボルの符号長は、多くてステージの数までとなり、パッケージマージの過程で、無視され除外された回数の多いシンボルほど、最終的な符号長が小さくなるという仕組みになっている

４. 符号表を作成

後はカノニカル・ハフマン符号化の手順に従って、各々のシンボルの符号長から符号表を作成する

符号長別にグループ分けした後、その中で文字番号の小さい順に並べかえる
符号長が短く文字番号の小さなシンボルほど小さな符号になるよう符号を割り当てる

f:id:DarkCrowCorvus:20161225165246j:plain

これで、package-merge algorithm によって最大符号長の制限された符号表が完成する

遅延 package-merge

package-merge algorithm は一番下のステージに出揃った要素をピックアップして、各々のシンボルの符号長を求める

この一番下に出揃う要素について、その数に着目すると、
ステージの数にかかわらず、必ず $2n - 2$ だけになる。
このあたりなんかうまくそうできてるらしい

f:id:DarkCrowCorvus:20161225184410j:plain

これから察するに、最後のステージに対して、 $2n-2$ 回だけ要素の作成を要求して、その過程で必要になり次第、上のステージの要素を作成してパッケージを貰ってくる...というアルゴリズムが組めそうだ。

実際に必要になるまで上のステージの要素の作成を遅らせる様子から、
このアルゴリズムのことを、
遅延 package-merge (Lazy package-merge)　と呼ぶことにする。

生成手順

各々のステージはそれぞれ以下の情報を保有する

要素1 (先読みツリー)
要素2 (先読みツリー)
シンボルカウンタ

このうち、2つの "要素" は自身の一つ下のステージで、次にパッケージを作成する元として使われるであろう候補の要素を事前に知っておくために保有しておく

冒頭で紹介した資料さんによれば、
この要素のことを 先読みツリー (lookahead tree) と呼ぶそうだ

なお最下段のステージは、自身の下にパッケージを提供するステージが存在しないため、先読みツリーを持たなくても構わない。

"シンボルカウンタ" は自身のステージで、[シンボル,重み] のリストをいくつだけ読んだかの情報を覚えておくために、その数を保持する。

遅延 package-mergeを使った符号表の生成手順を以下に示す

１. シンボルリストをソート

[シンボル,重み] のリストを、あらかじめ重みの昇順になるように並べ替えておく

２. ステージの初期化

一番下のステージを除いて、各ステージ上の先読みツリー2つを、重みの昇順に並んだ [シンボル,重み] リストの上二つの要素で初期化する。

また、シンボルカウンタには、リストを "2つ" 読み出したことを記録しておく

f:id:DarkCrowCorvus:20161227232710j:plain

３. 要素を作成

これから、最下段ステージに要素を作成する次の手順を、 $2n-2$ 回だけ繰り返す

まず、[シンボル,重み] のリストから次に読み出せる要素の重みと、自身の一つ上の先読みツリー2つの重みの合計のどちらが小さいかを比較する。

リストの要素の重みのほうが小さければ 3.1 の処理、そうではない場合、またはシンボルのリストから読み出せる要素がもうない場合は 3.2 の処理へ進む

f:id:DarkCrowCorvus:20161229200142j:plain

3.1 [シンボル,重み] リストの要素を追加

[シンボル,重み] のリストから読み出した要素を自身のステージに追加する。
その後、シンボルカウンタを1つ進める。

f:id:DarkCrowCorvus:20161229204603j:plain

なお、１番目、２番目に追加される要素は必ず、[シンボル,重み] のリストの１番目、２番目の要素になるため、２. ステージの初期化 で各ステージを初期化する際に、この要素２つをあらかじめ最下段ステージに作成しておいてもかまわない。

f:id:DarkCrowCorvus:20161229205426j:plain

3.2 先読みツリーのパッケージを追加

一つ上のステージの先読みツリー2つからパッケージを作成し、自身のステージへ追加する。

f:id:DarkCrowCorvus:20161229213605j:plain

一つ上の先読みツリーからパッケージが作成されるたび、ここまでの 3.要素を作成 の手順を、今度は一つ上のステージに対して2回行うことで先読みツリー2つを更新する。

この過程でさらに上のステージの先読みツリーからもパッケージが作られれば、そのステージでも同じ通り、新しい要素を作成する手順を2回行う。

それよりさらに上のステージでも同様、最終的に更新が必要な先読みツリーすべてに対して、新しい要素が補填されるまでこの処理は繰り返される

なお最上段のステージは、上にパッケージを貰ってこれるステージが存在しないため、常に [シンボル,重み] リストのまだ読んでいない新しい要素 2つによって先読みツリーを更新する

f:id:DarkCrowCorvus:20161230172854g:plain

最下段のステージに $2n-2$ 個の要素がそろえば、あとは通常の package-merge algorithm の時と同様の手順で、各シンボルの符号長を導出し、符号表を作成できる

利点

早いうちに最下段ステージに要素が作成されるというのが、このアルゴリズムの特徴になる。これによる利点は、メモリ空間の再利用ができるということ

符号長を導出する手続きは、なにも最下段のステージに要素がすべて出揃うのを待つ必要はない。要素が一つ新しく作成されるたびに、その要素がもつシンボル、またはその要素が参照するシンボルの符号長を更新することができる。

符号長の更新後、その要素とそれが参照している要素は、もう扱われることがない。そのため、それらの要素を保持するために使ったメモリ空間は、これより以降に要素を作成するために使いまわすことができる。

f:id:DarkCrowCorvus:20170101011731j:plain

要素のプールを作成してこれを実現する場合、
資料さんによれば、プールの "空き要素" は $nL$ つだけ必要とのこと。
(資料さんに載ってるここの証明がうまく理解できなかった。悔しい)

※ 2017/01/07追記
たまに $nL$ で空き要素が足りないことがあるっぽい。一番下のサンプルプログラムのほうは、ステージの数を減らしたりしてひとまず対処してみてるけど、理由はよくわかってない

なお、 $n$ はシンボルの数、 $L$ は制限したい符号の長さを表す。

境界 package-merge

package-merge algorithm で生成した各ステージ上の要素のうち、実際にシンボルの符号長を求めるために使われた要素に対して色を付けてみる。

f:id:DarkCrowCorvus:20170102163345j:plain

最下段のステージを除いて、それより上にある各ステージはともに、ある要素を境にして、実際に符号長の導出のために使われた要素(左側) と使われなかった要素(右側)に分かれるのがわかる。

この色のついた左側にある要素を、以降は "アクティブな要素" と呼んで扱うことにする

さらにこのアクティブな要素のうち、シンボル単体からなる要素 (パッケージではない要素) に着目し、その数を数えてみる

f:id:DarkCrowCorvus:20170102163357j:plain

シンボル単体からなる要素は、各ステージともに、その重みの小さい順にもれなく出現している

そのため、アクティブなシンボル単体の要素の数が、その中で２であるとするならば、そこには重みの一番小さなシンボルと、2番目に小さなシンボルの 2つが必ず現れる

アクティブなシンボル単体の要素の出現回数を $c$ と定義するならば、重みの昇順に並んだ１～ $c$ 番目までのシンボル単体からなる要素が、そこには出現することになる

この通り、アクティブなシンボル単体の要素の出現回数だけをステージごとに覚えておきさえすれば、後から実際に出現したシンボル単体の要素が何であるかを推測できる

出現回数から、実際に出現するシンボルが何であるかを割り出せれば、あとはそのシンボルの符号長をインクリメントする...という方法で同じ通り符号長の導出ができそうだ。

f:id:DarkCrowCorvus:20170103144355g:plain

アクティブな要素とアクティブでない要素との境界をステージごとに形成し、それよりも左側に出現したシンボル単体の要素の数から、各シンボルの符号長を求めるこのアルゴリズムを

境界 package-merge (Boundary package-merge) と呼ぶことにする。

生成手順

各々のステージはそれぞれ以下の情報を保有する

要素1 (先読みチェーン)
要素2 (先読みチェーン)

また、各要素は以下の情報を保有する

重み
シンボルカウンタ
要素への参照

このうち "要素への参照" は、自身の要素が作成されたときに、一つ上のステージで、一番最後にパッケージを作成する元として使われていた要素を覚えておくために利用される。以降はこの参照を チェーン と呼ぶことにする

境界 package-mergeを使った符号表の生成手順を以下に示す

１. シンボルリストをソート

[シンボル,重み] のリストを、あらかじめ重みの昇順になるように並べ替えておく

２. ステージの初期化

一番下のステージを除いて、各ステージ上の先読みチェーン 2つを、重みの昇順に並んだ [シンボル,重み] リストの上二つの要素で初期化する。

うち、先読みチェーンの右側 (重みの大きいほう) の要素は、

シンボルカウンタ ⇒ ２
チェーン ⇒ なし

の状態でそれぞれ設定しておく。

f:id:DarkCrowCorvus:20170103191631j:plain

なお、一番初めの先読みチェーンの左側 (重みの小さいほう) の要素については、重み以外の情報を扱うことがないため、重み以外はテキトウな設定にしておいて構わない。

３. 要素を作成

これから、最下段ステージに要素を作成する次の手順を、 $2n-2$ 回だけ繰り返す

[シンボル,重み] のリストから次に読み出せる要素の重みと、自身の一つ上の先読みチェーン2つの重みの合計のどちらが小さいかを比較する。

3.1 [シンボル,重み] リストの要素を追加

[シンボル,重み] のリストから読み出した要素を自身のステージに追加する

要素のシンボルカウンタには、ここまでに同じステージ上で [シンボル,重み] のリストからシンボルを読んだ回数の値を設定する

要素のチェーンは、自身の一つ前の要素がチェーンを持っていれば、そのチェーンをそのまま引き継ぐ

f:id:DarkCrowCorvus:20170103191654j:plain

遅延 package-merge の時と同様、１番目、２番目に追加される要素は必ず、[シンボル,重み] のリストの１番目、２番目の要素になるため、２. ステージの初期化 で各ステージを初期化する際に、この要素２つをあらかじめ最下段ステージに作成しておいてもかまわない。

3.2 先読みチェーンのパッケージを追加

一つ上のステージの先読みチェーン2つからパッケージを作成し、自身のステージへ追加する。

要素のシンボルカウンタは、自身の一つ前の要素のシンボルカウンタの値を引き継ぐ

要素のチェーンには、パッケージ作成元の先読みチェーン２つのうち、右側 (重みの大きいほう) の要素の参照を設定する。

f:id:DarkCrowCorvus:20170103191736j:plain

この後は、遅延 package-merge の時と同様。3.要素を作成 の手順を、更新が必要な先読みチェーンすべてに、新しい要素が補填されきれるまで繰り返す。

４. 符号長を抽出

最下段のステージに $2n-2$ 回、要素を作成する手続きを行ったあと、 $2n-2$ 番目に作成される要素が、最下段のステージの 境界の要素 になる。

また、その要素がチェーンを持っていれば、そのチェーン先の要素が一段上のステージの境界の要素となり、それがまたチェーンを持っていれば、そのチェーン先の要素がさらに一段上のステージの境界の要素となる。

それぞれの境界の要素が持つ "シンボルカウンタ" には、自身を含めて自身の左側に出現したシンボル単体の要素の数を保有するため、この数から前述した方法で、各シンボルの符号長を求めることができる。

f:id:DarkCrowCorvus:20170103204520j:plain

各シンボルの符号長が求まれば、あとは package-merge algorithm と時と同様、カノニカル・ハフマン符号化の手順を利用して符号表を作成できる

利点

境界の要素 よりも左側にある各ステージ上の要素は、それが作成されても、以降扱われることはない。最下段ステージに $2n-2$ の要素を作成する過程で、境界の要素が更新されるたびに、それよりも左側にある要素のメモリ空間は、ほかの要素を作成するために使いまわすことができる。

この通り、境界 package-merge でも要素に使ったメモリ空間の再利用が行える。
遅延 package-merge との違いは、プールにあらかじめ確保しておくべき "空き要素" の数が $L(L+1)$ であるということ。遅延 package-mergeの $nL$ よりも、その数が少なくなることを期待できる

※Deflateのカスタムハフマン符号 (シンボル数 $n$ =286, 制限符号長 $L$ =15) の場合を例とするならば、遅延 package-merge を利用したとき、最大で $nL =$ 4,290 の空き要素が必要であるのに対し、境界パッケージマージを利用した時は、最大でも $L(L+1) =$ 240 の空き要素だけ用意すれば事足りる。