平成28年度 春期 応用情報技術者試験 午前 問4
テクノロジ／基礎理論a，b，c，dの4文字から成るメッセージを符号化してビット列にする方法として表のア～エの4通りを考えた。この表はa，b，c，dの各1文字を符号化するときのビット列を表している。メッセージ中でのa，b，c，dの出現頻度は，それぞれ50%，30%，10%，10%であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって，ビット列の長さが最も短くなるものはどれか。 （注：本サイトでは原問題の表を文字表記に変換しています）
出典：平成28年度 春期 応用情報技術者試験 午前 問4
- アa＝0，b＝1，c＝00，d＝11
- イa＝0，b＝01，c＝10，d＝11
- ウa＝0，b＝10，c＝110，d＝111
- エa＝00，b＝01，c＝10，d＝11
正解：ウ
解説
一意に復号可能であるためには符号がどの符号語も他の符号語の先頭部分（接頭語）にならない必要があります。選択肢ウの符号（a＝0，b＝10，c＝110，d＝111）は接頭語条件を満たすハフマン符号であり，平均符号長は0.5×1＋0.3×2＋0.1×3＋0.1×3＝1.7ビットと最も短くなります。
選択肢ごとの解説
- ア誤り。a＝0がc＝00の先頭部分になっており，一意に復号できません。
- イ誤り。a＝0がb＝01の先頭部分になっており，一意に復号できません。
- ウ正しい。接頭語条件を満たし，かつ出現頻度に応じて短い符号を割り当てているため，一意に復号可能で平均符号長が最短（1.7ビット）になります。
- エ誤り。固定長2ビットの符号で一意に復号可能ですが，平均符号長は2ビットとなり，ウの1.7ビットより長くなります。