ハフマン符号について勉強してみる - 理論編

アルゴリズムの勉強をしてみる Advent Calendar 2016 6日目の投稿です。

ハフマン符号とは

from Wikipedia: ハフマン符号

ハフマン符号（ハフマンふごう、Huffman coding）とは、1952年にデビット・ハフマン（英語版）によって開発された符号で、文字列をはじめとす>るデータの可逆圧縮などに使用される。
ほかのエントロピー符号と同様、よく出現する文字には短いビット列を、あまり出現しない文字には長いビット列を割り当てることで、メッセージ>全体の符号化に使われるデータ量を削減することを狙っている。

ハフマン符号とは、データを圧縮するためのアルゴリズムで、JPEG, ZIP, LZH等で使われています。
よく出てくる文字には短いビット列、あまり出ない文字には長いビット列を割り当てることでサイズを削減します。
ということで、このアルゴリズムの中心は文字の出現頻度からビット列を生成する部分になります。

簡単な例

This is a pen.

上記文字列(最近流行りのアレを狙ったわけではありません)をハフマン符号で圧縮してみます。
出現する各文字について、出現する回数とハフマン符号のアルゴリズムで求まるビット列を下表に示します。

※ この部分に、すべての文字に対して0, 10, 110, ..., 11...0, 11...1という形式の符号が割り当てられている表を掲載していましたが、@le_panda_noirさんのご指摘の通りこれは完全な誤りなので、一旦削除させていただきます。
後日修正いたします。

アルゴリズム

1. 元の文字列に出現するすべての文字に対応するノードをつくります。
   ノードの値として、その文字及び出現回数を持たせておきます。
2. すべての親を持たないノードのうち、出現回数が最も小さいものから順に2つ選びます。
3. 1. で選んだ2つを子要素とする親ノードを作成します。このノードの出現回数は2つの子要素の出現回数の合計とします。
4. 親ノードを持たないノードの個数が1個になるまで、これらの操作を続けます。

このようにして作られた木をハフマン木とよびます。以下、ハフマン木からどのようにしてビット列を構成するかについて述べます。

1. まず木の頂点要素から見ていきます。空のバッファを用意しておきます。
2. 子要素を辿っていきます。1つ目の要素をたどるときは0を、2つめの要素をたどるときは1をバッファに追加していきます。
3. 以上の処理を、文字ノードにたどり着くまで繰り返します。
4. 文字ノードにたどり着いた時、その文字に対応するビット列がバッファの内容になります。

次回

ハフマン符号について勉強してみる - 実装編 に続く(かも)