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