データベーススペシャリスト令和2年秋期 午前T 問2

午前T 問2

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

分類

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

正解

解説

最小ビットで圧縮できる方式を考える前に、各方式が符号化されたビット列から元のメッセージを一意に復号可能かどうかを検証し、条件を満たす方式についてだけビット数を計算します。
  • 文字列bb(11)と、d(11)の区別がつかず一意の復号は不可能です。
  • abc(00110)と、aada(00110)の区別がつかず一意の復号は不可能です。
  • 並べてみるとわかりますが、一意の復号が可能です。
    各文字の出現頻度を考慮すると、1文字を表現するのに必要な平均ビットは、
     (1×0.5)+(2×0.3)+(3×0.1)+(3×0.1)
    =0.5+0.6+0.3+0.3=1.7
    となり、4つの中では復号可能かつビット列の長さが最も短くなる方法となります。
  • 各文字が2ビットずつなので一意の復号が可能です。
    1文字を表現するのに必要な平均ビットは2ビットなので、「ウ」の方式よりはビット列が長くなります。
この設問の例のように、出現度の高い文字を短いビット列で、出現率が低い文字を長いビット列で表現することで、1文字を表現するのに使用する平均ビット長を最小とする圧縮技術をハフマン符号化と言います。
© 2016-2020 データベーススペシャリストドットコム All Rights Reserved.

Pagetop