令和2年度 10月 応用情報技術者試験 午前 問4
テクノロジ／基礎理論a，b，c，d の 4 文字から成るメッセージを符号化してビット列にする方法として表のア〜エの 4 通りを考えた。この表は a，b，c，d の各 1 文字を符号化するときのビット列を表している。メッセージ中での a，b，c，d の出現頻度は，それぞれ 50％，30％，10％，10％であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって，ビット列の長さが最も短くなるものはどれか。 （注：本サイトでは原問題の表を文字表記に変換しています）
出典：令和2年度 10月 応用情報技術者試験 午前 問4
- ア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
正解：ウ
解説
一意に復号可能であるためには，ある符号語が別の符号語の接頭部になっていない（語頭条件を満たす）ことが十分条件になります。ウの 0，10，110，111 は語頭条件を満たし，平均ビット長は 0.5×1＋0.3×2＋0.1×3＋0.1×3＝1.7 ビットで最短です。
選択肢ごとの解説
- ア誤り。a＝0，c＝00 のように 0 が 00 の接頭部になっており，ビット列 00 が aa とも c とも読めるため一意に復号できません。
- イ誤り。ビット列 010 が a・c（0，10）とも b・a（01，0）とも読めるため，一意に復号できません。
- ウ正しい。語頭条件を満たすので一意に復号でき，平均ビット長は 1.7 ビットでエの 2 ビットより短くなります。
- エ誤り。全て 2 ビットの固定長で一意に復号はできますが，平均ビット長が 2 ビットとなり，ウの 1.7 ビットより長くなります。