応用情報技術者 2016年 春期 午前2 問04

平均符号長と一意復号【午前2解説】

正解の理由

解法ステップ

1. 各選択肢について「一意復号可能か」を判定する。簡易判定として「接頭辞符号（prefix code）か」をまず確認する。接頭辞符号なら必ず一意復号可能。
2. 一意復号可能と判定できた選択肢だけを残す。
3. 残った選択肢について平均符号長 $L=\sum p_i{\ell }_i$ を計算し、最小のものを選ぶ。
4. 必要ならハフマン符号との一致やエントロピーとの比較で妥当性を確認する。

• ア: 長さ = [1,1,2,2] → $L=0.5\times 1+0.3\times 1+0.1\times 2+0.1\times 2=1.2$（ただし一意復号不可）
• イ: 長さ = [1,2,2,2] → $L=1.5$（一意復号不可）
• ウ: 長さ = [1,2,3,3] → $L=1.7$（一意復号可能）
• エ: 長さ = [2,2,2,2] → $L=2.0$（一意復号可能）

選択肢別の誤答解説

• ア（a=0, b=1, c=00, d=11）
  0（a）が 00（c）の接頭になっているため接頭辞符号ではなく、一意復号可能とは限りません。具体例：a+c = 0 + 00 = 000、c+a = 00 + 0 = 000 で同じビット列になり得ます（ac と ca が同じ符号列）。したがって不適。
• イ（a=0, b=01, c=10, d=11）
  表面上短い符号語があるため平均長が小さく見えますが、これも接頭辞条件を満たしていません。具体的な曖昧性の例を示します：a+c = 0 + 10 = 010、一方 b+a = 01 + 0 = 010。よって "010" が ac と ba のどちらとしても解釈でき、これは一意復号不可能です。したがって不適。
• ウ（a=0, b=10, c=110, d=111）
  各符号語は互いに接頭でない（0, 10, 110, 111）ため接頭辞符号であり一意復号可能。与えられた確率に対する平均符号長は 1.7 ビットで、同じ条件下で最小です。ハフマン符号の構築でもこの配列になるため最適性が裏付けられます。
• エ（a=00, b=01, c=10, d=11）
  固定長2ビットで一意復号可能だが平均長は 2.0 ビットと ウ（1.7ビット）より大きいため不適。

よくある誤解

• 「符号語が短いほど良い」は誤り：短い符号語があっても、接頭関係により復号が曖昧になれば使えません。平均長だけでなく一意復号可能性が必要です。
• 「一意復号可能＝接頭辞符号」は不正確：接頭辞符号であれば必ず一意復号可能ですが、逆は必ずしも真ではありません（接頭辞でないが一意復号可能な例も存在します）。ただし実用上は接頭辞符号を用いることが多く判定も簡単です。
• 「短い平均長を示す選択肢は常に正解」は誤り：平均長が小さくても一意復号できなければ無効です（例：アは平均長1.2だが復号不能）。

補足コラム

• ハフマン符号の構築（簡単な流れ）
  1. 出現確率が最も小さい2つ（ここでは c,d の各0.1）を結合して確率0.2の仮想ノードを作る。
  2. 次に確率0.2（c,dの結合）と確率0.3（b）を結合して確率0.5のノードにする。
  3. 最後に残る0.5（a）と0.5（前段の結合）を結合して木を完成。
     これにより各文字の深さ（符号長）が a:1, b:2, c:3, d:3 となり、選択肢は ウ に一致します。
• 情報理論的下限としてのエントロピー $H$：
  $H=-\sum p_i{\log }_2{p}_i\approx 1.6855$ ビット。最適な（可接頭の場合の）平均符号長はエントロピー以上であり、ハフマン符号の平均長 1.7 はこの下限に非常に近い値です。
• 一意復号可能性の厳密判定には Sardinas–Patterson アルゴリズムが使えますが、試験では接頭辞判定と簡単な反例提示で十分です。

FAQ