一意に復号できる最短の符号
出典: 平成28年度 春期 応用情報技術者試験 午前 問4 (IPA)
a，b，c，d の 4 文字から成るメッセージを符号化してビット列にする方法として表のア～エの 4 通りを考えた。この表は a，b，c，d の各 1 文字を符号化するときのビット列を表している。メッセージ中での a，b，c，d の出現頻度は，それぞれ 50%，30%，10%，10%であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって，ビット列の長さが最も短くなるものはどれか。
- ア ア
- イ イ
- ウ ウ
- エ エ
正解と解説を見る
正解: ウ
- ア: c (00) が aa とも読めるので、一意に復号できません。
- イ: 010 が a と c とも b と a とも読めるので、一意に復号できません。
- ウ: 語頭符号なので一意に復号でき、平均 1.7 ビットで最も短くなるので正しい答えです。
- エ: 一意に復号できますが、平均 2 ビットで、ウ (1.7 ビット) より長くなります。
ポイント
- 一意に復号するには、どの符号も 他の符号の先頭部分になっていない (語頭符号) ことが必要です。
- ア: 00 は c とも aa とも読めます。イ: 010 は a・c (0, 10) とも b・a (01, 0) とも読めます。どちらも一意に復号できません。
- ウとエは一意に復号できるので、平均の長さを比べます。
・ウ: 1 × 0.5 ＋ 2 × 0.3 ＋ 3 × 0.1 ＋ 3 × 0.1 = 1.7 ビット
・エ: 全て 2 ビットなので 2.0 ビット
よって ウ です。