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