ハフマン符号
#情報理学I #符号化 #2元ハフマン符号化
記憶のない情報源に対するコンパクト符号の代表
Huffman code
2元ハフマン符号化の方法
情報源$ Sの記号$ a_jの出現確率を$ p_jとする（$ j=1,2, ..., n）
1. 確率の小さい方から順に2つの記号$ a_i, a_jをとってくる
2. この2つをまとめて1つの新たな記号とする（確率は$ p_i+p_j）
3. 新しい記号群で1.の手順に戻り、n-1回繰り返し全体を１つの記号に
4. 符号の木を作成
5. 符号の木の枝に0と1を割り当て
6. 根から葉まで辿り、2元記号列を符号とする
ハフマン符号化は一意に定まらないことがある
応用例
ファイルの圧縮
ZIP
gzip
LHA
画像の圧縮
jpeg
png
音声・映像の圧縮
MP3
AAC
MPEG2
実際には他の技術も組み合わせている。