解説
一意に復号可能で、かつ平均ビット長が最も短い符号化を選ぶ問題です。まず一意に復号可能であるためには、ある符号語が別の符号語の接頭辞（先頭部分）になっていない「語頭符号（プレフィックス符号）」である必要があります。各選択肢を確認します。アは a＝0 が c＝00 の接頭辞、イは a＝0 が b＝01 の接頭辞になっており、いずれも一意に復号できません。ウ（a＝0，b＝10，c＝110，d＝111）とエ（a＝00，b＝01，c＝10，d＝11）は語頭符号で一意に復号可能です。次に平均ビット長を出現頻度（a50%，b30%，c10%，d10%）で計算します。ウは 0.5×1＋0.3×2＋0.1×3＋0.1×3＝1.7ビット、エは全て2ビットなので 2.0ビットです。一意に復号可能で平均長が最短なのはウ（1.7ビット）であり、選択肢cが正解です。出現頻度の高い文字に短い符号を割り当てるハフマン符号の考え方が活きています。
なぜ他の選択肢は違うのか
- 選択肢 ア
- ア（a＝0，b＝1，c＝00，d＝11）は一意に復号できません。符号語 a＝0 が c＝00 の接頭辞に、b＝1 が d＝11 の接頭辞になっているため、例えばビット列「00」が「a a」なのか「c」なのか区別できず、語頭符号の条件を満たさないため復号が一意に定まりません。ビット列「00」をaを2つ並べた「a a」と読むか、cと読むかが区別できず、復号結果が一意に定まりません。語頭符号の条件を満たさない時点で不適切です。
- 選択肢 イ
- イ（a＝0，b＝01，c＝10，d＝11）も一意に復号できません。符号語 a＝0 が b＝01 の接頭辞になっているため、ビット列の先頭の「0」を a と読むか b の一部と読むかが区別できません。語頭符号の条件を満たさず、平均ビット長を比較する以前に復号が一意に定まりません。符号語の先頭にある「0」を、aと読むかbの一部と読むかが区別できず、復号が一意に定まりません。平均ビット長を比較するまでもなく、語頭符号の条件を満たしません。
- 選択肢 エ
- エ（a＝00，b＝01，c＝10，d＝11）は語頭符号で一意に復号可能ですが、全ての符号語が2ビット固定なので平均ビット長は2.0ビットです。語頭符号のウは出現頻度の高い a に1ビットを割り当てており平均1.7ビットと短いため、最短という条件ではウに劣ります。全ての符号語が2ビット固定なので平均ビット長は一律2.0ビットです。出現頻度の高いaに1ビットを割り当てるウ（平均1.7ビット）より長く、最短という条件で劣ります。