応用情報技術者 2020年 秋期 午前2 問04

一意復号可能符号【午前2解説】

正解の理由

解法ステップ

1. 「一意復号可能か」をまず判定する。プレフィックス符号（どのコード語も他のコード語の接頭辞にならない）なら自動的に一意復号可能。
2. プレフィックス性を満たさない場合は、具体的なビット列で復号の曖昧性（複数の分割が可能か）を探す。見つかればその符号は不適。
3. 一意復号可能と判定された候補について平均符号長 $L=\sum p_i{l}_i$ を計算する。
4. 平均符号長が最小のものを選ぶ。

選択肢別の誤答解説

• ア（a:0, b:1, c:00, d:11）
  • 長さ：a=1,b=1,c=2,d=2 → 平均 $L=0.5\times 1+0.3\times 1+0.1\times 2+0.1\times 2=1.2$（短い）が、a=0 が c=00 の接頭辞になっているためプレフィックス性を満たさず、一意復号可能ではありません。実際にビット列 00 は「c」か「a」「a」のどちらの並びとも解釈でき、復号が曖昧になります（例："c" ⇔ "aa"）。
• イ（a:0, b:01, c:10, d:11）
  • 長さ：a=1,b=2,c=2,d=2 → 平均 $L=0.5\times 1+0.3\times 2+0.1\times 2+0.1\times 2=1.5$（短い）が、a=0 と b=01 の関係によりプレフィックス性を欠き、一意復号可能ではありません。具体例としてビット列 010 は次のように二通りに解釈できます：01|0 = b a、または 0|10 = a c。よって曖昧です。
• ウ（a:0, b:10, c:110, d:111） ← 有効かつ最短
  • 長さ：a=1,b=2,c=3,d=3。すべての符号語が互いに接頭辞になっていない（プレフィックス符号）ため一意復号可能。平均 $L=1.7$。この集合はハフマン符号の結果と一致し、与えられた確率で最適な（平均長が最短の）プレフィックス符号です。
• エ（a:00, b:01, c:10, d:11）
  • 長さすべて2で平均 $L=2.0$。プレフィックス性を満たすため一意復号可能だが、平均長は ウ より長い。

よくある誤解

• 「非プレフィックスなら必ず一意復号不可能」と思い込む誤り：一般にプレフィックス性がなければ直ちに不適とは限らない（理論上は非プレフィックスでも一意復号可能な例は存在する）が、本問のア・イのように接頭辞関係から具体的な曖昧な分割が作れる場合は明確に一意復号不可能となります。問題では具体的な反例を示して排除するのが確実です。
• 平均符号長だけで選んでしまう誤り：平均長が最小でも、一意復号可能性を満たさない選択肢は不正解です。まず復号可能性を確認してください。
• 算出ミス：確率と各符号語の長さを掛けて足す計算で小数点の扱いを誤るケースが多いので計算は慎重に。

補足コラム

• ハフマン符号は与えられたシンボル確率に対して平均符号長を最小にするプレフィックス符号を構成します。本問でも c,d をまず結合(0.1+0.1=0.2)、次にそれを b(0.3) と結合して 0.5 にし、最後に a(0.5) と結合する手順により、符号長 1,2,3,3 の割当（= ウ）が得られます。
• 情報理論的下限としてエントロピー $H$ があり、今回の確率に対して
  $H=-\sum p_i{\log }_2{p}_i\approx 1.6855\text{[bit]}$
  プレフィックス符号の平均長 $L$ は $H\le L<H+1$ を満たし、ウ の $L=1.7$ はこの範囲内で実用上ほぼ最適です。

FAQ