情報に関する理論 (全37問中31問目)

No.31

a,b,c,d の4文字からなるメッセージを符号化してビット列にする方法として表のア〜エの4通りを考えた。この表は a,b,c,d の各1文字を符号化するときのビット列を表している。メッセージ中の a,b,c,d の出現頻度は,それぞれ,50%,30%,10%,10% であることが分かっている。符号化されたビット列から元のメッセージが一致に復号可能であって,ビット列の長さが最も短くなるものはどれか。
  • [この問題の出題歴]
  • 応用情報技術者 H22秋期 問2
  • 応用情報技術者 H28春期 問4

分類

テクノロジ系 » 基礎理論 » 情報に関する理論

正解

解説

最小ビットで圧縮できる方式を考える前に、各方式が符号化された文字列から元の文字列を一意に復号可能かを検証し、条件を満たす方式についてだけビット数を計算します。
  • 文字列bb(11)と、d(11)の区別がつかず一意の復号は不可能です。
  • abc(00110)と、aada(00110)の区別がつかず一意の復号は不可能です。
  • 並べてみるとわかりますが、一意の復号が可能です。
    一文字を表現するのに必要な平均ビットは、各文字の出現頻度を考慮して計算すると、

     (1×0.5)+(2×0.3)+(3×0.1)+(3×0.1)
    =0.5+0.6+0.3+0.3=1.7

    となり4つの中では、復号可能かつビット列の長さが最も短くなる方法となります。
  • 各ビットが2ビットずつで一意の復号が可能です。
    一文字を表現するのに必要な平均ビットは2ビットなので、「ウ」の方式よりはビット列が長くなります。
この設問の例のように出現度の高い文字を短いビット列で、出現率が低い文字を長いビット列で表現することで、1文字を表現するのに使用する平均ビット長を最小とする圧縮技術をハフマン符号化と言います。
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop