応用情報技術者 2020年 秋期 午前2 問04
問題文
a, b, c, dの 4 文字から成るメッセージを符号化してビット列にする方法として表のア〜エの4通りを考えた。この表は a, b, c, dの各1文字を符号化するときのビット列を表している。メッセージ中での a, b, c, dの出現頻度は、それぞれ 50%、30%、10%、10%であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって、ビット列の長さが最も短くなるものはどれか。
選択肢
ア：
イ：
ウ：（正解）
エ：
符号化方式の選択問題【午前2 解説】
要点まとめ
- 結論：選択肢ウが最も短いビット列で一意復号可能な符号化方式です。
- 根拠：出現頻度に応じて短い符号を割り当て、かつ前方一致しない符号（プレフィックス符号）であることが重要です。
- 差がつくポイント：符号の前方一致性と平均符号長の計算、ハフマン符号の原理理解が合否を分けます。
正解の理由
選択肢ウは、aに最短の1ビット「0」、bに2ビット「10」、cに3ビット「110」、dに3ビット「111」を割り当てています。
これにより、頻度の高い文字ほど短い符号長となり、平均符号長が最小化されます。
また、すべての符号がプレフィックス符号（どの符号も他の符号の接頭辞にならない）であるため、一意に復号可能です。
これにより、頻度の高い文字ほど短い符号長となり、平均符号長が最小化されます。
また、すべての符号がプレフィックス符号（どの符号も他の符号の接頭辞にならない）であるため、一意に復号可能です。
よくある誤解
符号長が短いからといって必ずしも一意復号可能とは限らず、前方一致があると復号できません。
また、単純にビット数の合計だけでなく、出現頻度を考慮した平均符号長が重要です。
また、単純にビット数の合計だけでなく、出現頻度を考慮した平均符号長が重要です。
解法ステップ
- 各文字の出現頻度を確認（a:50%、b:30%、c:10%、d:10%）。
- 各選択肢の符号長を文字ごとに確認。
- プレフィックス符号かどうかを判定（前方一致がないか）。
- 平均符号長を計算：。
- 最も平均符号長が短く、かつ一意復号可能なものを選ぶ。
選択肢別の誤答解説
- ア：cとdの符号が「00」「11」でa「0」とb「1」と前方一致し、復号が曖昧になる。
- イ：b「01」とc「10」、d「11」はプレフィックス符号だが、a「0」とb「01」が前方一致しないため一意復号可能。平均符号長はウより長い。
- ウ：すべての符号がプレフィックス符号であり、頻度に応じた最適割り当てで平均符号長が最小。
- エ：すべて2ビット符号で平均符号長が長く、効率が悪い。
補足コラム
この問題はハフマン符号の基本原理を問うものです。ハフマン符号は頻度の高い文字に短い符号を割り当て、平均符号長を最小化します。プレフィックス符号であることが復号の鍵で、これによりビット列を一意に元の文字列に戻せます。
FAQ
Q: プレフィックス符号とは何ですか？
A: どの符号も他の符号の接頭辞（前方一致）にならない符号のことです。これにより一意復号が可能になります。
A: どの符号も他の符号の接頭辞（前方一致）にならない符号のことです。これにより一意復号が可能になります。
Q: 平均符号長はどう計算しますか？
A: 各文字の符号長にその文字の出現頻度を掛けて合計します。で求めます。
A: 各文字の符号長にその文字の出現頻度を掛けて合計します。で求めます。
関連キーワード: ハフマン符号、プレフィックス符号、平均符号長、符号化、復号
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！