にしのクエスト2

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

20221224103753

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

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

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

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

f:id:koharuwest:20190908113156p:plain


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

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

設問2
ハフマン木を作成するプログラム1の説明及びプログ
ラム1を読んで、プログラム1中の( )に入れる正し
い答えを、解答群の中から選べ。


〔プログラム1の説明〕

(1)
四つの1次元配列 parent、left、rig
ht 及び freq の同じ要素番号に対応する要
素の組み(以下、要素組という)によって、一つの節
を表す。要素番号は0から始まる。四つの配列の大き
さはいずれも十分に大きく、全ての要素は-1で初期
化されている。


(2)
図3に、図1に示したハフマン木を表現した場合の各
配列の要素がもつ値を示す。配列 parent に
は親、配列 left には左側の子、配列 rig
ht には右側の子を表す要素組の要素番号がそれぞ
れ格納され、配列 freq には節の値が格納され
る。節が葉のとき、配列 left と配列 rig
ht の要素の値は、いずれも-1である。図3では、
要素番号0~3の要素組が、順に文字”A”~”D”
の葉に対応している。節が根のとき、配列 pare
nt の要素の値は-1である。

f:id:koharuwest:20190930150507p:plain

 

副プログラム Huffman は、次の①~⑤ を
受け取り、ハフマン木を表現する配列を作成する。


1 葉である節の個数 size
2 初期化された配列 parent
3 初期化された配列 left
4 初期化された配列 right
5 初期化された後、文字の出現回数が要素番号0か
  ら順に格納された配列 freq


副プログラム SortNode は、親が作成され
ていない節を抽出し、節の値の昇順に整列し、節を表
す要素組の要素番号を順に配列 node に格納し、
その個数を変数 nsize に格納する。行番号1
9~24で親が作成されていない節を表す要素組の要
素番号を抽出し、行番号25で節の値の昇順に整列す
る。


副プログラム Sort (プログラムは省略)は、
節を表す要素組の要素番号の配列 node を受け
取り、要素番号に対応する要素組が表す節の値が昇順
となるように整列する。節の値が同じときの順序は並
べ替える直前の順序に従う。


副プログラム Huffman、SortNode 
及び Sort の引数の仕様を、表2~4に示す。

f:id:koharuwest:20190930150650p:plain

f:id:koharuwest:20190930150722p:plain

f:id:koharuwest:20190930150753p:plain

 

f:id:koharuwest:20190930150819p:plain




 
設問3
ハフマン木から文字のビット表現を作成して表示する
プログラム2の説明及びプログラム2を読んで、プロ
グラム2中の に入れる正しい答えを、解答群の中か
ら選べ。

〔プログラム2の説明〕
(1)
ビット表現を求めたい文字に対応する葉を表す要素組
の要素番号を、副プログラム Encode の引数 
k に与えて呼び出すと、ハフマン木から文字のビッ
ト表現を作成して表示する。

(2)
副プログラム Encode の引数の仕様を、表5
に示す。

f:id:koharuwest:20190930151632p:plain

(3)
副プログラム Encode は、行番号2の条件が
成リ立つとき、副プログラム Encode を再帰
的に呼び出す。これによって、ハフマン木を葉から根
までたどっていく。


(4)
根にたどり着くと次は葉に向かつてたどっていく。現
在の節が親の左側の子のときは0を、右側の子のとき
は1を表示する。

(5)
関数 print は、引数で与えられた文字列を表
示する。

f:id:koharuwest:20190930151710p:plain

 



設問2

処理の継続条件が、nodeが1以上になる時なので

cウ

Sortでは、親が作成されていない節を抜き出すと
ころから始まります。それを判断するのはParent
です。これが0以下なら処理を続けます。

dエ

この問題は難しいですよ。
dから解くとわかりやすいんですけど。


設問3

「根まで辿っていく」とありますので、
Parentの値が継続条件になりそうです。

eオ


左側の節と値が同じかどうかを判断する必要があり
ます。 

fイ


(次回に続く!)