文字列 AAAABBCD(8文字)を例にハフマン符号と情報量の関係を整理します。

1. 出現回数・確率・情報量

文字 回数 確率 p 情報量 −log₂p
A 4 1/2 1
B 2 1/4 2
C 1 1/8 3
D 1 1/8 3

出現頻度が高いほど確率が大きく、情報量は小さくなります。

2. ハフマン木

左の枝＝0、右の枝＝1。

3 木の作り方(ノードの数字の意味)

ノードの数字は「その配下にある文字の出現回数の合計」。手順はシンプル。

  1. 一番回数が少ない2つを選んで結合する
  2. 新ノードの数字 = 2つの回数の合計
  3. 1つにまとまるまで繰り返す

C(1)+D(1) → 2 ／ B(2)+2 → 4 ／ A(4)+4 → 8(ルート＝総文字数と一致)

4. 根から葉までの符号

文字 符号 ビット数
A 0 1ビット
B 10 2ビット
C 110 3ビット
D 111 3ビット

5. 符号化と圧縮結果

AAAABBCD → ハフマン符号:

0,0,0,0,10,10,110,111
方式 ビット数
固定長(2bit×8文字) 16ビット
ハフマン符号 14ビット
理論限界(エントロピー) 14ビット

固定長は文字種 4 種(A,B,C,D)を区別するため 2 ビット必要です → $2 \times 8＝16$ ビットになります。
ハフマン符号は14ビットです。

6. なぜ14ビットが理論の限界なのか

平均情報量(エントロピー) $H$ は、各文字の確率×情報量の合計:

\[\begin{aligned} H = -\frac{1}{2}\log_{2}\frac{1}{2} -\frac{1}{4}\log_{2}\frac{1}{4} -\frac{1}{8}\log_{2}\frac{1}{8} -\frac{1}{8}\log_{2}\frac{1}{8} \\ H = \frac{1}{2} \times 1 + \frac{1}{4} \times 2 + \frac{1}{8} \times 3 + \frac{1}{8} \times 3 = 1.75 ビット \end{aligned}\]

8 文字ぶんなら $1.75 \times 8 = 14\ ビット$ 。
ハフマン符号の結果と一致します。

これは各文字の確率がちょうど 1/2, 1/4, 1/8, 1/8 のように 2 のべき乗の逆数 になっている特別なケースだからです。一般にはハフマン符号はエントロピーに近いですが、必ずしも完全一致するとは限りません。