応用情報技術者 2017年 秋期 午前2 問03
問題文
四つのアルファベット a〜d から成るテキストがあり、各アルファベットは2ビットの固定長 2進符号で符号化されている。このテキストにおける各アルファベットの出現確率を調べたところ、表のとおりであった。各アルファベットの符号を表のような可変長 2進符号に変換する場合、符号化されたテキストの、変換前に対する変換後のビット列の長さの比は、およそ幾つか。
選択肢
ア：0.75
イ：0.85
ウ：0.90
エ：0.95（正解）
四つのアルファベットの可変長符号化によるビット長比【午前2 解説】
要点まとめ
- 結論：変換後のビット列の長さは変換前の約0.95倍となり、選択肢はエが正解です。
- 根拠：各アルファベットの出現確率と可変長符号のビット長を用いて、平均符号長を計算し、固定長符号（2ビット）との比を求めます。
- 差がつくポイント：平均符号長の計算ミスや確率の割合を正確に扱うこと、固定長符号のビット数を正しく理解することが重要です。
正解の理由
各アルファベットの出現確率と符号長は以下の通りです。
- a: 40%（0.4）、符号長1ビット
- b: 30%（0.3）、符号長2ビット
- c: 20%（0.2）、符号長3ビット
- d: 10%（0.1）、符号長3ビット
平均符号長は
固定長符号は2ビットなので、比は
よって、変換後のビット列は変換前の約95%の長さとなり、選択肢エが正解です。
よくある誤解
平均符号長を計算する際に確率の割合をパーセントのまま使ったり、固定長符号のビット数を3ビットと誤認することがあります。これにより誤った比率を導きます。
解法ステップ
- 各アルファベットの出現確率を小数に直す（例：40% → 0.4）。
- 各アルファベットの可変長符号のビット長を確認する。
- 平均符号長を確率×符号長の和で計算する。
- 固定長符号のビット長（2ビット）と平均符号長の比を求める。
- 比率に最も近い選択肢を選ぶ。
選択肢別の誤答解説
- ア（0.75）：平均符号長を過小評価し、符号長を1ビットに近いと誤認した可能性があります。
- イ（0.85）：符号長の計算は近いが、確率の扱いで誤差が生じています。
- ウ（0.90）：平均符号長の計算はほぼ正しいが、固定長符号のビット数を誤解している可能性があります。
- エ（0.95）：正確に平均符号長と固定長符号の比を計算しているため正解です。
補足コラム
可変長符号は情報理論で効率的な符号化を実現する手法で、出現頻度の高い文字に短い符号を割り当てることで平均符号長を短縮します。ハフマン符号が代表例で、今回の問題もハフマン符号の考え方に基づいています。
FAQ
Q: なぜ固定長符号は2ビットなのですか？
A: アルファベットが4種類なので、通りの符号が必要で、2ビットで全て表現可能だからです。
A: アルファベットが4種類なので、通りの符号が必要で、2ビットで全て表現可能だからです。
Q: 平均符号長が固定長符号のビット数より大きくなることはありますか？
A: はい、可変長符号の設計が不適切な場合や符号化対象の確率分布によっては平均符号長が固定長符号より長くなることもあります。
A: はい、可変長符号の設計が不適切な場合や符号化対象の確率分布によっては平均符号長が固定長符号より長くなることもあります。
関連キーワード: 可変長符号、平均符号長、ハフマン符号、符号化効率、情報理論
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！