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

ハフマン符号の構成手順：確率の小さい 2 つを 1 つにまとめる（確率は和にする）操作を、残りが 1 つになるまで繰り返します。まとめるたびに、まとめられた記号の符号長が 1 ずつ増えます。

確率を小数で書くと $a_1:0.35,a_2:0.25,a_3:0.2,a_4:0.1,a_5:0.1$ です。

手順 1：最小の 2 つ $a_4(0.1)$ と $a_5(0.1)$ をまとめて $b_1=\{a_4,a_5\}$（確率 $0.2$）を作る。残りは $0.35,0.25,0.2(a_3),0.2(b_1)$。

手順 2：最小の 2 つ $a_3(0.2)$ と $b_1(0.2)$ をまとめて $b_2$（確率 $0.4$）を作る。残りは $0.35(a_1),0.25(a_2),0.4(b_2)$。

手順 3：最小の 2 つ $a_2(0.25)$ と $a_1(0.35)$ をまとめて $b_3$（確率 $0.6$）を作る。残りは $0.4(b_2),0.6(b_3)$。

手順 4：$b_2$ と $b_3$ をまとめて確率 $1$ となり終了。

まとめた順を逆にたどって、分かれるたびに一方に $0$、他方に $1$ を付けると、たとえば
$$a_1:10,a_2:11,a_3:00,a_4:010,a_5:011$$
という符号が得られます。符号長は $l_1=l_2=l_3=2,l_4=l_5=3$ です（クラフトの不等式を確かめると $3\cdot 2^{-2}+2\cdot 2^{-3}=1\le 1$ で、語頭符号になっています）。

平均符号長：
$$\bar{L}=2\left(\frac{7}{20}+\frac{1}{4}+\frac{1}{5}\right)+3\left(\frac{1}{10}+\frac{1}{10}\right)=2\cdot \frac{4}{5}+3\cdot \frac{1}{5}=\frac{8}{5}+\frac{3}{5}=\frac{11}{5}.$$

ハフマン符号は語頭符号の中で平均符号長が最小となる符号なので、これが最小値です。なお、同じ確率のものが並んだときのまとめ方によって符号語は変わることがありますが、平均符号長は変わりません。参考までにエントロピーは $H(X)\approx 2.16$ ビットで、$H(X)\le \bar{L}<H(X)+1$ を満たしています。

答え：$\bar{L}=\frac{11}{5}$

確率を 100 分の 1 の単位で表すと、35, 25, 20, 10, 10 である。

ハフマン法の手順：
1. 最小の 2 つ（10 と 10）を合併して 20 を作る。残りは 35, 25, 20, 20。
2. 最小の 2 つ（20 と 20）を合併して 40 を作る。残りは 35, 25, 40。
3. 最小の 2 つ（25 と 35）を合併して 60 を作る。残りは 40, 60。
4. 最後に 40 と 60 を合併して 100 を作る。

符号語の長さ：
- 40 のグループ：a_3（20）と、(a_4, a_5) の合併(20) からなる。a_3 は深さ 2、a_4, a_5 は深さ 3。
- 60 のグループ：a_1（35）と a_2（25）は深さ 2。

よって l = (2, 2, 2, 3, 3)。

平均符号長：
$\bar{L}=2(0.35+0.25+0.2)+3(0.1+0.1)=1.6+0.6=2.2$

別の結び方の確認：手順 2 で 20 同士ではなく、a_3(20) と合併 20 のどちらを選んでも同じ 20 同士であり、a_3 と (a_4,a_5) の合併が唯一の組合せである。また、手順 1 の後に a_3(20) と合併 20 は同点だが、最小 2 つは 20 と 20 で一意に決まる。したがって平均符号長は一意に 2.2 となる。

検算：エントロピー H ≈ 0.35·1.515+0.25·2+0.2·2.322+0.2·3.322 ≈ 0.530+0.5+0.464+0.664 = 2.158。H ≤ L < H+1 を満たす。