シャノン符号化とハフマン符号化
シャノン符号化
符号を出現確率でソートし,だいたい確率が半分になるところで分割する方法.
プログラム
出力
A:1001 B:000001 C:001001 D:00110 E:110 F:001000 G:000011 H:01000 I:0111 J:0000000010 K:00000001 L:00111 M:00011 N:0110 O:1000 P:000010 Q:0000000001 R:01001 S:0101 SP:111 T:101 U:00101 V:0000001 W:000101 X:0000000011 Y:000100 Z:0000000000
ハフマン符号化
- 符号を出現確率でソートし,出現確率の一番小さい符号と二番目に符号を持つ節を作る.
- 残りの符号と,先ほど作った節の中から出現確率の一番小さい符号と二番目に符号を持つ節を作る.
- 残りの符号がなくなったら終わり.
プログラム
出力
A:1101 B:000001 C:00000 D:00101 E:010 F:110011 G:100001 H:1000 I:1110 J:1001000011 K:11000011 L:10101 M:010011 N:0110 O:1001 P:010001 Q:0101000011 R:0100 S:1100 SP:111 T:1011 U:10000 V:0000011 W:100011 X:1101000011 Y:110001 Z:0001000011
その他
シャノン符号のツリーが出来る様子の画像を生成するスクリプトも作ったので置いておきます.PythonからImageMagickを使っています.
% python/generate_shannon_pic.py % cd image % convert -loop 0 -delay 100 *png output.gif