問題プレビューID: 103b7dc2応用情報技術者試験 2010年(平成22年度)秋期 午前

問 2
応用情報技術者試験 2010年(平成22年度)秋期 午前

a,b,c,d の 4 文字からなるメッセージを符号化してビット列にする方法として表のア〜エの 4 通りを考えた。この表は,a,b,c,d の各 1 文字を符号化するときのビット列を表している。メッセージ中での a,b,c,d の出現頻度は,それぞれ 50%,30%,10%,10% であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって,ビット列の長さが最も短くなるものはどれか。

解説

正解は「ウ」です。

符号化されたビット列から元のメッセージを一意に復号するには,どの符号も他の符号の先頭部分(接頭語)になっていないこと(接頭符号であること)が必要です。

  • ア: a の符号 0 が c の符号 00 の先頭部分になっているため,一意に復号できません。
  • イ: a の符号 0 が b の符号 01 の先頭部分になっているため,一意に復号できません。
  • エ: どの符号も接頭符号の条件は満たしますが,すべて 2 ビット固定長なので,1 文字当たりの平均ビット数は 2 となります。
  • ウ: 接頭符号の条件を満たし,出現頻度の高い文字ほど短い符号を割り当てているため,1 文字当たりの平均ビット数は 1×0.5+2×0.3+3×0.1+3×0.1=1.71 \times 0.5 + 2 \times 0.3 + 3 \times 0.1 + 3 \times 0.1 = 1.7 ビットとなり,最も短くなります。

よって,正解は「ウ」です。

関連問題

本文が同じ・似ている問題を表示しています