平成30年度 秋期 基本情報技術者試験 午前 問4
テクノロジ／基礎理論出現頻度の異なるA，B，C，D，Eの5文字で構成される通信データを，ハフマン符号化を使って圧縮するために，符号表を作成した。aに入る符号として，適切なものはどれか。 文字：出現頻度（%）：符号 A：26：00 B：25：01 C：24：10 D：13：a E：12：111 （注：本サイトでは原問題の表を文字表記に変換しています）
出典：平成30年度 秋期 基本情報技術者試験 午前 問4
- ア001
- イ010
- ウ101
- エ110
正解：エ
解説
ハフマン符号は，出現頻度が低い文字ほど長い符号を割り当て，かつどの符号も他の符号の前置き（プレフィックス）にならないように構成します。A，B，Cにはそれぞれ2ビットの符号00，01，10が割り当てられており，Eには3ビットの符号111が割り当てられています。残るDの符号は，00，01，10のいずれの前置きにもならず，かつ111とは別の3ビットの符号でなければならないので，110が適切です。
選択肢ごとの解説
- ア誤り。001は先頭の00がAの符号00と一致し，Aの符号の前置きになってしまうため使用できません。
- イ誤り。010は先頭の01がBの符号01と一致し，Bの符号の前置きになってしまうため使用できません。
- ウ誤り。101は先頭の10がCの符号10と一致し，Cの符号の前置きになってしまうため使用できません。
- エ正しい。110はA，B，Cのどの符号の前置きにもならず，Eの符号111とも重複しない3ビットの符号なので，Dに割り当てることができます。