ハフマン符号化を用いた文字列圧縮に関する次の記述を読んで，設問１〜３に答えよ。

(1) 文字列中の文字の出現回数を求め，出現回数表を作成する。例えば，文字列 “AAAABBCDCDDACCAAAAA”（以下，文字列αという）中の文字の出現回数表は，表１のとおりになる。

　ハフマン木の定義は，次のとおりである。

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

図１　文字列αに対応するハフマン木の例

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

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

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

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

図２　文字列αにおける文字“B”のビット表現の作成例

基本情報技術者試験

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

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

図３　図１に示したハフマン木を表現する四つの配列

　�@ 葉である節の個数 size

　�A 初期化された配列 parent

　�B 初期化された配列 left

　�C 初期化された配列 right

　�D 初期化された後，文字の出現回数が要素番号 0 から順に格納された配列 freq

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

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

(6) 副プログラム Huffman，SortNode 及び Sort の引数の仕様を，表２〜４に示す。

c，d に関する解答群

基本情報技術者試験

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

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

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

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

〔プログラム２〕