基本情報技術者試験「符号化」の問題
4種類の文字A・B・C・Dが出現確率0.5,0.25,0.125,0.125で現れる。ハフマン符号化を行ったとき、1文字あたりの平均符号長は何ビットか。
ア2.0ビット
イ2.25ビットになる
ウ1.75ビット
エ1.5ビット
正解
ウ．1.75ビット
出現確率の低い文字を長い符号にする。割当例はA(1ビット),B(2ビット),C(3ビット),D(3ビット)。平均符号長=0.5×1+0.25×2+0.125×3+0.125×3=0.5+0.5+0.375+0.375=1.75ビットとなり正しい。
?選択肢ごとの解説
ア ×2.0ビットは4種類を一律2ビットの固定長で符号化した場合の値で、出現確率に応じて符号長を変えるハフマンの効果を反映していない。
イ ×2.25ビットは符号長の割当を取り違え、頻度の高いAにも長い符号を与えるなどした誤りの値である。
ウ ○出現確率の低い文字を長い符号にする。割当例はA(1ビット),B(2ビット),C(3ビット),D(3ビット)。平均符号長=0.5×1+0.25×2+0.125×3+0.125×3=0.5+0.5+0.375+0.375=1.75ビットとなり正しい。
エ ×1.5ビットは最短符号長や一部の文字だけで平均をとるなど、全文字の確率を正しく重み付けしなかった誤りである。
✎くわしく
ハフマン符号は出現確率の低い2つを繰り返し統合して符号木を作り、頻出文字に短い符号を割り当てる。本問の確率は2のべき乗で構成され、平均符号長はエントロピー(=1.75ビット)に一致し最適となる。
✓本番での押さえどころ
試験のコツ
平均符号長=Σ(確率×符号長)。頻度高=短符号を確認し、固定長との差(圧縮効果)に注目する。
覚え方
ハフマンは『よく出る文字ほど短く』。確率半分ずつなら符号長1,2,3,3と階段状になる、と覚える。
よくある誤り
固定長2ビットと混同して2.0とする、または確率による重み付けを忘れて単純平均する誤りが多い。
基礎理論の他の問題
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0023