九大 システム情報科学府 情報理工学専攻 専門科目（情報系4分野） 2024年度 院試 過去問 解答例・解説（全4問）

瞬時復号可能符号とハフマン符号

2元瞬時復号可能符号では、符号語長 $\ell_i$ が Kraft 不等式 $$\sum_i2^{-\ell_i}\le1$$ を満たす必要十分条件である。

長さ $3,3,3,2,2,2$ の場合は $$3\cdot2^{-3}+3\cdot2^{-2}=\frac38+\frac34=\frac98>1$$ なので不可能である。長さ $3,3,3,3,2,2$ の場合は $$4\cdot2^{-3}+2\cdot2^{-2}=\frac12+\frac12=1$$ なので可能であり、例えば $$00,\ 01,\ 100,\ 101,\ 110,\ 111$$ を割り当てればよい。

確率 $$0.30,\ 0.20,\ 0.18,\ 0.13,\ 0.11,\ 0.08$$ に対するハフマン符号の一例は $$\begin{array}{c|c|c} \text{記号}&\text{確率}&\text{符号語}\\ \hline s_3&0.30&10\\ s_2&0.20&01\\ s_1&0.18&111\\ s_4&0.13&110\\ s_5&0.11&001\\ s_6&0.08&000 \end{array}$$ である。平均符号長は $$0.30\cdot2+0.20\cdot2+(0.18+0.13+0.11+0.08)\cdot3=2.50.$$

KLダイバージェンス最小化

$q$ を $p_1,p_2$ の重み付き平均として $$q=\alpha p_1+(1-\alpha)p_2 =\bigl(\alpha,(1-\alpha)b,(1-\alpha)(1-b)\bigr)$$ とおく。$u=(1/3,1/3,1/3)$ に対し $$D(u\|q)=\sum_{x}\frac13\log\frac{1/3}{q(x)}$$ である。定数を除けば、これは $$-\frac13\log\{\alpha(1-\alpha)^2b(1-b)\}$$ を最小にする問題である。$b$ は固定なので $$\alpha(1-\alpha)^2$$ を最大にすればよい。微分すると $$(1-\alpha)(1-3\alpha)=0$$ より、内部解は $\alpha=1/3$。したがって $$q=\left(\frac13,\frac{2b}{3},\frac{2(1-b)}{3}\right).$$