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

シャノン符号化とハフマン符号化

シャノン符号化

符号を出現確率でソートし,だいたい確率が半分になるところで分割する方法.

プログラム

出力
 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

ハフマン符号化

  1. 符号を出現確率でソートし,出現確率の一番小さい符号と二番目に符号を持つ節を作る.
  2. 残りの符号と,先ほど作った節の中から出現確率の一番小さい符号と二番目に符号を持つ節を作る.
  3. 残りの符号がなくなったら終わり.
プログラム

出力
 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