平成28年度春期 応用情報技術者試験 午前 問4
a，b，c，dの4文字から成るメッセージを符号化してビット列にする方法として表のア～エの4通りを考えた。この表はa，b，c，dの各1文字を符号化するときのビット列を表している。メッセージ中でのa，b，c，dの出現頻度は，それぞれ50％，30％，10％，10％であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって，ビット列の長さが最も短くなるものはどれか。
※選択肢ア〜エは上の図表内に記載されています。
解答・解説を見る
正解：ウ
AI解説
出現頻度に応じて短い符号を割り当てる符号化(ハフマン符号の考え方)の問題である。一意に復号可能であるためには、どの符号語も他の符号語の先頭部分(語頭)になっていないこと(語頭条件)が必要である。頻度がa:50%、b:30%、c:10%、d:10%のとき、a=1ビット、b=2ビット、c=d=3ビットを割り当てる符号(例:a=0、b=10、c=110、d=111)が語頭条件を満たしつつ平均符号長1×0.5+2×0.3+3×0.1+3×0.1=1.7ビットで最短となり、ウが該当する。 ア: 図中の符号は、全て2ビットの固定長などで平均符号長が1.7ビットより長くなるため最短ではない。 イ: 図中の符号は、ある符号語が他の符号語の語頭になっているなど一意復号ができない、または平均符号長が長くなるため不適である。 ウ: 正解。語頭条件を満たし、高頻度のaに最短の符号を与えることで平均符号長が最小(1.7ビット)となる。 エ: 図中の符号は、低頻度の文字に短い符号を与えるなど割当てが頻度と逆で、平均符号長が長くなるため不適である。 💡 平均符号長=Σ(符号長×出現確率)で各選択肢を計算し、同時に語頭条件(prefix条件)を満たすかを確認する。「短い符号は高頻度の文字へ」がハフマン符号の原則である。
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。