平成22年度秋期 応用情報技術者試験 午前 問2
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
解答・解説を見る
正解：ウ
AI解説
出現頻度に偏りがあるデータを符号化する際、ハフマン符号化のように出現頻度の高い文字ほど短いビット列を割り当て、かつどの符号も他の符号の先頭部分（プレフィックス）にならない「プレフィックスフリー」な符号にすることで、一意に復号可能で平均符号長が最小となる。選択肢ウ（a:0, b:10, c:110, d:111）はこの条件を満たし、平均符号長は0.5×1＋0.3×2＋0.1×3＋0.1×3＝1.7ビットとなり最小である。 ア: aの符号"0"がcの符号"00"の先頭部分になっており（プレフィックス条件違反）、ビット列から一意に元のメッセージを復号できない。 イ: aの符号"0"がbの符号"01"の先頭部分になっており、プレフィックス条件を満たさないため一意に復号できない。 ウ: 正しい。a:0, b:10, c:110, d:111はいずれの符号も他の符号の先頭部分にならないプレフィックスフリーな符号であり、出現頻度に応じた可変長符号化により平均符号長が最小（1.7ビット）になる。 エ: すべて2ビットの固定長符号であり一意に復号可能ではあるが、平均符号長は常に2ビットとなり、出現頻度を考慮したウの1.7ビットより長くなる。 💡 一意復号可能性の判定は「ある符号が他の符号の先頭部分（プレフィックス）になっていないか」を確認する。出現頻度が高い文字に短い符号を割り当てるのがハフマン符号化の考え方である。
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。