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

ハフマン符号は、「確率の最も小さい $2$ つを $1$ つにまとめる」操作を、残りが $1$ つになるまで繰り返して作ります。まとめるたびに、まとめた $2$ つの片方に $0$、もう片方に $1$ を割り当てます。

比べやすいように、確率を分母 $20$ にそろえます。
$$a_1:\frac{9}{20},a_2:\frac{5}{20},a_3:\frac{4}{20},a_4:\frac{2}{20}$$

手順 1：最も小さい $2$ つは $a_4\left(\frac{2}{20}\right)$ と $a_3\left(\frac{4}{20}\right)$ です。これをまとめて $\{a_3,a_4\}$（確率 $\frac{6}{20}$）とします。

残りは $\frac{9}{20},\frac{5}{20},\frac{6}{20}$ です。

手順 2：最も小さい $2$ つは $a_2\left(\frac{5}{20}\right)$ と $\{a_3,a_4\}\left(\frac{6}{20}\right)$ です。これをまとめて $\{a_2,a_3,a_4\}$（確率 $\frac{11}{20}$）とします。

残りは $\frac{9}{20},\frac{11}{20}$ です。

手順 3：残りの $2$ つをまとめると確率 $1$ になり、終わりです。

符号語の割り当て：まとめた順と逆にたどり、$0,1$ を付けていきます。
- 手順 3：$a_1\to 0$、$\{a_2,a_3,a_4\}\to 1$
- 手順 2：$a_2\to 10$、$\{a_3,a_4\}\to 11$
- 手順 1：$a_3\to 110$、$a_4\to 111$

よって符号長は $l_1=1,l_2=2,l_3=3,l_4=3$ です。符号 $\{0,10,110,111\}$ は、どの符号語も他の符号語の語頭（先頭部分）になっていないので、語頭符号です。（なお、符号長について $2^{-1}+2^{-2}+2^{-3}+2^{-3}=1\le 1$ とクラフトの不等式を満たしており、この符号長をもつ語頭符号が存在することとも整合しています。）

平均符号長：
$$\bar{L}=\frac{9}{20}\cdot 1+\frac{5}{20}\cdot 2+\frac{4}{20}\cdot 3+\frac{2}{20}\cdot 3=\frac{9+10+12+6}{20}=\frac{37}{20}$$

ハフマン符号は語頭符号の中で平均符号長が最小になる符号なので、$\frac{37}{20}=1.85$ がこの情報源に対する $2$ 元語頭符号の平均符号長の最小値です。

（参考）エントロピーは $H(X)=-{\sum }_i{p}_i{\log }_2{p}_i\approx 0.518+0.500+0.464+0.332=1.815$ ビットであり、$H(X)\le \bar{L}<H(X)+1$ が成り立っていることも確かめられます。

答え：$\frac{37}{20}$

確率を 20 分の何かで表すと、$a_1:9/20,a_2:5/20,a_3:4/20,a_4:2/20$ である。

ハフマン法で確率の小さい 2 つを順に併合する。
1. 最小の 2 つ $a_4(2/20)$ と $a_3(4/20)$ を併合して $6/20$ を得る。
2. 残りは $9/20,5/20,6/20$ である。小さい 2 つ $5/20$ と $6/20$ を併合して $11/20$ を得る。
3. 残りは $9/20$ と $11/20$ なので、最後にこれらを併合する。

符号語の長さは $a_1$ が 1、$a_2$ が 2、$a_3$ が 3、$a_4$ が 3 となる。

平均符号長は
$$\bar{L}=\frac{9}{20}\cdot 1+\frac{5}{20}\cdot 2+\frac{4}{20}\cdot 3+\frac{2}{20}\cdot 3=\frac{9+10+12+6}{20}=\frac{37}{20}=1.85$$

検算として、併合で現れた確率（内部節点）の和を求める。$6/20+11/20+20/20=37/20$ となり、一致する。

なお、$a_1$ と $a_2,a_3,a_4$ の側を最初に併合する別の木（長さ 2,2,2,2 など）では平均が 2 になり、より大きいので最適ではない。