ハフマン符号とエントロピー

文字を事象と考え、先ほどの例の平均情報量(エントロピー)を求めてみよう。 Aが現れる確率は8/20, G が現れる確率は7/20, Cが現れる確率は3/20, Tが現れる確率は2/20 だから、

$$H=-\frac{8}{20}\log_2\frac{8}{20} -\frac{7}{20}\log_2\frac{7... ...c{3}{20} -\frac{2}{20}\log_2\frac{2}{20} =1.8016 \;\;{\rm bit}$$

これに対し、ハフマン符号を用いた場合の(一文字あたりの)平均ビット長は

$$37/20=1.85 \;\;{\rm bit}$$

となる。 実はハフマン符号を使って符号化を行うと、その平均ビット長は (0, 1を使う符号化の中では) もっともエントロピーに近い値となる。つまり、これ以上 ない程、最高に効率的な符号化と言える。