平成28年度 高度共通 午前I（PM試験） 問2
a，b，c，dの4文字から成るメッセージを符号化してビット列にする方法として表のア〜エの4通りを考えた。この表はa，b，c，dの各1文字を符号化するときのビット列を表している。メッセージ中でのa，b，c，dの出現頻度は，それぞれ50％，30％，10％，10％であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって，ビット列の長さが最も短くなるものはどれか。
※選択肢ア〜エは上の図表内に記載されています。
解答・解説を見る
正解：ウ
AI解説
一意に復号可能にするには、どの符号も他の符号の先頭部分(語頭)になっていないこと(語頭条件)が必要である。その上で平均符号長＝Σ(出現頻度×符号長)が最小のものを選ぶ。出現頻度の高いa(50％)に最短の符号を割り当てたウ(例：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に1ビット符号を与えることで平均符号長1.7ビットと最短になる。 エ: 一意復号可能であっても符号長の割当てが頻度と合っておらず、平均符号長がウより長くなる。 💡 符号化問題は「(1)語頭条件で一意復号可能かをふるいにかける、(2)残りは平均符号長＝Σ頻度×長さを計算して比較」の2段階で解く。頻度が高い文字ほど短い符号、がハフマン符号の原則である。
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。