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

3 元ハフマン符号を作れば、平均符号長が最小の 3 元語頭符号が得られる。

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

分母を $20$ にそろえると、確率は $$a_1:\frac{8}{20},a_2:\frac{5}{20},a_3:\frac{4}{20},a_4:\frac{3}{20},d:0$$ となる。

手順 2：小さい 3 個をまとめる。 いちばん小さい 3 個は $d(0)$, $a_4(\frac{3}{20})$, $a_3(\frac{4}{20})$ である。これらをまとめて確率 $\frac{7}{20}$ の節点 $b$ を作る。残りは $$a_1:\frac{8}{20},b:\frac{7}{20},a_2:\frac{5}{20}$$ の 3 個である。

手順 3：残った 3 個をまとめる。 この 3 個をまとめると確率 $1$ の根になり、木が完成する。

手順 4：符号語を割り当てる。 根から $a_1$ に $0$、$b$ に $1$、$a_2$ に $2$ を割り当て、$b$ の下で $a_3$ に $0$、$a_4$ に $1$、$d$ に $2$ を割り当てると、$$a_1:0,a_2:2,a_3:10,a_4:11$$ となる（ダミー記号の符号語 $12$ は使わない）。符号長は $l_1=1,l_2=1,l_3=2,l_4=2$ である。

手順 5：平均符号長を計算する。 $$\bar{L}=\frac{8}{20}\cdot 1+\frac{5}{20}\cdot 1+\frac{4}{20}\cdot 2+\frac{3}{20}\cdot 2=\frac{8+5+8+6}{20}=\frac{27}{20}$$

ハフマン符号は平均符号長が最小の語頭符号なので、求める最小値は $\frac{27}{20}$ である。

（参考：ダミーを補わずに $a_4,a_3,a_2$ の 3 個を先にまとめると、根の下に枝が 2 本しか出ず、符号長が $1,2,2,2$ となって $\bar{L}=\frac{8+2(5+4+3)}{20}=\frac{32}{20}$ と大きくなる。）

3 元の語頭符号の最小平均符号長は、3 元ハフマン符号で得られる。記号数 4 は偶数で、3 元の完全木に必要な「1 + 2k 個」にならないので、確率 0 のダミー記号を 1 個加えて 5 個にする。

1. 確率の小さい 3 つ（0, 3/20, 1/5）を合併して 7/20 とする。
2. 残りは 2/5, 1/4, 7/20 の 3 つなので、これらを合併して根とする。

符号語の長さは $l_1=l_2=1$、$l_3=l_4=2$ となる。

$\bar{L}=\frac{2}{5}\cdot 1+\frac{1}{4}\cdot 1+\frac{1}{5}\cdot 2+\frac{3}{20}\cdot 2=\frac{8+5+8+6}{20}=\frac{27}{20}$

検算として、クラフトの不等式から別の長さの組を調べる。長さ 1 の語を 3 個にすると $3/3+1/9>1$ となり、4 つ目の語に長さを割り当てられない。したがって長さ 1 の語は多くても 2 個である。残り 2 個は長さ 2 以上なので、長さ $(1,1,2,2)$ が最適で、$27/20=1.35$ が最小値となる。