原理と方法

例として、AGTGCGAAAGAGGTAACACG の20文字からなるメッセージを 符号化しよう。ちなみに各文字に2ビットを割り当てる単純な符号化を すると、全体で 20×2 = 40 ビット必要になる。

1. 文字の出現頻度(もしくは確率)を調べ、大きい順に並べる。

   頻度	文字
   8	A
   7	G
   3	C
   2	T

2. 一番小さいものどうしをくっつけ、頻度(もしくは確率)を合計する。

   頻度		文字
   8		A
   7		G
   5	3	C
   	2	T

3. これを繰り返す。

   頻度			文字
   8			A
   12	7		G
   	5	3	C
   		2	T

4. できあがった表を左から右に見て行き、二つに分かれるところで上を《0》 下を《1》とする。

   頻度			文字
   8 《0》			A
   12	7 《0》		G
   《1》	5	3 《0》	C
   	《1》	2 《1》	T

5. 数字を左から読んで行くとそれがハフマン符号。
   つまり、A=0, G=10, C=110, T=111

こうして作ったハフマン符号を使って、元のメッセージを符号化すると 全部で 　　　 bit となる 。

ちなみに自分でノートで作業する際は表よりも、ツリーで表した方が 書きやすいかもしれない(図2)。

図 2: ハフマン符号を作る木