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

平均符号長が最小の $3$ 元語頭符号は、$3$ 元ハフマン符号で得られる（ハフマン符号の最適性）。確率を $\frac{1}{20}$ 単位で表すと $6,4,3,3,2,2$（合計 $20$）である。

ダミー記号の追加

$3$ 元ハフマン符号では、$3$ 個まとめるごとに記号数が $2$ 減る。最後に $1$ 個の根にまとまるには、記号数 $M$ が $M\equiv 1(\mathrm{mod}2)$ をみたす必要がある。$M=6$ は偶数なので、確率 $0$ のダミー記号 $d$ を $1$ 個加えて $7$ 個にする。

ハフマンの手順（毎回、確率の小さい $3$ 個をまとめる）

1. $0(d),2(a_5),2(a_6)$ をまとめて $4$ の節点 $u$ を作る。残り: $6,4,4,3,3$
2. $3(a_3),3(a_4),4(a_2)$ をまとめて $10$ の節点 $v$ を作る。残り: $10,6,4$
3. $10(v),6(a_1),4(u)$ をまとめて根（$20$）にする。

符号長

根から数えた深さが符号長である。
- $a_1$: 根の子なので ${\ell }_1=1$
- $a_2,a_3,a_4$: $v$ の子なので ${\ell }_2={\ell }_3={\ell }_4=2$
- $a_5,a_6$: $u$ の子なので ${\ell }_5={\ell }_6=2$

（たとえば $a_1\to 0$, $a_2\to 10$, $a_3\to 11$, $a_4\to 12$, $a_5\to 20$, $a_6\to 21$。$22$ はダミーに当たり使わない。）

クラフトの不等式を確かめると
$$3^{-1}+5\cdot 3^{-2}=\frac{3}{9}+\frac{5}{9}=\frac{8}{9}\le 1$$
で、語頭符号として実現できる。

平均符号長

$$L=\frac{6\cdot 1+4\cdot 2+3\cdot 2+3\cdot 2+2\cdot 2+2\cdot 2}{20}=\frac{6+8+6+6+4+4}{20}=\frac{34}{20}=\frac{17}{10}.$$

最小であることの直接の確認（参考）

ハフマン符号の最適性を使わずに、任意の $3$ 元語頭符号で $L\ge \frac{17}{10}$ となることも確かめられる。各記号について ${\ell }_i={\sum }_{k\ge 1}1[{\ell }_i\ge k]$ なので
$$L=\sum _{k\ge 1}P(\ell \ge k)\ge 1+P(\ell \ge 2)+P(\ell \ge 3)$$
である（$P(\ell \ge k)$ は符号長が $k$ 以上の記号の確率の和）。長さ $1$ の符号語の個数を $j$ とする。$j=3$ だと $0,1,2$ がすべて符号語になり、ほかの符号語は必ずそのどれかを語頭にもつので置けない。よって $j\le 2$ である。

• $j\le 1$ のとき: 長さ $1$ の記号の確率は高々 $\frac{3}{10}$ なので $P(\ell \ge 2)\ge \frac{7}{10}$、よって $L\ge 1+\frac{7}{10}=\frac{17}{10}$。
• $j=2$ のとき: 長さ $1$ の記号の確率の和は高々 $\frac{3}{10}+\frac{1}{5}=\frac{1}{2}$ なので $P(\ell \ge 2)\ge \frac{1}{2}$。長さ $1$ の符号語を語頭にもつ語は使えないので、残りの $4$ 個の符号語はすべて残った $1$ 文字 $c$ で始まり、長さは $2$ 以上である。$c$ で始まる長さ $2$ の語は $c0,c1,c2$ の $3$ 個しかない。もしこの $3$ 個がすべて符号語なら、$4$ 個目の符号語の先頭 $2$ 文字はこのどれかに一致し、語頭符号の条件に反する。したがって長さ $2$ の符号語は高々 $2$ 個で、$4$ 個のうち少なくとも $2$ 個は長さ $3$ 以上である。その $2$ 個の記号の確率の和は、全記号の中で小さい方から $2$ つの和 $\frac{1}{10}+\frac{1}{10}=\frac{1}{5}$ 以上なので $P(\ell \ge 3)\ge \frac{1}{5}$。よって $L\ge 1+\frac{1}{2}+\frac{1}{5}=\frac{17}{10}$。

いずれの場合も $L\ge \frac{17}{10}$ であり、上のハフマン符号で等号が成り立つので、最小値は $\frac{17}{10}$ である。

3 元の最適語頭符号は 3 元ハフマン符号で得られる。記号数 $6$ は、3 元木が完全になる個数（$1+2k$ 個、すなわち奇数）ではないので、確率 $0$ のダミー記号を 1 個加えて $7$ 個にする。

確率（単位 $1/20$）: $a_1=6,a_2=4,a_3=3,a_4=3,a_5=2,a_6=2,\text{dummy}=0$。

1. 小さい 3 つ $0,2,2$ を併合 → $4$（$=0.2$）。
2. 残り $6,4,3,3,4$。小さい 3 つ $3,3,4$ を併合 → $10$（$=0.5$）。
3. 残り $6,4,10$ を併合 → $20$（$=1$）。

平均符号長は併合で作られた内部節点の確率の和: $0.2+0.5+1=1.7$。

検算: 木は、根の直下に $a_1$（長さ 1）、$a_2$（長さ 1）、確率 $0.5$ の節点があり、その下に $a_3,a_4$（長さ 2）と確率 $0.2$ の節点（$a_5,a_6$ が長さ 3）。
$L=0.3\cdot 1+0.2\cdot 1+0.15\cdot 2\cdot 2+0.1\cdot 3\cdot 2=0.5+0.6+0.6=1.7$。
別の併合（同確率 $0.2$ のうち $a_2$ を選ぶ）でも $L=0.3+0.4+1.0=1.7$ で一致。

なお、エントロピー下界 $H_3\approx 1.5$ 程度より大きく、整合。