平成22年度 秋期 応用情報技術者試験 午前 問2
テクノロジ／基礎理論a，b，c，dの4文字からなるメッセージを符号化してビット列にする方法として表のア～エの4通りを考えた。この表はa，b，c，dの各1文字を符号化するときのビット列を表している。メッセージ中でのa，b，c，dの出現頻度は，それぞれ50％，30％，10％，10％であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって，ビット列の長さが最も短くなるものはどれか。 （注：本サイトでは原問題の表を文字表記に変換しています）
出典：平成22年度 秋期 応用情報技術者試験 午前 問2
- ア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ビットです。
選択肢ごとの解説
- ア誤り。aの符号"0"がcの符号"00"の先頭部分になっており，プレフィックス条件を満たさず一意に復号できません。
- イ誤り。aの符号"0"がbの符号"01"の先頭部分になっており，プレフィックス条件を満たさず一意に復号できません。
- ウ正しい。a：0，b：10，c：110，d：111はどの符号もほかの符号の先頭部分になっておらず，一意に復号可能で，出現頻度を考慮した最短の符号長になっています。
- エ誤り。一意に復号は可能ですが，すべて2ビット固定長であり，出現頻度に偏りがあるにもかかわらず短縮されておらず，最短の符号にはなっていません。