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