今週の午後問題〔問題〕アルゴリズム ハフマン符号化を用いた文字列圧縮 2019 年度 春期

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

   表 1 文字列 α 中の文字の出現回数表

   文字	A	B	C	D
   出現回数	10	2	4	3

2. 文字の出現回数表に基づいてハフマン木を作成する。
   ハフマン木の定義は，次のとおりである。
   • 節と枝で構成する二分木である。
   • 親である節は，子である節を常に二つもち，子の節の値の和を値としてもつ。
   • 子をもたない節（以下，葉という）は文字に対応し，出現回数を値としてもつ。
   • 親をもたない節（以下，根という）は，文字列の文字数を値としてもつ。

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

   

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

   1. 節の値を格納する 1 次元配列を用意する。
   2. 文字の出現回数表に基づいて，各文字に対応する葉の値を，配列の先頭の要素から順に格納する。
   3. 親が作成されていない節を二つ選択し，選択した順に左側の子，右側の子とする親の節を一つ作成する。この節の値を，配列中で値が格納されている最後の要素の次の要素に格納する。節の選択は節の値の小さい順に行い，同じ値をもつ節が二つ以上ある場合は，配列の先頭に近い要素に値が格納されている節を選択する。
   4. 親が作成されていない節が一つになるまで ⅲ を繰り返す。
3. ハフマン木から文字のビット列（以下，ビット表現という）を次の手順で作成する。
   1. 親と左側の子をつなぐ枝に 0 ，右側の子をつなぐ枝に 1 の値をもつビットを割り当てる。
   2. 文字ごとに根から対応する葉までたどったとき，枝のビット値を順に左から並べたものを各文字のビット表現とする。
      図 2 に示すとおり，根から矢印のようにたどると，文字列 α の文字 “B” のビット表現は 010 となる。

      

4. 文字列の全ての文字を 3. で得られたビット表現に置き換えて，ビット列を作成する。

設問 1

次の記述中のに入れる正しい答えを，解答群の中から選べ。

a に関する解答群

b に関する解答群

ア　0.77　　イ　0.85　　ウ　0.88　　
エ　0.92

設問 2

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

infoスマートフォンをご覧の際、プログラムは右にスクロールできます

○副プログラム: Huffman(整数型: size, 整数型: parent[], 整数型: : left[], 整数型: right[], 整数型: freq[])
○整数型: i, j, nsize
○整数型: node[]
• SortNode(size, parent, freq, nsize, node)
■ "[   c   ]"
| ･ i ← node[0]    /* 最も小さい値をもつ要素組の要素番号 */
| ･ j ← node[1]    /* 2 番目に小さい値をもつ要素組の要素番号 */
| ･ left[size] ← i
| ･ right[size] ← j
| ･ freq[size] ← freq[i] + freq[j] /* 子の値の合計 */
| ･ parent[i] ← size   /* 子に親の節の要素番号を格納 */
| ･ parent[j] ← size   /* 子に親の節の要素番号を格納 */
| ･ size + size + 1
| ･ SortNode(size, parent, freq, nsize, node)
■

○副プログラム: SortNode(整数型: size, 整数型: parent[], 整数型: freq[], 整数型: nsize, 整数型: node[])
○整数型: i 
･ nsize ← 0
■ i: 0, i < size, 1
| ▲ "[   d   ]"
| | ･ node[nsize] ← i
| | ･ nsize ← nsize + 1
| ▼
■
･ Sort(freq, nsize, node)

c， d に関する解答群

ア nsize ≧ 0  イ nsize ≧ 1  ウ nsize ≧ 2
エ parent[i] < 0  オ parent[i] > 0  カ size ≦ nsize
キ size ≧ nsize

設問 3

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

○副プログラム: Encode(整数型:k, 整数型: parent[], 整数型: left[])
▲ "[   e   ]"
| ･ Encode(parent[k], parent, left)
| ▲ "[   f   ]"
| | ･ print("0")        /* 0 を表示する */
|-+---
| | ･ print("1")        /* 1 を表示する */
| ▼
▼ 

e に関する解答群

ア k ≧ 0  イ left[k] = -1  ウ left[k] ≧ 0
エ parent[k] = -1  オ parent[k] ≧ 0

f に関する解答群

ア left[k] = k  イ left[parent[k]] = k
ウ parent[k] = k  エ parent[left[k]] = k