文字列 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×8＝16ビット。ハフマン符号は14ビットまで縮みます。

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

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

H = 1/2×1 + 1/4×2 + 1/8×3 + 1/8×3 = 1.75 ビット/文字

8文字ぶんなら 1.75 × 8 = 14ビット。ハフマン符号の結果とぴったり一致します。

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