問題プレビューID: b4abe90e応用情報技術者試験 2016年(平成28年度)春期 午前

問 4
応用情報技術者試験 2016年(平成28年度)春期 午前

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

abcd
ア010011
イ0011011
ウ010110111
エ00011011
解説

正解は「ウ」です。

出現頻度の高い文字には短い符号,低い文字には長い符号を割り当てると,ビット列の長さを短くできます。ただし,一意に復号できるように,どの符号も他の符号の接頭辞にならない(前置符号である)必要があります。

  • ウ: a=0,b=10,c=110,d=111 は前置符号であり,平均符号長は 0.5×1+0.3×2+0.1×3+0.1×3=1.70.5 \times 1 + 0.3 \times 2 + 0.1 \times 3 + 0.1 \times 3 = 1.7 ビットで最も短くなります。
  • ア: a=0 と c=00 では,「0」が「00」の接頭辞となるため一意に復号できません。
  • イ: a=0 と b=01 では,「0」が「01」の接頭辞となるため一意に復号できません。
  • エ: すべて長さ 2 なので平均符号長は 2 ビットとなり,ウより長くなります。

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

関連問題

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