平成22年 秋期 応用情報技術者 午前 問2

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


答え ウ


解説

 ア  この規則だと“aa”を符号化すると“00”になり、これは“c”との区別ができず、復号できないので符号化のルールが条件に合わない。
 イ  この規則だと“ba”を符号化すると“010”になり、これは“ac”との区別ができず、復号できないので符号化のルールが条件に合わない。
 ウ  この符号化ルールは問題ないので、ビット列の平均値を求めると出現頻度は、a:長さ1×50%、b:長さ2×30%、c:長さ3×10%、d:長さ3×10%なので、0.5+0.6+0.3+0.3=1.7である。
 エ  この符号化ルールは問題ないので、ビット列の平均値を求めると出現頻度は、a:長さ2×50%、b:長さ2×30%、c:長さ2×10%、d:長さ2×10%なので、1.0+0.6+0.2+0.2=2.0である。
したがって、最も短くなるのはウである。


キーワード
・符号化

キーワードの解説
  • 符号化
    データを一定の規則により、符号(記号)にすることです。
    コンピュータでは数字や英字などを符号にして扱っています。
    ASCIIコードでは“0”は0x30、“A”は0x41、“ ”(スペース)は0x20という符号にします。

もっと、「符号化」について調べてみよう。

戻る 一覧へ 次へ