AP 令和2年度秋期問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

解答・解説

解答

　ウ

解説

　ハフマン符号に関する問題です。

a：0　b：1　c：00　d：11　
“00”という符号が、“aa”なのか“c”なのか区別できず復号できません。
（同様に“11”も、“bb”なのか“d”なのか区別できず復号できません。）
a：0　b：01　c：10　d：11　
“0110”という符号が、“ada”なのか“bc”なのか区別できず復号できません。
a：0　b：10　c：110　d：111　
復号可能です。なお、1文字あたりの平均ビット長さは
1 × 0.5 + 2 × 0.3 + 3 × 0.1 + 3 × 0.1 = 1.7[ビット]
になります。
a：00　b：01　c：10　d：11　
2ビット単位の符号のため復号は可能ですが、ウよりもビット列が長くなります。