情報理論・符号理論の問題

ハフマン符号は、「確率の最も小さい 2 つを 1 つにまとめる」操作を、残りが 1 つになるまでくり返して作ります。

手順 1. 確率を並べると $\frac{2}{5}=0.4,\frac{3}{10}=0.3,\frac{1}{5}=0.2,\frac{1}{10}=0.1$ です。最も小さい 2 つは $c(0.2)$ と $d(0.1)$ なので、これをまとめて確率 $0.3$ の節点 $\{c,d\}$ を作ります。

手順 2. 残りは $a(0.4),b(0.3),\{c,d\}(0.3)$ です。最も小さい 2 つは $b$ と $\{c,d\}$ なので、まとめて確率 $0.6$ の節点 $\{b,c,d\}$ を作ります。

手順 3. 残りは $a(0.4),\{b,c,d\}(0.6)$ の 2 つなので、これをまとめて根（確率 $1$）とします。

符号語の割り当て. まとめるたびに、2 つの枝に $0$ と $1$ を割り当てます。例えば
$$a:0,b:10,c:110,d:111$$
となり、符号長は $l_a=1,l_b=2,l_c=3,l_d=3$ です（クラフトの不等式も $2^{-1}+2^{-2}+2^{-3}+2^{-3}=1\le 1$ で成り立っています）。

平均符号長.
$$\bar{L}=\frac{2}{5}\cdot 1+\frac{3}{10}\cdot 2+\frac{1}{5}\cdot 3+\frac{1}{10}\cdot 3=\frac{4}{10}+\frac{6}{10}+\frac{6}{10}+\frac{3}{10}=\frac{19}{10}.$$

ハフマン符号は語頭符号の中で平均符号長を最小にするので、これが最小値です。

参考（エントロピーとの比較）. $H(X)=-\sum p_i{\log }_2{p}_i\approx 0.529+0.521+0.464+0.332\approx 1.846$ であり、$H(X)\le \bar{L}=1.9<H(X)+1$ が確かめられます。

答え：$\frac{19}{10}$

確率は a:0.4, b:0.3, c:0.2, d:0.1。ハフマン法では確率の小さい 2 つを順に併合する。
1. d(0.1) と c(0.2) を併合 → 0.3
2. 残りは a:0.4, b:0.3, (cd):0.3。小さい 2 つ b と (cd) を併合 → 0.6
3. a(0.4) と (bcd)(0.6) を併合 → 1
このとき符号長は a:1, b:2, c:3, d:3 となる。
平均符号長は $\bar{L}=0.4\cdot 1+0.3\cdot 2+0.2\cdot 3+0.1\cdot 3=0.4+0.6+0.6+0.3=1.9$。

手順 2 で別の組合せを選んだ場合も確認する。b(0.3) と (cd)(0.3) は同確率なので、a(0.4) と b(0.3) を併合する選択もある。この場合は 0.7 になり、これと (cd)(0.3) を併合する。符号長は a:2, b:2, c:2, d:2 となり、平均符号長は 2 である。しかしこれは最小の 2 つを併合していないので、ハフマン法の手順ではない。
実際には、手順 2 で最小の 2 つは b(0.3) と (cd)(0.3) である。a(0.4) は最小の 2 つに入らない。

検算：クラフトの不等式は $2^{-1}+2^{-2}+2^{-3}+2^{-3}=1$ で成立する。エントロピーは約 1.846 で、$1.846\le 1.9<2.846$ なので整合している。

答えは $\bar{L}=1.9=\frac{19}{10}$ 。