応用情報技術者試験 応用情報技術者試験 令和2年度 午前 問4: 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%であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって，ビット列の長さが最も短くなるものはどれか。

選択肢

• ア.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ビット、エは全て2ビットなので2.0ビット。高頻度の文字に短い符号を割り当てたウのほうが短くなり、正解はウ。

選択肢ごとの解説

• ア.a=0 が c=00 の語頭、b=1 が d=11 の語頭になっており、区切りが曖昧で一意に復号できないため不適。
• イ.a=0 が b=01 の語頭になっており、例えば 010 が a,b なのか b,a なのか判別できず一意に復号できないため不適。
• ウ.どの符号も他の符号の語頭になっておらず一意に復号でき、平均ビット長1.7ビットと最短になるため正しい。
• エ.語頭条件は満たし一意に復号できるが、すべて2ビットの固定長で平均2.0ビットとなり、ウより長いため最短ではない。