ａ、ｂ、ｃ、ｄの4文字からなるメッセージを符号化してビット列にする方法として表のア〜エの4通りを考えた。この表はａ、ｂ、ｃ、ｄの各1文字を符号化するときのビット列を表している。メッセージ中でのａ、ｂ、ｃ、ｄの出現頻度は、それぞれ50%、30%、10%、10%
であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって、ビット列の長さが最も短くなるものはどれか。
┌───┬───┬───┬───┐
│ ａ │ ｂ │ ｃ │ ｄ │
┌─┼───┼───┼───┼───┤
│ア│ ０ │ １ │ ００ │ １１ │
├─┼───┼───┼───┼───┤
│イ│ ０ │ ０１ │ １０ │ １１ │
├─┼───┼───┼───┼───┤
│ウ│ ０ │ １０ │１１０│１１１│
├─┼───┼───┼───┼───┤
│エ│ ００ │ ０１ │ １０ │ １１ │
└─┴───┴───┴───┴───┘
ウ
ハフマン符号は出現頻度の高い文字には短いビット列を、出現頻度の低い文字には長いビット列を割り当てることで全体のデータ量を圧縮する方法である。
0、10、110、1110、11110、11111のように最も出現頻度の低い文字にはオール1を割り当てる。
ア 000 と続いた場合、 acか caか区別できない。
イ 010 の場合、 acか baか区別できない。
ウ 正しい。一文字の平均ビット長は
1×50% + 2×30% ＋ 3×10% ＋ 3×10% ＝ 1.7
エ 一意に復元できるが、平均ビット長は2ビットである。
| 問１ | 目次 | 問３ |