アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20211212 実施分 問6
a，b，c，d の 4 文字から成るメッセージを符号化してビット列にする方法として表のア～エの 4 通りを考えた。この表は a，b，c，d の各 1 文字を符号化するときのビット列を表している。メッセージ中での a，b，c，d の出現頻度は，それぞれ 50%，30%，10%，10%であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって，ビット列の長さが最も短くなるものはどれか。
| a | b | c | d | |
|---|---|---|---|---|
| ア | 0 | 1 | 00 | 11 |
| イ | 0 | 01 | 10 | 11 |
| ウ | 0 | 10 | 110 | 111 |
| エ | 00 | 01 | 10 | 11 |
- ア a:0，b:1，c:00，d:11
- イ a:0，b:01，c:10，d:11
- ウ a:0，b:10，c:110，d:111
- エ a:00，b:01，c:10，d:11
出典：基本情報技術者試験 科目A免除 修了試験 20211212 実施分 問6
答えと解説を見る
正解：ウ
覚える知識
符号の平均ビット数計算
一意復号可能な符号は、どの符号語も他の符号語の接頭辞にならず、出現頻度の高い文字ほど短くすると平均長が短くなる。
この問題で必要なこと
一意復号可能(語頭条件を満たす)なのはイ(不可)・ウ・エ。平均長はウ=0.5×1+0.3×2+0.1×3+0.1×3=1.7、エ=2で、ウが最短。
ひっかけ
ア・イは接頭辞関係があり復号が一意に定まらないのに、短さだけで選ばせる。
この知識の出題：本試験系 1 回・免除試験 4 回（公開問題での観測値）