にしのクエスト2

情報処理技術者試験と資格学校講師の日常

f:id:koharuwest:20191106221322p:plain

まいにち基本 平成31年春午後問題解説 問8 その1

ハフマン符号の問題その1になります。

このあとなんですが、プログラミングの問題は13
を解説して終わろうかと思います。残り3回で終わ
りますよ。

いや、そうじゃないだろ!という方。希望の言語と
かありますかね?お知らせくださいませ〜!

f:id:koharuwest:20190908113156p:plain


午後の問題を少しずつ解説していく連載です。
・赤字は「私ならここに線を引くなぁ」という場所。
・青字は私が考えたことや注釈などです。
皆さんも一緒に問題を読みながら、解答の方法をトレ
ースしてみていただけたら、幸いです。

問8 ハフマン符号
ハフマン符号化を用いた文字列圧縮に関する次の記述
を読んで、設問1~3に答えよ。


”A”~”D”の4種類の文字から成る文字列をハフマン
符号化によって圧縮する。ハフマン符号化では、出現
回数の多い文字には短いビット列を、出現回数の少な
い文字には長いビット列を割り当てる。ハフマン符号
化による文字列の圧縮手順は、次の(1)~(4)の
とおりである。


(1)
文字列中の文字の出現回数を求め、出現回数表を作成
する。例えば、文字列

”AAAABBCDCDDACCAAAAA”

(以下、文字列aという)中の文字の出現回数表は、
表1のとおりになる。

f:id:koharuwest:20190929224455p:plain

(2)
文字の出現回数表に基づいてハフマン木を作成する。
ハフマン木の定義は、次のとおりである。

・節と枝で構成する二分木である。
・親である節は、子である節を常に二つもち、子の節
 の値の和を値としてもつ。
・子をもたない節(以下、葉という)は文字に対応し、
 出現回数を値としてもつ。
・親をもたない節(以下、根という)は、文字列の文
 字数を値としてもつ。


文字列αに対応するハフマン木の例を、図1に示す。

f:id:koharuwest:20190929224616p:plain


ハフマン木は、次の手順で配列によって実現する。

1 節の値を格納する1次元配列を用意する。
2 文字の出現回数表に基づいて、各文字に対応する
  葉の値を、配列の先頭の要素から順に格納する。
X[10,2,3,4]
3 親が作成されていない節を二つ選択し、選択した
  順に左側の子、右側の子とする親の節を一つ作成
  する。この節の値を、配列中で値が格納されてい
  る最後の要素の次の要素に格納する。節の選択は
  節の値の小さい順に行い、同じ値をもつ節が二つ
  以上ある場合は、配列の先頭に近い要紫に値が格
  納されている節を選択する。
X[10,2,3,4]ならば2,3で作る
X[10,2,3,4,5] 10と4
X[10,2,3,4,5,14] 5と14
X[10,2,3,4,5,14,19]おしまい!
4 親が作成されていない節が一つになるまで③を繰
  り返す。


これね。流れ図を作ったほうがいいやつですよ。

(3)
ハフマン木から文字のビット列(以下、ビット表現と
いう)を次の手順で作成する。

1 親と左側の子をつなぐ枝に0、右側の子をつなぐ
  枝に1の値をもつビットを割り当てる。

2 文字ごとに根から対応する葉までたどったとき、
  枝のビット値を順に左から並べたものを各文字の
  ビット表現とする。

図2に示すとおり、根から矢印のようにたどると、文
字列αの文字”B”のビット表現は010となる。

f:id:koharuwest:20190929225503p:plain

文字列の全ての文字を(3)で得られたビット表現に
置き換えて、ビット列を作成する。
図で言うと、上から下ですね。



設問1
次の記述中の(  )に入れる正しい答えを、解答群
の中か1ら選べ。

 文字列”ABBBBBBBCCCDD”を、ハフマン
符号化を用いて表現する。各文字とビット表現を示し
た表は( a )である。ハフマン符号化によって圧
縮すると、文字”A”~”D”をそれぞれ2ビットの固定
長で表現したときの当該文字列の総ビット長に対する
圧縮率は( b )となる。ここで、圧縮率は次式で
計算した値の小数第3位を四捨五入して求める。

 

f:id:koharuwest:20190929225653p:plain



 設問1

 文字列”ABBBBBBBCCCDD”を、ハフマン
符号化を用いて表現する。各文字とビット表現を示し
た表は( a )である。ハフマン符号化によって圧
縮すると、文字”A”~”D”をそれぞれ2ビットの固定
長で表現したときの当該文字列の総ビット長に対する
圧縮率は( b )となる。ここで、圧縮率は次式で
計算した値の小数第3位を四捨五入して求める。

 

f:id:koharuwest:20190929225653p:plain
出現率は
A1 B7 C3  D2
配列に入れると
X[1,7,3,2]
枝を作っていきます1と2
X[1,7,3,2,3] 3と3
X[1,7,3,2,3,3,6]7と6
X[1,7,3,2,3,3,6,13]
ゆえに
         6(0)         7B(1)
3C(0)     3(1)
       1A(0)     2D(1)
こんな感じなので
A010 B1 C00 D011

a ア

総ビット数は13文字なので2ビット 26bit
圧縮すると010100011 に出現回数を掛けます
A1*3bit B7*1bit C3*2bit  D2*3bit なので
22/26= 0.85が一番近い数字です。

b イ


(次回に続く!)