情報に関する理論 (全39問中11問目)
No.11
a，b，c，d の4文字からなるメッセージを符号化してビット列にする方法として表のア〜エの4通りを考えた。この表は a，b，c，d の各1文字を符号化するときのビット列を表している。メッセージ中の a，b，c，d の出現頻度は，それぞれ，50%，30%，10%，10% であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって，ビット列の長さが最も短くなるものはどれか。
出典：平成28年春期 問4
- [この問題の出題歴]
- 応用情報技術者 H22秋期 問2
- ソフトウェア開発技術者 H18春期 問7
分類
テクノロジ系 » 基礎理論 » 情報に関する理論
正解
ウ
解説
最小ビットで圧縮できる方式を考える前に、各方式が符号化された文字列から元の文字列を一意に復号可能かを検証し、条件を満たす方式についてだけビット数を計算します。
- 文字列bb(11)と、d(11)の区別がつかず一意の復号は不可能です。
- abc(00110)と、aada(00110)の区別がつかず一意の復号は不可能です。
- 並べてみるとわかりますが、一意の復号が可能です。
一文字を表現するのに必要な平均ビットは、各文字の出現頻度を考慮して計算すると、
(1×0.5)＋(2×0.3)＋(3×0.1)＋(3×0.1)
＝0.5＋0.6＋0.3＋0.3＝1.7
となり4つの中では、復号可能かつビット列の長さが最も短くなる方法となります。 - 各ビットが2ビットずつで一意の復号が可能です。
一文字を表現するのに必要な平均ビットは2ビットなので、「ウ」の方式よりはビット列が長くなります。