情報処理安全確保支援士試験 情報セキュリティスペシャリスト試験 平成28年度春期 午前Ⅰ 問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，1，00，11
• イ.0，01，10，11
• ウ.0，10，110，111
• エ.00，01，10，11

正解

ウ. 0，10，110，111

解説

一意復号には語頭符号(どの符号も他の符号の接頭辞でない)であることが必要。アとイは0が他語の先頭になり境界が曖昧で復号不能。残るウとエのうち、平均符号長は出現頻度で重み付けして比較する。ウは0.5×1+0.3×2+0.1×3+0.1×3=1.7ビットで、固定2ビットのエより短い。これはハフマン符号の考え方で、頻度の高い文字に短い符号を割り当て圧縮効率を高める。

選択肢ごとの解説

• ア.aの0がcの00やbの1と区別できず一意に復号できないため誤り。
• イ.aの0がbの01やcの10の先頭と重なり境界が定まらず復号不能で誤り。
• ウ.語頭符号で一意復号可能、平均長1.7ビットと最短になるため正解。
• エ.一意復号は可能だが全て2ビット固定で平均2ビットとウより長く誤り。