応用情報技術者試験 令和2年秋 午前問4 解説付き過去問
問題
a、b、c、dの4文字からなるメッセージを符号化してビット列にする方法として4通りを考えた。
この表はa、b、c、dの各1文字を符号化するときのビット列を表している。
メッセージ中のa、b、c、dの出現頻度は、それぞれ、50%、30%、10%、10%であることが分かっている。
符号化されたビット列から元のメッセージが一意に復号可能であって、ビット列の長さが最も短くなるものはどれか。
正解
解説
この問題は、文字ごとの出現頻度が異なる場合において、平均のビット数を最小化するような符号化方式を選ぶものです。
条件として、「一意に復号可能」であること、かつ「平均ビット長が最小」であることの2点が求められます。
- 一意に復号可能な符号の条件
符号が一意に復号できるためには、任意の1文字のビット列が他の文字のビット列の先頭（プレフィックス）になっていない必要があります。
このような符号は「プレフィックスフリー符号」と呼ばれ、ハフマン符号などで用いられます。 - 出現頻度に応じたビット長の調整
文字の出現頻度が高いほど、割り当てるビット列は短くするのが理想です。
与えられた出現頻度は以下のとおりです：
a：50%、b：30%、c：10%、d：10%
このような場合、最も短いビット列をaに、最も長いビット列をcやdに割り当てると効率的です。 - ビット長と平均ビット数の計算
以下のようなビット長を持つと仮定できます。
a：1ビット、b：2ビット、c：3ビット、d：3ビット
このときの平均ビット数は、
1×0.5＋2×0.3＋3×0.1＋3×0.1 ＝ 0.5＋0.6＋0.3＋0.3 ＝ 1.7
他の選択肢と比較しても、復号可能かつこの平均ビット数が最小であることが分かります。
したがって、出現頻度の高い文字に短いビット列を割り当て、全体の平均ビット長を最小化している選択肢が正解です。