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

平均符号長を最小にする 3 元瞬時符号は、3 元ハフマン符号で得られる。

ダミー記号の追加. $D$ 元のハフマン符号では、毎回 $D$ 個を 1 個にまとめると記号数が $D-1$ ずつ減るので、最後にちょうど 1 個になるには記号数 $n$ が $n\equiv 1(\mathrm{mod}D-1)$ を満たす必要がある。$D=3$ では $n$ が奇数でなければならないが、$n=6$ なので確率 $0$ のダミー記号を 1 個加えて 7 個にする。（クラフトの不等式 $\sum 3^{-{\ell }_i}\le 1$ の観点では、6 個の符号語だけでは 3 分木の葉を埋め尽くせず、余る葉が 1 つ出ることに対応する。）

確率を $\frac{1}{20}$ 単位で表すと $6,4,3,3,2,2,0$ である。

ハフマンの手順.
1. 小さい 3 つ $0,2,2$ をまとめて $4$。残り: $6,4,4,3,3$。
2. 小さい 3 つ $3,3,4$ をまとめて $10$。残り: $10,6,4$。
3. 残り 3 つ $10,6,4$ をまとめて $20$（根）。

手順 2 で $4$ が 2 つあるが、どちらを選んでも平均符号長は同じである。例えば手順 1 でできた $4$ を選ぶと、符号長は
$$a_1:1,a_2:1,a_3:2,a_4:2,a_5:3,a_6:3$$
となる（クラフトの和は $\frac{1}{3}+\frac{1}{3}+\frac{1}{9}+\frac{1}{9}+\frac{1}{27}+\frac{1}{27}=\frac{26}{27}\le 1$ で、ダミーの葉 $\frac{1}{27}$ を加えるとちょうど $1$）。平均符号長は
$$\frac{6\cdot 1+4\cdot 1+3\cdot 2+3\cdot 2+2\cdot 3+2\cdot 3}{20}=\frac{34}{20}=\frac{17}{10}.$$
（もう一方の選び方では符号長 $1,2,2,2,2,2$ となり、$\frac{6+8+6+6+4+4}{20}=\frac{34}{20}$ で同じ値になる。また、平均符号長は内部節点の重みの和 $\frac{4+10+20}{20}$ としても求められる。）

よって最小の平均符号長は $\frac{17}{10}$ である。

（参考: 2 を底とするエントロピーは $H_2(X)\approx 0.521+0.464+0.821+0.664\approx 2.471$ で、3 元エントロピーは $H_3(X)=\frac{H_2(X)}{{\log }_{2}3}\approx \frac{2.471}{1.585}\approx 1.56$ である。$H_3(X)\le \frac{17}{10}<H_3(X)+1$ を満たしている。）

3 元ハフマン符号が最小平均符号長を与える。記号数 6 は $3$ 元で完全木にならない（$n\equiv 1(\mathrm{mod}2)$ が必要）ので、確率 0 のダミー記号を 1 つ加えて 7 記号とする。確率を $1/20$ 単位で表すと $6,4,3,3,2,2,0$。

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

平均符号長は併合で作られた内部節点の確率の総和に等しいので $(4+10+20)/20=34/20=17/10$。

確認: 符号長は $a_1:1,a_2:1,a_3:2,a_4:2,a_5:3,a_6:3$（またはどちらの 4 を併合しても総和は同じ）。クラフトの不等式: $3\cdot 3^{-1}\to$ $2\cdot 3^{-1}+2\cdot 3^{-2}+2\cdot 3^{-3}=\frac{18+6+2}{27}=\frac{26}{27}\le 1$。平均長 $=(6\cdot 1+4\cdot 1+3\cdot 2+3\cdot 2+2\cdot 3+2\cdot 3)/20=34/20=17/10$。

3 元エントロピーは約 $1.6$ 台で下界 $H_3(X)\le 1.7<H_3(X)+1$ とも矛盾しない。