応用情報技術者 2016年 春期 午前2 問04
問題文
a, b, c, dの4文字から成るメッセージを符号化してビット列にする方法として表のア〜エの4通りを考えた。この表は a, b, c, dの各1文字を符号化するときのビット列を表している。メッセージ中での a, b, c, dの出現頻度は、それぞれ50%、30%、10%、10%であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって、ビット列の長さが最も短くなるものはどれか。
選択肢
ア：
イ：
ウ：（正解）
エ：
符号化方式の選択問題【午前2 解説】
要点まとめ
- 結論：符号化方式は「ウ」が最も短いビット列で一意復号可能な符号を実現します。
- 根拠：各文字の出現頻度に応じて短い符号語を割り当て、かつ前方一致しない符号（プレフィックス符号）であることが重要です。
- 差がつくポイント：符号語の長さとプレフィックス性の両立、頻度の高い文字に短い符号を割り当てているかを見極める力が問われます。
正解の理由
選択肢「ウ」は、a=0（頻度50%）、b=10（30%）、c=110（10%）、d=111（10%）と、頻度の高い文字ほど短いビット列を割り当てています。さらに、どの符号語も他の符号語の先頭部分になっていないため、一意に復号可能なプレフィックス符号です。これにより、平均符号長が最も短くなり、効率的な符号化が実現されます。
よくある誤解
符号語が短ければ良いと考えがちですが、プレフィックス性がないと復号時に曖昧さが生じます。単に短い符号語を割り当てるだけでは不十分です。
解法ステップ
- 各文字の出現頻度を確認する（a:50%、b:30%、c:10%、d:10%）。
- 各選択肢の符号語がプレフィックス符号かどうかを判定する。
- プレフィックス符号でない選択肢は除外する。
- 平均符号長を計算し、最も短いものを選ぶ。
- その結果、「ウ」が最適であると判断する。
選択肢別の誤答解説
- ア：c=00、a=0があり、aの符号語0がcの符号語00の先頭部分となりプレフィックス符号ではない。
- イ：a=0、b=01、c=10、d=11でプレフィックス符号だが、bとc、dの符号長が長く平均符号長が「ウ」より大きい。
- ウ：プレフィックス符号であり、頻度に応じた最適な符号長割り当てで平均符号長が最小。
- エ：すべて2ビットでプレフィックス符号だが、aの頻度が高いため平均符号長が長く非効率。
補足コラム
この問題はハフマン符号の基本原理に基づいています。ハフマン符号は頻度の高い文字に短い符号語を割り当て、プレフィックス符号を保証することで最適な平均符号長を実現します。プレフィックス符号とは、どの符号語も他の符号語の先頭部分にならない符号のことです。
FAQ
Q: プレフィックス符号とは何ですか？
A: どの符号語も他の符号語の先頭部分にならない符号で、一意に復号可能な符号体系です。
A: どの符号語も他の符号語の先頭部分にならない符号で、一意に復号可能な符号体系です。
Q: なぜ頻度の高い文字に短い符号語を割り当てるのですか？
A: 平均符号長を短くし、全体のデータ圧縮効率を高めるためです。
A: 平均符号長を短くし、全体のデータ圧縮効率を高めるためです。
関連キーワード: ハフマン符号、プレフィックス符号、符号化、平均符号長、データ圧縮
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！