応用情報技術者試験 応用情報技術者試験 令和2年度 午前 問4: a，b，c，d の 4 文字から成るメッセージを符号化してビット列にする方法として表のア〜エの 4 通りを考えた。この表は a，b，c，d の各 1 文字を符号

正解

ウ. a=0, b=10, c=110, d=111

正答率 74.6%（1,304人中 973人が正解）

問題の解説

ハフマン符号化の考え方を問う問題で、まず一意に復号できる条件(ある符号が別の符号の接頭辞=語頭になっていないという語頭条件)を満たすものに絞り、その中で出現頻度を重みにした平均ビット長が最短のものを選ぶ。語頭条件を満たすのはウとエだけで、ウの平均ビット長は 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ビットとなり、ウより長いため最短ではない。