物工情報処理 Huffman法によるコードデータの圧縮

 

データを圧縮する方法として

1)可逆圧縮

2)非可逆圧縮

が利用されている。1)はPCのコードデータで使用されており、完全に復元できる圧縮法である。

 

1)を実現する方法として多くの方法が提案されており、実用化されているがもっとも有名で、かつ実際に使われている方法としてHuffman法が挙げられる。講義でも説明したがその具体的な例を次に詳説する。

コード列として次のアルファベットの集合を考える。

haabcagfaaghdeaabach

これをHaffmann法で圧縮するには次の手順を行えばよい。

) 出現する要素の回数を生起数となづけ、その大きいものから順に並べる。

b)生起数の小さいものから2つをまとめ、その生起数の和を新たにそのまとめたものの生起数とする。この結果、要素がひとつ減ったコード列となる。

c)再び生起数の大きいものから並べなおす。

d)b)、c)の手続きを要素が1つになるまで繰り返す。

) 以上のようにして符号の木を作り、最後に枝分かれに従って0と1の符号の記号を割り当てる。

 

与えられたコード列では以下のような割り当てが成され、総計53bitのデータに圧縮される。

 

 

生起数

割り当てられたコード

a

8

0

h

3

100

b

2

1010

c

2

1011

g

2

110

d

1

1110

e

1

11110

f

1

11111

符号の木は次のようになる。

符号の図