情報処理安全確保支援士試験 情報処理安全確保支援士試験 令和2年度 午前Ⅰ 問2: a，b，c，d の 4 文字から成るメッセージを符号化してビット列にする方法として表のア〜エの 4 通りを考えた。この表は a，b，c，d の各 1 文字を符号

問題本文

a，b，c，d の 4 文字から成るメッセージを符号化してビット列にする方法として表のア〜エの 4 通りを考えた。この表は a，b，c，d の各 1 文字を符号化するときのビット列を表している。メッセージ中での a，b，c，d の出現頻度は，それぞれ 50％，30％，10％，10％であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって，ビット列の長さが最も短くなるものはどれか。

選択肢

• ア.ア
• イ.イ
• ウ.ウ
• エ.エ

正解

ウ. ウ

解説

瞬時に復号できる符号は、どの符号語も他の符号語の接頭辞にならない接頭符号である必要がある。アとイは0が他語の先頭と重なり一意復号できない。エは全て2ビットで一意だが平均長は2.0。ウは出現頻度の高いaを短い符号にしたハフマン符号で、平均長=0.5×1+0.3×2+0.1×3+0.1×3=1.7と最短になる。出現確率に応じ符号長を変えるのが効率化の要点。

選択肢ごとの解説

• ア.a=0,c=00のように0が接頭辞となり境界が判別できず、一意に復号できないため不適。
• イ.a=0がb=01などの接頭辞となり接頭符号にならず、一意復号できないため不適。
• ウ.接頭符号かつ頻度の高い文字を短くしたハフマン符号で、平均長1.7ビットと最短になり正しい。
• エ.一意復号は可能だが全文字2ビットで平均長2.0となり、ウより長く最短ではない。