はじめに
「データ圧縮」は、必要な情報を残したまま、データをコンパクトに保存・伝送する技術であり、テキストや画像・動画情報の圧縮など、多くの場面で使われる情報化社会において不可欠なものとなっています。データ圧縮の中身は、「モデル化」と「符号化」の2種類に大きく分けられます。前者はデータをどのように表現するかを求める部分であり、後者はその表現したものをコンピュータ上でどう保存するかという部分です。今回扱うCHCは、この後者のための代表的な技術であり、モデルが分かっているデータを最も短い符号長注1で保存する技術です。
対象読者
C++の利用者を対象としています。データ圧縮の基礎を知っていることが望ましいです。
必要な環境
C++、32bit環境を想定しています。Windows XP上のVisual Studio C++ 2005、gcc 3.2.2で動作確認済みです。
Huffman Codeの概要
初めに、Huffman Code（以下、HC）について簡単に説明します。データ中に出現する各文字の出現確率が既に分かっている、もしくは予測できる場合に、多く出現する文字に対し短い符号を割り当て、あまり出現しない文字に対し長い符号を割り当てることで、データ全体の符号長を短くすることができます。このように各文字の符号の長さが違う符号（可変長符号）は、元のデータに間違いなく復元できる条件は必要ですが、HCはさらに次の条件を満たした符号を決定します。
- 瞬時復元可能である
- データ全体の符号長が最小である
「瞬時復元可能」とは、符号化されたデータを前から順に見た時に、各符号が何の文字を表しているかを一意に決定できることであり、ある文字の符号が他の文字のprefixに含まれないことが必要十分条件です。
例えば、文字a、b、cの符号がそれぞれ0、01、001の場合を考えて見ます。この場合、符号化されたデータが「0...」と並んでいたときに、先頭の「0」を読んだ段階で、それがaかbかcか分からないため、この符号は瞬時復元可能ではありません。それに対し、それぞれの符号が0、10、110ならば、先頭の「0」を読んだ段階でこの符号がaを表していると分かります（さらに上の符号では、一意に復元できません。001とある場合abかcか分かりません）。
HCは各文字の出現確率の情報を用いてHuffman Treeを構成し、各文字の符号を決定します。こうして決定された符合は上の条件を満たします（証明は省略します）。Huffman Treeは次のようにして構成されます。
- 出現確率の小さい文字2つを選び、この2つを新しく作った節点の子とする。この節点の確率は選んだ2つの文字の出現確率の和とする。
- 1.の操作を節点が一つになるまで繰り返す。最後に残った節点を根とする。
このように構成されたHuffman Treeはニ分木であり、葉が各文字に対応しています。各節点の左の子への枝に0、右の子への枝に1を割り当てます（逆の符号を割り当ててもよいです）。各文字の符号は、木の根から文字に対応する葉までたどっていった時に、各枝に付けられた符号をつなげたものです。例えば次の例では、各文字の符号が次のように求められます。
| 文字番号 | 出現回数 | 最適な符号長 | 符号 |
| a | 67 | 1 | 0 |
| b | 11 | 3 | 100 |
| c | 7 | 3 | 111 |
| d | 6 | 3 | 110 |
| e | 5 | 4 | 1010 |
| f | 4 | 4 | 1011 |
