符号化方式ーハフマン方式

応用情報技術者平成30年秋期 午前問5

符号化方式に関する記述のうち，ハフマン方式はどれか。

１、ハフマン方式
ハフマン符号化方式は、可変長の符号化方式で、出現確率が高いデータには短い符号を、低いデータには長い符号を与えることで圧縮を効率よく行う方法です。特に、出現確率に差がある場合には固定長の符号化よりも高い圧縮率になります。

２、ランレングス法の説明
0と1の数字で構成する符号の中で，0又は1の連なりを一つのブロックとし，このブロックに長さを表す符号を割り当てる。

・ランレングス符号化とは、主に画像データの圧縮に用いられる符号化方式の一種で、連続する同一の値を「色×回数」という列の長さ（run-length）の情報に置き換える方式のことである。

ランレングス符号化では、例えば画像の中に「白白白黒黒黒黒白黒黒」というデータの並びがあった場合、「白3黒4白1黒2」というデータに変換される。ランレングス符号化は単純な画像データほど効果的な圧縮が可能であり、可逆圧縮であるため完全にデータを再現できるというメリットを持っている。FAXなどではランレングス符号化によるデータ圧縮方式が採用されている。

３、二進化十進数(BCD：Binary Coded Decimal)の説明
10進数字の0～9を4ビット2進数の最初の10個に割り当てる。

一般に二進法の4桁(ニブル)は、0から15までの整数を表すことができる。二進化十進法ではこのうちの最初の10個を有効な数値として扱う。
例えば、127 という整数値は、 0001、0010、0111 という3つのBCDで表される。

４、サンプリングの説明
連続した波を標本化と量子化によって0と1の数字で構成する符号に割り当てる。

ーーーーーーーーーーーーーーーーーーーーーーーーーーー
補足
a，b，c，d の4文字からなるメッセージを符号化してビット列にする方法として表のア～エの4通りを考えた。この表は a，b，c，d の各1文字を符号化するときのビット列を表している。メッセージ中の a，b，c，d の出現頻度は，それぞれ，50%，30%，10%，10% であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって，ビット列の長さが最も短くなるものはどれか。

注意する必要な点は、一意に複号可能かもチェックするのが必要ですね。
単な出現頻度により、ビット列の長さが最短だけではないです。

そうすると、
ア、イは一意に複号できないですね。
　ア（一意に復号できない例）
　bb(11)、d(11)
ア（一意に復号できない例）
　abc(00110)、aada(00110)

ウ、エは一意に復号できる。

参照：

ランレングス符号化
https://www.weblio.jp/content/%E3%83%A9%E3%83%B3%E3%83%AC%E3%83%B3%E3%82%B0%E3%82%B9%E6%B3%95

二進化十進表現
https://ja.wikipedia.org/wiki/%E4%BA%8C%E9%80%B2%E5%8C%96%E5%8D%81%E9%80%B2%E8%A1%A8%E7%8F%BE