過去問.JP

a，b，c，d の4文字から成るメッセージを符号化してビット列にする方法として表のア～エの4通りを考えた。

この表1は a，b，c，d の各1文字を符号化するときのビット列を表している。

メッセージ中の a，b，c，d の出現頻度は，それぞれ，50%，30%，10%，10% であることが分かっている。

符号化されたビット列から元のメッセージが一意に復号可能であって，ビット列の長さが最も短くなるものはどれか。

最小ビットで効率的にメッセージを圧縮する際には、符号化されたビット列から元のメッセージが一意に復号可能であることが重要です。

さらに、ビット列の長さが最も短い方法を選ぶことで、データ圧縮の効率を最大化します。

各文字の出現頻度を考慮して、出現頻度の高い文字には短いビット列を、頻度の低い文字には長いビット列を割り当てているかどうかを確認することが重要です。

これを実現するのが、ハフマン符号化の基本的な考え方です。

• 記号"11"が符号化後のビット列にある場合、元のメッセージを一意に復号することができなくなる可能性があります。例えば、"bb"と"d"がどちらも"11"で符号化されていると、誤認が生じる可能性があるからです。
• 複合パターン"00110"の場合、"abc"と"adda"を区別できないため、再構築の内容が固有ではありません。

ウの選択肢は、出現頻度の高い文字に短いビット列を割り当て、一意の復号が可能でありながら、1文字を表現するための平均ビット数が最も短くなります。そのため、効率性の観点から、最も適した符号化方式となります。

• ア: メッセージを一意に復号することが難しいケースがあるため、最適とは言えません。特定のビット列が複数の文字列に対応している場合があるためです。
• イ: アと同じように異なる文字列に対応可能なビット列が存在するため、元のメッセージを一意に復号することに不利です。
• ウ: 一意に復号可能で、さらに出現頻度の高い文字に短いビット列を割り当てることで、平均ビット数を他の方式よりも小さくしています。これにより、データの圧縮効率が最大化されます。
• エ: 一意に復号可能ですが、1文字を表現するのに必要な平均ビット数がウの方式よりも大きくなります。そのため、ウの方式には及びません。