Canonical Huffman Codeの概要
Canonical Huffman Code（以下、CHC）はHuffman Codeの一種ですが、さらに次の条件が満たされます。
- 各文字の符号の辞書式順序は、文字の出現確率の大きい順序と一致する。
例えば、先ほどのデータのa、b、c、d、e、fの出現回数がそれぞれ67、11、7、6、5、4の場合、表2のように符号が決定されます。Huffman法の場合、左と右の枝のどちらに0または1を付けるかで自由度があるのですが、このCHCは符号が一意に決定されます。図2に、この場合の木を便宜的に紹介します。このようにCHCでは必ず片方に偏った木ができます。
| 文字番号 | 出現回数 | 最適な符号長 | 符号 |
| a | 67 | 1 | 0 |
| b | 11 | 3 | 100 |
| c | 7 | 3 | 101 |
| d | 6 | 3 | 110 |
| e | 5 | 4 | 1110 |
| f | 4 | 4 | 1111 |
この条件3で、符号・復元が簡単になります。理由は後で詳述しますが、簡単に言えば文字同士の辞書式順序の比較が可能だということです。上の符号の例で使って説明すると、符号化されたデータから4bit読み込んだ段階で1101とわかっていれば、1101と各文字を辞書式順序で比較し、110 (d) < 1101 < 1110 (e) なので、この1101の最初3bitはdだと分かります。
こでは各文字の確率表から、余計な作業領域を必要とせずに直接各文字の符号を求める巧妙なアルゴリズム（参考資料1）を紹介します。このアルゴリズムは入力として、出現確率の大きい順にソートされている確率表を受け取ります。詳細は次のとおりです。
- Huffman法と同じように、出現確率の最も小さい2つの要素を選択し、その要素をマージした結果を保持する。マージしたことによって必要が無くなった確率表のエントリに、新しくできた節点へのポインタを保持する。
- 1.を最後まで繰り返す。
- 2.によって構成されたHuffman Treeから、各文字の符号長を求める。
最も出現確率が小さい文字を選ぶのは、まだ親の節点を持っていない文字の中で最も出現確率が小さい文字か、節点の中で最も出現確率が小さい2つを比較することで行われます。該当するソースコードは「chc.hpp」中のculcHuffmanLength()です。
ここまでで、各文字の最適な符号長が求められました。次に各文字の符号を決定します。始めに符号長が最も短い文字（出現確率が高い文字）の符号を「0..0」とします。それ以外の文字の符号は、前の文字の符号に1を加え、文字符号長が長くなる場合は長くなった分0を最後につけます。これですべての文字の符号が決定できます（これで上の条件すべてを満たす符号が構成できますが、詳しい証明は省略します。詳細は参考資料1を参照してください）。
例えば表2の例では、初めにaに対し符号「0」が決定され、次にbに対する符号は、符号長が3とaより2長いので、aの符号「0」＋1＝1の最後に0を2つ付けた「100」となります。次のcに対する符号は、長さが同じなのでbの符号に1を足した「101」となります。
さて、次に表引きで、どのように各符号を求めるかを説明します。符号長がLの文字の個数をC（L）とします。また、符号長がLの文字の中で最も符号の値が小さい（出現確率が大きい）文字に対する符号をBase（L）とします。また、その文字の順位をOffset（L）とします。この時、符号化したい文字の順位がxのとき、xの符号長Lはoffset[L+2] > x >= offset[L+1]を満たすLとして求められ、(x-offset[L])+base[L]がxの符号となります（該当ソースコードは「chc.hpp」中のchcEncode::encode()）。
復号の時は、可能性のある最大bitを読み込み、どの文字が符号化されたかを調べます。この読み込んだ値をVとします。まず符号長を求めるのに、各Lについて、limit[L] := base[L]<<Lのように定義されるlimitを保持します。このlimitとVを比較し、符号長を求めます。具体的にはlimit[L] > V >= limit[L-1]となるLを求め、(Vの先頭Lbit - base[L]) + offset[L]が復号された文字になります（該当ソースコードは「chc.hpp」中のchcDecode::decode()）。
次の文字を復号する場合は、実際に使われた分だけVから取り除き、足りなくなった分を残りのバッファから読み込みます。そして上と同様の操作を繰り返します。
| L:符号の長さ | C（L） | base（L） | offset（L） |
| 1 | 1 | 0 | 1 |
| 2 | 0 | - | - |
| 3 | 3 | 4 | 2 |
| 4 | 2 | 14 | 5 |
| 5 | 0 | - | 7（番人） |
符号、復号で時間がかかるのは符号長Lを決定する部分です。ここは一見、二分探索を使って求めたくなりますが、ほとんどの場合、小さいLで比較が終了するので線形探索の方が高速です。さらに高速化したい場合は、小さいLを求めるためのテーブルを作成しておきます。実際の実装では、符号はすべて前もって作られた表引きによって行われています。復号は小さいLについては表引きでLを決定し、復号します。
符号長に上限がある場合の最小冗長符号の求め方
今まで紹介した符号は、確かにデータを最小長で表現可能ですが、実際に利用する場面では符号が長すぎると困る場合があります。例えば、ビット演算を32bit整数を用いて実現する場合、32bitより長い符号を扱うことが困難となります。また、復号を高速化するために、すべての符号が表に載るように符号を短くしたい場合があります。
符号長が一定長Mより長くならないような制限を加えた場合において、最小冗長符号を求める方法は、既にいくつか提案されています。今回は1995年にTurpinらが提案した「reverse package merge」と呼ばれる手法（参考資料2）を用いて実現します。
この方法では、初めにすべての文字に対してM bitの符号が与えられたと考えます。次に各文字の符号を、復元可能な条件を満たしたまま短くしていきます。この時、全体のサイズが一番小さくなるようなものを優先的に選んで短くしていきます。このアルゴリズムの計算量・作業領域量はO(n(M - log n + 1))です（ただしMは符号長の上限、nは文字種類数）。詳細については、参考資料2を参照してください（該当ソースコードは「chc.hpp」中のchcEncode::culcHuffmanLengthLimited()）。
実際の実装では、初めに制約なしで最適な符号長を求めた後（計算量はO(n)）、制約が満たされない場合に、今紹介した方法を用いて制約付きでの最適な符号長を求めます。
Canonical Huffman Codeの使い方
CHCは、付属のソースコードの「chc.hpp」をincludeすることで利用できます。
CHCは符号表を構築するため、最初に各文字がデータ中で何回出現したかを記録した表注2と、符号化されたデータの出力先のファイルのポインタを渡す必要があります。その後は、void chcEncoder::encode(int x)で文字xを符号、int chcDecoder::decode()で復号します。
vector<int> count(ALPHASIZE); //ALPHASIZEは文字種類数 //...count[i] に文字iの出現回数を入れる FILE* outfp = fopen("test.chc","wb"); .. chcEncoder ce(count,outfp); { int c; while ((c = fgetc(infp)) != EOF){ ce.encode(c); } } ce.flush();
符号の長さに上限を設けたい場合は、コンストラクタに第3引数を与えます。
chcEncoder ce(count,outfp,20); //符号長が20以下である制約を加える。
ただし、その上限の制約で文字集合が表現できない場合（例えば2bitの制約がある上で8種類の文字を表現することは、2bitが4通りの文字しか表現できないので不可能）は、制約を加えずにそのまま処理を実行します。
復元は、符号の時に用いたファイルを開き、1文字ずつ復元していきます。ファイルの最後に到達した時、decodeはEOFを返します。
FILE* infp = fopen("test.chc","rb"); chcDecoder cd(infp); { int c; while ((c = cd.decode()) != EOF){ fputc(c,outfp); } }
chcを実際に利用したサンプルプログラムが「chc_unitTest.cpp」です。また、これをコンパイルしたものが「chc.exe」です。このプログラムは、
chc e inputfile
により、「inputfile」中の各文字の出現回数を求め、CHCで符号化します。そして、「inputfile.chc」という名前で保存します。
chc d inputfile.chc
で、「inputfile.chc」から元の「inputfile」を復元します。ただし、テストファイルのため、比較ができるように違う名前「inputfile.chc.tes」で復元した結果を保存します。実際はこの「chc_unitTest.cpp」を改造して利用するとよいと思います。
その他
CHCは以前から多くの実装の場面で使われていました。最適な構築方法や、その性質がまとめられたのは90年代のA. Moffatらの仕事によるものです。CHCの特徴は作業領域が小さいことにあります。実際にHuffman符号などで作業領域が問題になる場合は多くないのですが、最近のコンピュータは、主要計算部分が1次キャッシュに載るかどうかで実行速度が大きく変わってきます。CHCの作業領域は約符号長の種類数(≒log(文字種類数)) * 2 * sizeof(int)です。
まとめ
今回紹介したCHCは、最小冗長符号であるHuffman符号を高速に処理できるように符号に制約を加えたものです。この制約のおかげで、シンプルな表引きで符号・復号が行えます。さらに符号長に制約が加わった場合の最適解を求める方法も紹介しました。
参考資料
- 『Compression and Coding Algorithms』 A. Moffat、A. Turpin 著、Kluwer Academic Publishers、2002年
- The Computer Journal, 38(5):339-347 『Practical length-limited coding for large alphabets』 A. Turpin、A. Moffat 著、1995年
