問題プレビューID: aa5847f8基本情報技術者試験 午前免除試験 2021年12月12日

問 6
基本情報技術者試験 午前免除試験 2021年12月12日

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

Label

a

b

c

d

ア

0

1

00

11

イ

0

01

10

11

ウ

0

10

110

111

エ

00

01

10

11

解説

正解は「ウ」です。

一意に復号できるためには,どの符号語も他の符号語の先頭部分(接頭語)になっていないこと(接頭符号であること)が必要です。

  • ア:a の符号語 0 が c の符号語 00 の先頭部分になっているため,一意に復号できません。
  • イ:a の符号語 0 が b の符号語 01 の先頭部分になっているため,一意に復号できません。
  • エ:a,b,c,d の符号語がすべて 2 ビットで接頭符号となっており一意に復号できますが,1 文字当たりの平均ビット数は 0.5×2+0.3×2+0.1×2+0.1×2=20.5 \times 2 + 0.3 \times 2 + 0.1 \times 2 + 0.1 \times 2 = 2 ビットとなり,ウより長くなります。

ウは a = 0,b = 10,c = 110,d = 111 で接頭符号であり,出現頻度の高い文字ほど短い符号語を割り当てています。1 文字当たりの平均ビット数は

0.5×1+0.3×2+0.1×3+0.1×3=1.7 ビット0.5 \times 1 + 0.3 \times 2 + 0.1 \times 3 + 0.1 \times 3 = 1.7 \text{ ビット}

となり,4 通りの中で最も短くなります。したがって「ウ」が正解です。

関連問題

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