高度情報処理技術者試験・情報処理安全確保支援士試験 令和2年度 秋期 午前I 問2
a、b、c、dの4文字から成るメッセージを符号化してビット列にする方法として表のア～エの4通りを考えた。この表はa、b、c、dの各1文字を符号化するときのビット列を表している。メッセージ中でのa、b、c、dの出現頻度は、それぞれ50％、30％、10％、10％であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって、ビット列の長さが最も短くなるものはどれか。
選択肢を押すと答え合わせができます。
正解と解説を見る
【正解】ウ
ウでは、a、b、c、dにそれぞれ0、10、110、111を割り当てています。どの符号語も、別の符号語の先頭部分になっていません。この性質を接頭語条件といい、ビット列を左から読むだけで区切りを一意に決められます。例えば、先頭が0ならa、10ならb、110ならc、111ならdです。1文字当たりの平均符号長は、出現頻度を用いて、0.5×1＋0.3×2＋0.1×3＋0.1×3＝0.5＋0.6＋0.3＋0.3＝1.7ビットです。
アは平均1.2ビットですが、一意に復号できないので誤りです。例えば「00」はcとも、aを2文字並べたaaとも解釈できます。「11」もdとbbの区別ができません。
イは平均1.5ビットですが、これも一意に復号できません。ビット列「010」は「01｜0」と区切ればba、「0｜10」と区切ればacとなり、二通りのメッセージに復号できます。
エは全て2ビットの固定長符号なので一意に復号できますが、平均符号長は2ビットです。したがって、一意に復号できるウとエを比較すると、1.7ビットのウが最短です。
【ポイント】 平均符号長は「各文字の出現確率×符号長」の合計で求めます。 短い符号を高頻度の文字に割り当てると、全体を効率よく圧縮できます。 符号長だけでなく、一意に復号できるかを具体的なビット列で確認することが重要です。
出典：令和2年度 秋期 高度情報処理技術者試験・情報処理安全確保支援士試験 午前I 問2
※ 解説は SkillStack 編集部が作成したものです。Web 表示のため、図表の配置や表記を一部改めています。
この回の30問を、アプリで通しで解く
- 本番と同じ問題数・制限時間で通し演習（模試モード）
- 間違えた問題は自動で「復習すべき問題」に回る
- 解説で分からない点はAIに質問できる