データ圧縮法概説　第3章−２

3.4 ハフマン符号化と復号化の手順

ハフマン符号化の手順は以下のとおりです。

元データをスキャンして、全ての記号の種類と出現率を求める。
各記号に対する葉を作り、それぞれの葉に記号とその出現率を書いておく。
出現率の最も小さい２枚の葉について節点を１つ作り、その節点と２枚の葉を枝で結ぶ。そして枝の一方には「０」、他方には「１」のラベルを付ける。
この新しい節点に２枚の葉の出現率の和を書き、この節点を新たな葉と考える。
節点より下の枝と葉をないものと考え、3.と4.の手順を繰り返す。
葉(節点)が１枚になったところで符号の木が完成する。このようにして構成した符号の木を「ハフマン木」と呼ぶ。
ハフマン木によって構成された符号に基づき、元データを可変長符号に変換する。
a→0　b→10　c→110　d→111

符号化されたデータの復号方法は、前節で説明しましたように符号化されたビット列にしたがってハフマン木を根からたどり、葉にたどり着いたところでその葉に対応する記号に逆変換します。このためハフマン符号化では圧縮後のデータにハフマン木を追加保存しておく必要があり、そのぶんが圧縮後データのオーバーヘッドになります。

3.5 符号化の実例

例として、「aabbccccddddeeeeeeeeffff」という元データを前節の手順に従って符号化してみましょう。

元データをスキャンして全記号の種類と出現率を求め、対応する葉を作る。
出現率の最も小さい２枚の葉について節点を作り、出現率を合計する。
同手順の続き。
同手順の続き。
同手順の続き。
同手順の続き、ハフマン木完成。
このハフマン木より構成されるハフマン符号。
e:0　c:100　d:101　f:110　a:1110　b:1111
元データの符号化。

1110 1110 1111 1111 100 100 100 100 101 101 101 101 0 0 0 0 0 0 0 0 110 110 110 110

a a b b c c c c d d d d e e e e e e e e f f f f

この時の圧縮率と平均符号長は次のようになります。

圧縮率＝ 60
───
24×8 ＝ 60
──
192 ＝0.3125(31.25％)

平均符号長＝ 60
──
24 ＝2.5ビット

符号化されたビット列「111011101111111110010010010010110110110100000000110110110110」を復号するのは、6.で完成されたハフマン木を利用すれば比較的簡単ですので、説明は省略します。一度、自分で実際に復号してみてください。(^_-)

3.6 ハフマン符号化の特徴

どんなデータにも適用可能で汎用性がある。
同じ記号がたくさん出てくるデータに特に向いている。
２パスで符号化するため圧縮過程が比較的低速。
圧縮率は中程度。
圧縮／展開方法が比較的理解しやすい……んじゃないかな？(^^;)

1110	1110	1111	1111	100	100	100	100	101	101	101	101	0	0	0	0	0	0	0	0	110	110	110	110
a	a	b	b	c	c	c	c	d	d	d	d	e	e	e	e	e	e	e	e	f	f	f	f