平成28年度 春期
応用情報技術者試験問題と解答
問4
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 │
      └─┴──┴──┴──┴──┘



【正解】 ウ
ハフマン符号は出現頻度の高い文字には短いビット列を、
出現頻度の低い文字には長いビット列を割り当てることで
全体のデータ量を圧縮する方法である。

0、10、110、1110、
1111011111のように最も出現頻度の
低い文字にはオール1を割り当てる。

ア 000 と続いた場合、 acか caか区別できない。
イ 010 の場合、 acか baか区別できない。
ウ 正しい。一文字の平均ビット長は
 1×50% + 2×30% + 3×10% + 3×10% = 
1.7
エ 一意に復元できるが、平均ビット長は2ビット。



問3 目次 問5
ファーストマクロ TOPページ