読者です 読者をやめる 読者になる 読者になる

Rodhos Soft

備忘録を兼ねた技術的なメモです。

ハフマン符号

アルゴリズム

"AABABCAC"を単純にbitを割り当てるとA 00, B 01, C 10のように1文字に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 

参考したサイト

michisugara.jp

広告を非表示にする