ハフマン符号
"AABABCAC"を単純にbitを割り当てるとA 00, B 01, C 10のように１文字に2ビットで、計16ビットかかる。
出現頻度を調べる。
"AABABCAC"のAは4、Bは2、Cは2で現れる。
ハフマン木をつくる。
最も低い出現頻度とその次のものを取ってくる。今は,B,C。
{B,C}
次の出現頻度のものはAなので
{A,{B,C}}
というハフマン木ができる。
根元から0,1をふっていく。
A = 0
B = 10
C = 11
よってハフマン符号によって
0 0 10 0 10 11 0 11
で、計12ビットに圧縮できた。
復号方法
"0" 0 10 0 10 11 0 11 ... ハフマン木に0*はないのでA確定
A "0" 10 0 10 11 0 11
A A 10 0 10 11 0 11
以下同様にハフマン木を見ていけば復号できる。
A A B A A B A B
