平成29年度秋期 情報処理安全確保支援士 午前Ⅰ 問2

午前I 問02：ハフマン符号の圧縮率を平均の長さで考えよう

圧縮率を見るときは、元のデータが何ビットで表されていたかだけを見るんじゃなくて、ハフマン符号で各記号に割り当てられたビット数が、全体として平均何ビットになるかで考えるんだよ。よく出る記号を短いコード、あまり出ない記号を長いコードにすることで、全体のデータ量を減らすイメージだね。

この問題で問われていること

この問題では、記号ごとの出現頻度を「重み」として使い、各記号のビット長を平均できるかがポイントだよ。たとえば、よく使う言葉ほど短いあだ名で呼ぶと会話が楽になる、という感じで、頻度が高い記号ほど圧縮効果に大きく影響することを意識しよう。

Average Code Length

compare encoded lengths by calculating expected code length from symbol probabilities and bit lengths

average length = sum(probability * code length)

確認ポイント

• 最長符号長だけでは決められない。
• 頻度の高い記号ほど短い符号が有利です。
• 平均符号長の比を見る。

正解

エ

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア

0.75は不正解だよ。元は全員2ビットの固定長で、変換後は平均で1.9ビットになる。比は1.9÷2=0.95。0.75だと平均1.5ビットまで短くなる計算だけど、長い符号もそこそこ使うので、そこまでは縮まらないよ。

選択肢イ

0.85は不正解だよ。0.85なら平均ビット長は2×0.85=1.7ビットということになる。でも実際には、aだけは1ビットでかなり得をするけど、cとdは3ビットで元より長くなる。全体では平均1.9ビットなので、0.85までは小さくならないよ。

選択肢ウ

0.90は不正解だよ。0.90にするには、変換後の平均が2×0.90=1.8ビットである必要がある。でも実際は、3ビットの符号を使うcとdも合わせて30%あるので、平均は1.9ビットになる。少し短く見積もりすぎだね。

選択肢エ（正解）

0.95が正解だよ。買い物袋に貼るラベルの長さを、よく出る商品ほど短くするイメージだね。aは40%で1ビット、bは30%で2ビット、cは20%で3ビット、dは10%で3ビットだから、平均は0.4×1+0.3×2+0.2×3+0.1×3=1.9ビット。元の2ビットと比べると1.9÷2=0.95になるよ。