本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

平成28年度 春期 高度情報技術者試験問題と解説

問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 │
 └─┴───┴───┴───┴───┘


正解


解説

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

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

ア 000 と続いた場合、acか caか区別できない。

イ 010 の場合、acか baか区別できない。

ウ 正しい。一文字の平均ビット長は
1×50% + 2×30% + 3×10% + 3×10% = 1.7

エ 一意に復元できるが、平均ビット長は2ビットである。

問1 目次 問3