この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

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

難易度 4大学院入試の標準レベル大学数学情報理論・符号理論

情報源記号 $a_{1}, a_{2}, \dots, a_{6}$ を、それぞれ確率
$P (a_{1}) = \frac{3}{10}, P (a_{2}) = \frac{1}{5}, P (a_{3}) = P (a_{4}) = \frac{3}{20}, P (a_{5}) = P (a_{6}) = \frac{1}{10}$
で発生する記憶のない情報源がある。各情報源記号に、符号アルファベット ${0, 1, 2}$ の記号列（空でないもの）からなる符号語を $1$ つずつ割り当て、どの符号語もほかの符号語の接頭語にならないようにする（ $3$ 元の瞬時符号）。

このような符号のうち、情報源記号 $1$ 個あたりの平均符号長 $L = i = 1 \sum 6 P (a_{i}) ℓ_{i}$ （ $ℓ_{i}$ は $a_{i}$ の符号語の長さ）の最小値を求めよ。

この問題で使うもの

D 元ハフマン符号（説明と入口の問題）
語頭符号とクラフトの不等式（説明と入口の問題）

この問題を解けるようになるまで（24 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

$3$ 元ハフマン符号を作ります。 $3$ 個ずつまとめる操作で最後にちょうど $3$ 個が残るよう、記号の個数を調整する必要があるか考えましょう。

ヒント 2

$1$ 回まとめるごとに個数は $2$ 減るので、個数が奇数になるように確率 $0$ のダミー記号を $1$ 個加えます。確率を $20$ 倍して $6, 4, 3, 3, 2, 2, 0$ として計算すると楽です。

ヒント 3

1 回目は $0, 2, 2$ をまとめて $4$ 、2 回目は $3, 3, 4$ をまとめて $10$ になります。残り $3$ 個を根でまとめ、各記号の深さ（符号長）を読み取りましょう。

答えと解説

答えを見る

\frac{17}{10}

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

$3$ 元ハフマン符号は、確率の小さい $3$ 個を $1$ つにまとめる操作を繰り返して符号の木を作る。最後にちょうど $3$ 個が残って根でまとまるためには、記号の個数 $M$ が $M \equiv 1 (mod 2)$ を満たす必要がある（ $1$ 回まとめるごとに個数が $2$ ずつ減るから）。 $M = 6$ はこれを満たさないので、確率 $0$ のダミー記号 $a_{0}$ を $1$ 個加えて $7$ 個にする。このとき $3$ 元ハフマン符号は $3$ 元瞬時符号の中で平均符号長が最小になる（ダミー記号は確率 $0$ なので平均符号長に寄与しない）。

計算しやすいように確率を $20$ 倍した重みで書くと、
$a_{1} : 6, a_{2} : 4, a_{3} : 3, a_{4} : 3, a_{5} : 2, a_{6} : 2, a_{0} : 0.$

1 回目. 小さい $3$ 個 $a_{0} (0), a_{5} (2), a_{6} (2)$ をまとめて重み $4$ の節点 $b_{1}$ を作る。残りは $6, 4, 3, 3, 4$ 。

2 回目. 小さい $3$ 個 $a_{3} (3), a_{4} (3)$ と重み $4$ の $1$ 個（ $a_{2}$ または $b_{1}$ 。どちらを選んでも平均符号長は同じ）をまとめて重み $10$ の節点 $b_{2}$ を作る。ここでは $a_{2}$ を選ぶ。残りは $a_{1} (6), b_{1} (4), b_{2} (10)$ 。

3 回目. 残った $3$ 個をまとめて根（重み $20$ ）とする。

符号長は、根からの深さとして
- $a_{1}$ ：深さ $1$ 、 $ℓ_{1} = 1$
- $b_{1}$ が深さ $1$ なので $a_{5}, a_{6}$ ： $ℓ_{5} = ℓ_{6} = 2$
- $b_{2}$ が深さ $1$ なので $a_{2}, a_{3}, a_{4}$ ： $ℓ_{2} = ℓ_{3} = ℓ_{4} = 2$

となる。たとえば $a_{1} \mapsto 0$ , $a_{5} \mapsto 10$ , $a_{6} \mapsto 11$ , $a_{2} \mapsto 20$ , $a_{3} \mapsto 21$ , $a_{4} \mapsto 22$ （ $12$ はダミー記号用で使わない）とすればよい。クラフトの不等式を確かめると
$3^{- 1} + 5 \cdot 3^{- 2} = \frac{3}{9} + \frac{5}{9} = \frac{8}{9} \leq 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} .$

（別の確かめ方）平均符号長は、作った内部節点の重みの和を全体の重みで割ったものに等しい： $\frac{4 + 10 + 20}{20} = \frac{17}{10}$ 。2 回目で $b_{1}$ を選んだ場合も内部節点の重みは $4, 10, 20$ で変わらないので、最小値は $\frac{17}{10}$ である。

（参考）エントロピーによる下界は
$H_{3} (X) = - i = 1 \sum 6 P (a_{i}) lo g_{3} P (a_{i}) = \frac{H _{2} ( X )}{lo g _{2} 3} \approx \frac{2.471}{1.585} \approx 1.56$
で、 $L = 1.7 \geq H_{3} (X)$ と矛盾しない。

別解

3 元の最適な瞬時符号は 3 元ハフマン符号。記号数 6 は偶数なので、確率 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 = \frac{34}{20} = \frac{17}{10}$ 。

符号長: $a_{1}, a_{2}$ は 1、 $a_{3}, a_{4}$ は 2、 $a_{5}, a_{6}$ は 3。 $L = (6 + 4 + 3 \cdot 2 + 3 \cdot 2 + 2 \cdot 3 + 2 \cdot 3) /20 = 34/20 = 1.7$ 。クラフト和 $= 2/3 + 2/9 + 2/27 = 26/27 \leq 1$ で成立。

下界の確認: エントロピー（3 を底）は約 $1.5$ 程度で、 $L = 1.7$ はこれ以上であり矛盾しない。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題