自由研究ノート(仮)

とかいう名前の備忘録

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 algorithm は、最大符号長の制限されたハフマン符号表を生成するために利用できる

 

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

 

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

00 01 10 11

 

最大符号長を「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

 

1. ステージの初期化

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

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

 

f:id:DarkCrowCorvus:20161224191534j:plain

 

2. パッケージマージ

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

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

 

f:id:DarkCrowCorvus:20161224191941j:plain

 

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

 

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

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

 

f:id:DarkCrowCorvus:20161225003416j:plain

 

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

 

f:id:DarkCrowCorvus:20161225021548j:plain

 

3. 符号長を抽出

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

 

f:id:DarkCrowCorvus:20161225115930g:plain

 

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

 

4. 符号表を作成

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

 

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

 

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を使った符号表の生成手順を以下に示す

  

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

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

 

2. ステージの初期化

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

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

 

f:id:DarkCrowCorvus:20161227232710j:plain

 

3. 要素を作成

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

 

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

 

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

 

f:id:DarkCrowCorvus:20161229200142j:plain

 

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

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

 

f:id:DarkCrowCorvus:20161229204603j:plain

 

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

 

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 と定義するならば、重みの昇順に並んだ 1~ c 番目までのシンボル単体からなる要素が、そこには出現することになる

 

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

 

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

 

f:id:DarkCrowCorvus:20170103144355g:plain

 

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

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

 

生成手順

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

 

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

 

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

 

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

 

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

 

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

 

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

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

 

2. ステージの初期化

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

 

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

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

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

 

f:id:DarkCrowCorvus:20170103191631j:plain

 

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

 

3. 要素を作成

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

 

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

 

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

 

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

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


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

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

 

f:id:DarkCrowCorvus:20170103191654j:plain

 

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

 

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

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

 

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

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

 

f:id:DarkCrowCorvus:20170103191736j:plain

 

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

 

4. 符号長を抽出

最下段のステージに 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 の空き要素だけ用意すれば事足りる。

 

遅延 package-merge のパッケージ要素が持つ要素への参照が2つであるのに対し、境界 package-merge の要素が持つ要素への参照 (チェーン) は1つだけ

 

これによって、要素の利用がピークになるとき、同時に生存していないといけない要素の 全体的な数を減らすことができるため、遅延 package-merge と比べて、はじめに準備しておくべき空き要素の数をその分だけ抑えられる

 


サンプル

 

 

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

 


参考にしたサイトさん

Package-merge algorithm - Wikipedia

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

sfnt2woff-zopfli/katajainen.c at master · bramstein/sfnt2woff-zopfli · GitHub