ハフマン符号の問題その２になります。
このあとなんですが、プログラミングの問題は１３
を解説して終わろうかと思います。残り２回で終わ
りますよ。
いや、そうじゃないだろ！という方。希望の言語と
かありますかね？お知らせくださいませ〜！
午後の問題を少しずつ解説していく連載です。
・赤字は「私ならここに線を引くなぁ」という場所。
・青字は私が考えたことや注釈などです。
皆さんも一緒に問題を読みながら、解答の方法をトレ
ースしてみていただけたら、幸いです。
問８ ハフマン符号
ハフマン符号化を用いた文字列圧縮に関する次の記述
を読んで、設問１～３に答えよ。
設問２
ハフマン木を作成するプログラム１の説明及びプログ
ラム１を読んで、プログラム１中の( )に入れる正し
い答えを、解答群の中から選べ。
〔プログラム１の説明〕
（１）
四つの１次元配列 ｐａｒｅｎｔ、ｌｅｆｔ、ｒｉｇ
ｈｔ 及び ｆｒｅｑ の同じ要素番号に対応する要
素の組み（以下、要素組という）によって、一つの節
を表す。要素番号は０から始まる。四つの配列の大き
さはいずれも十分に大きく、全ての要素は－１で初期
化されている。
（２）
図３に、図１に示したハフマン木を表現した場合の各
配列の要素がもつ値を示す。配列 ｐａｒｅｎｔ に
は親、配列 ｌｅｆｔ には左側の子、配列 ｒｉｇ
ｈｔ には右側の子を表す要素組の要素番号がそれぞ
れ格納され、配列 ｆｒｅｑ には節の値が格納され
る。節が葉のとき、配列 ｌｅｆｔ と配列 ｒｉｇ
ｈｔ の要素の値は、いずれも－１である。図３では、
要素番号０～３の要素組が、順に文字”Ａ”～”Ｄ”
の葉に対応している。節が根のとき、配列 ｐａｒｅ
ｎｔ の要素の値は－１である。
副プログラム Ｈｕｆｆｍａｎ は、次の①～⑤ を
受け取り、ハフマン木を表現する配列を作成する。
１ 葉である節の個数 ｓｉｚｅ
２ 初期化された配列 ｐａｒｅｎｔ
３ 初期化された配列 ｌｅｆｔ
４ 初期化された配列 ｒｉｇｈｔ
５ 初期化された後、文字の出現回数が要素番号０か
ら順に格納された配列 ｆｒｅｑ
副プログラム ＳｏｒｔＮｏｄｅ は、親が作成され
ていない節を抽出し、節の値の昇順に整列し、節を表
す要素組の要素番号を順に配列 ｎｏｄｅ に格納し、
その個数を変数 ｎｓｉｚｅ に格納する。行番号１
９～２４で親が作成されていない節を表す要素組の要
素番号を抽出し、行番号２５で節の値の昇順に整列す
る。
副プログラム Ｓｏｒｔ （プログラムは省略）は、
節を表す要素組の要素番号の配列 ｎｏｄｅ を受け
取り、要素番号に対応する要素組が表す節の値が昇順
となるように整列する。節の値が同じときの順序は並
べ替える直前の順序に従う。
副プログラム Ｈｕｆｆｍａｎ、ＳｏｒｔＮｏｄｅ
及び Ｓｏｒｔ の引数の仕様を、表２～４に示す。
設問３
ハフマン木から文字のビット表現を作成して表示する
プログラム２の説明及びプログラム２を読んで、プロ
グラム２中の に入れる正しい答えを、解答群の中か
ら選べ。
〔プログラム２の説明〕
（１）
ビット表現を求めたい文字に対応する葉を表す要素組
の要素番号を、副プログラム Ｅｎｃｏｄｅ の引数
ｋ に与えて呼び出すと、ハフマン木から文字のビッ
ト表現を作成して表示する。
（２）
副プログラム Ｅｎｃｏｄｅ の引数の仕様を、表５
に示す。
（３）
副プログラム Ｅｎｃｏｄｅ は、行番号２の条件が
成リ立つとき、副プログラム Ｅｎｃｏｄｅ を再帰
的に呼び出す。これによって、ハフマン木を葉から根
までたどっていく。
（４）
根にたどり着くと次は葉に向かつてたどっていく。現
在の節が親の左側の子のときは０を、右側の子のとき
は１を表示する。
（５）
関数 ｐｒｉｎｔ は、引数で与えられた文字列を表
示する。
設問２
処理の継続条件が、nodeが１以上になる時なので
ｃウ
Sortでは、親が作成されていない節を抜き出すと
ころから始まります。それを判断するのはParent
です。これが0以下なら処理を続けます。
ｄエ
この問題は難しいですよ。
ｄから解くとわかりやすいんですけど。
設問３
「根まで辿っていく」とありますので、
Parentの値が継続条件になりそうです。
ｅオ
左側の節と値が同じかどうかを判断する必要があり
ます。
ｆイ
（次回に続く！）
