令和2年度秋期 応用情報技術者試験 午前 問4
a，b，c，dの4文字から成るメッセージを符号化してビット列にする方法として表のア〜エの4通りを考えた。この表はa，b，c，dの各1文字を符号化するときのビット列を表している。メッセージ中でのa，b，c，dの出現頻度は，それぞれ50％，30％，10％，10％であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって，ビット列の長さが最も短くなるものはどれか。
※選択肢ア〜エは上の図表内に記載されています。
解答・解説を見る
正解：ウ
AI解説
一意に復号可能な符号(語頭符号・接頭符号)であって期待符号長が最小になるのは、出現頻度が高い文字ほど短い符号を割り当てるハフマン符号の考え方に沿った符号表である。頻度50％，30％，10％，10％の場合、最適な符号長は1,2,3,3ビットとなり、期待符号長は0.5×1＋0.3×2＋0.1×3＋0.1×3＝1.7ビットで最小になる。 ア: 図中の選択肢アは一意に復号可能であっても、出現頻度と符号長の対応が最適でなく期待符号長が最短にならない組合せである。 イ: 図中の選択肢イは、語頭符号の条件(他の符号の前置にならない)を満たさず一意に復号できない、又は符号長の割当てが非効率な組合せである。 ウ: 正しい。図中の選択肢ウは一意に復号可能な語頭符号であり、出現頻度の高い文字に短い符号を割り当てているため期待符号長が最短になる。 エ: 図中の選択肢エは一意に復号可能であっても符号長の割当てが非効率で、期待符号長が最短にならない組合せである。 💡 ハフマン符号の原則「出現頻度が高い文字ほど短い符号を割り当てる」と、一意復号のための「語頭符号(どの符号も他の符号の前置にならない)」という2条件を押さえておく。
出典：令和2年度 秋期 応用情報技術者試験 午前 問4 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。