ハフマン符号
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回繰り返し全体を1つの記号に
5. 符号の木の枝に0と1を割り当て
6. 根から葉まで辿り、2元記号列を符号とする
ハフマン符号化は一意に定まらないことがある
応用例
ファイルの圧縮
ZIP
gzip
LHA
画像の圧縮
jpeg
png
音声・映像の圧縮
MP3
AAC
MPEG2
実際には他の技術も組み合わせている。