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

確率を分母 $20$ にそろえると、$a_1,\dots ,a_6$ の確率は $\frac{6}{20},\frac{4}{20},\frac{3}{20},\frac{3}{20},\frac{2}{20},\frac{2}{20}$ である。以下、分子だけで書く。

ハフマン符号は、確率の最も小さい $2$ つを $1$ つにまとめる操作をくり返して構成する。

1. 最小の $2$ と $2$（$a_5,a_6$）をまとめて $4$ とする。残りは $6,4,3,3,4$。
2. 最小の $3$ と $3$（$a_3,a_4$）をまとめて $6$ とする。残りは $6,4,4,6$。
3. 最小の $4$ と $4$（$a_2$ と手順 1 でまとめたもの）をまとめて $8$ とする。残りは $6,6,8$。
4. 最小の $6$ と $6$（$a_1$ と手順 2 でまとめたもの）をまとめて $12$ とする。残りは $8,12$。
5. $8$ と $12$ をまとめて $20$（根）とする。

根から見た深さが符号長になる。手順 5 で根の子になるのは「$8$」と「$12$」（深さ $1$）。
- 「$8$」の子は $a_2$（深さ $2$）と手順 1 のまとまり（深さ $2$）で、その子 $a_5,a_6$ は深さ $3$。
- 「$12$」の子は $a_1$（深さ $2$）と手順 2 のまとまり（深さ $2$）で、その子 $a_3,a_4$ は深さ $3$。

よって符号長は $a_1:2,a_2:2,a_3:3,a_4:3,a_5:3,a_6:3$ である（例: $a_1=10,a_2=00,a_3=110,a_4=111,a_5=010,a_6=011$）。クラフトの不等式の左辺は $2\cdot 2^{-2}+4\cdot 2^{-3}=1$ で、等号が成り立っている。

平均符号長は
$$L=\frac{6\cdot 2+4\cdot 2+3\cdot 3+3\cdot 3+2\cdot 3+2\cdot 3}{20}=\frac{12+8+9+9+6+6}{20}=\frac{50}{20}=\frac{5}{2}.$$

（同じ確率のものが複数あるときのまとめ方の選び方によって符号語は変わりうるが、ハフマン符号の平均符号長は最小値なので選び方によらない。）

答えは $\frac{5}{2}$ である。

確率を 20 分の 1 を単位にして並べると $6,4,3,3,2,2$。ハフマン法で最小の 2 つを順に併合する。
1. $2+2=4$ → 残り $6,4,3,3,4$
2. $3+3=6$ → 残り $6,4,4,6$
3. $4+4=8$ → 残り $6,6,8$
4. $6+6=12$ → 残り $8,12$
5. $8+12=20$（根）
平均符号長は併合で作られた内部節点の確率の総和に等しい（各併合で、その節点より下の記号の符号長が 1 ずつ増えるため）。よって
$$L=\frac{4+6+8+12+20}{20}=\frac{50}{20}=\frac{5}{2}.$$
検算: 具体的な符号長は、$a_1(6)$: 2、$a_2(4)$: 2、$a_3(3)$: 3、$a_4(3)$: 3、$a_5(2)$: 3、$a_6(2)$: 3 のように得られる（併合の木から）。ただし実際には $a_1$ は $6+6=12$ の側に入るか確認が必要なので数え直す。木: 根 $=8+12$。$8=4_{(a_2)}+4_{(a_5+a_6)}$、$12=6_{(a_1)}+6_{(a_3+a_4)}$。よって長さは $a_1:2,a_2:2,a_3:3,a_4:3,a_5:3,a_6:3$ で
$$L=\frac{6\cdot 2+4\cdot 2+3\cdot 3+3\cdot 3+2\cdot 3+2\cdot 3}{20}=\frac{12+8+9+9+6+6}{20}=\frac{50}{20}=\frac{5}{2}.$$
一致する。同順位の選び方が複数あっても、ハフマン符号の平均符号長は一意に定まる。