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

手順 1：ダミー記号を補う。
$D=3$ 元ハフマン符号では、1 回の操作で確率の小さい 3 個を 1 個にまとめるので、記号数は 1 回ごとに $D-1=2$ 個ずつ減る。最後に 1 個（根）にするには、記号数 $m$ が $m\equiv 1(\mathrm{mod}2)$ でなければならない。いまは $m=4$ で $4\equiv 0(\mathrm{mod}2)$ なので、確率 $0$ のダミー記号 $d$ を 1 個補って $m=5$ にする。

記号と確率：$a_1:\frac{2}{5},a_2:\frac{3}{10},a_3:\frac{1}{5},a_4:\frac{1}{10},d:0$

手順 2：確率の小さい 3 個をまとめる（1 回目）。
小さい 3 個は $d(0)$, $a_4(\frac{1}{10})$, $a_3(\frac{1}{5})$ で、まとめた節点の確率は
$$0+\frac{1}{10}+\frac{1}{5}=\frac{3}{10}.$$
残りは $a_1:\frac{2}{5},a_2:\frac{3}{10},(\text{節点}):\frac{3}{10}$ の 3 個。

手順 3：残りの 3 個をまとめる（2 回目）。
3 個をまとめると確率 $1$ の根になり、木が完成する。

手順 4：符号語を割り当てる。
根から出る 3 本の枝に $0,1,2$ を付けると、例えば
$$a_1\to 0,a_2\to 1,a_3\to 20,a_4\to 21,d\to 22(\text{使わない})$$
となる。符号長は $l_1=1,l_2=1,l_3=2,l_4=2$。
（クラフトの不等式の確認：$3^{-1}+3^{-1}+3^{-2}+3^{-2}=\frac{8}{9}\le 1$。）

手順 5：平均符号長を計算する。
$$\bar{L}=\frac{2}{5}\cdot 1+\frac{3}{10}\cdot 1+\frac{1}{5}\cdot 2+\frac{1}{10}\cdot 2=\frac{4}{10}+\frac{3}{10}+\frac{4}{10}+\frac{2}{10}=\frac{13}{10}.$$
ハフマン符号は平均符号長を最小にする語頭符号なので、最小値は $\frac{13}{10}$ である。

（参考：ダミーを補わずに最初に $a_2,a_3,a_4$ をまとめると、根の子が 2 個しかない木になり、$l=(1,2,2,2)$、$\bar{L}=\frac{16}{10}$ となって最小にならない。）

3元ハフマン符号を構成する。記号数 4 は、3元で n = 3 + 2k の形（3, 5, 7, …）にならない（4 は偶数）。そのため、確率 0 のダミー記号を 1 個加えて 5 個にしてから、3 個ずつまとめる。

確率を小さい順に並べると 0（ダミー）, 1/10, 1/5, 3/10, 2/5 である。

1 回目：0, 1/10, 1/5 を合併して 3/10 の節点をつくる。
2 回目：残りは 3/10（合併節点）, 3/10（$a_2$）, 2/5（$a_1$）の 3 個である。これを合併して根（確率 1）とする。

符号長は次のとおり。
$a_1$：長さ 1
$a_2$：長さ 1
$a_3$ と $a_4$：長さ 2（ダミーは使わない）

よって $\bar{L}=\frac{2}{5}\cdot 1+\frac{3}{10}\cdot 1+\frac{1}{5}\cdot 2+\frac{1}{10}\cdot 2=0.4+0.3+0.4+0.2=1.3$ である。

検算：クラフトの不等式は $3\cdot 3^{-1}$ ではなく、$2\cdot 3^{-1}+2\cdot 3^{-2}=\frac{2}{3}+\frac{2}{9}=\frac{8}{9}\le 1$ で成り立つ。

また、全記号を長さ 1 にするには符号記号が 4 個必要だが、使えるのは 3 個だけなので不可能である。長さ 1 の語を最大の 3 個まで使い、残り 1 記号を長さ 2 にする案を考える。
- 語 3 個のうち 2 個を長さ 1 で使い、残りの語 1 個を長さ 2 の枝にして 2 記号を載せる：これが上の構成で、$\bar{L}=1.3$。
- 長さ 1 の語を 3 個使う場合、残りの記号を載せる枝が残らないので不可能。

したがって、最小値は 1.3 である。