基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成31年 春期 基本情報技術者 午後 問08
問08   必須問題

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

 

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

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

 

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

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

 

(2) 文字の出現回数表に基づいてハフマン木を作成する。

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

  • 節と枝で構成する二分木である。
  • 親である節は,子である節を常に二つもち,子の節の値の和を値としてもつ。
  • 子をもたない節(以下,葉という)は文字に対応し,出現回数を値としてもつ。
  • 親をもたない節(以下,根という)は,文字列の文字数を値としてもつ。
 文字列αに対応するハフマン木の例を,図1に示す。

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

 

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

@ 節の値を格納する1次元配列を用意する。

A 文字の出現回数表に基づいて,各文字に対応する葉の値を,配列の先頭の要素から順に格納する。

B 親が作成されていない節を二つ選択し,選択した順に左側の子,右側の子とする親の節を一つ作成する。 この節の値を,配列中で値が格納されている最後の要素の次の要素に格納する。 節の選択は節の値の小さい順に行い,同じ値をもつ節が二つ以上ある場合は, 配列の先頭に近い要素に値が格納されている節を選択する。

C 親が作成されていない節が一つになるまでBを繰り返す。

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

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

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

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

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

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

 

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

 

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

 

a に関する解答群

 

b に関する解答群 ア 0.77       イ 0.85       ウ 0.88      エ 0.92
解答 a ←クリックすると正解が表示されます

解答 b ←クリックすると正解が表示されます

 

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

 

〔プログラム1の説明〕

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

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

 

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

 

(3) 副プログラム Huffman は,次の@〜Dを受け取り,ハフマン木を表現する配列を作成する。

 @ 葉である節の個数 size

 A 初期化された配列 parent

 B 初期化された配列 left

 C 初期化された配列 right

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

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

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

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

 

表2 副プログラム Huffman の引数の仕様

  引数    データ型    入出力                   説明  
 size   整数型   入力/出力    節の個数  
 parent[]   整数型   入力/出力    節の親を表す要素組の要素番号を格納した配列  
 left[]   整数型   入力/出力    節の左側の子を表す要素組の要素番号を格納した配列  
 right[]   整数型   入力/出力    節の右側の子を表す要素組の要素番号を格納した配列  
 freq[]   整数型   入力/出力    節の値を格納した配列  

 

表3 副プログラム SortNode の引数の仕様

  引数    データ型    入出力                   説明  
 size   整数型    入力    節の個数  
 parent[]   整数型    入力    節の親を表す要素組の要素番号を格納した配列  
 freq[]   整数型    入力    節の値を格納した配列  
 nsize   整数型    出力    配列 node 中の,整列対象とした節の個数  
 node[]   整数型    出力    節の値の昇順に整列した,親が作成されていない節を  
 表す要素組の要素番号を格納した配列  

 

表4 副プログラム Sort の引数の仕様

  引数    データ型    入出力                   説明  
 freq[]   整数型     入力    節の値を格納した配列  
 nsize   整数型     出力    配列 node 中の,整列対象とした節の個数  
 node[]   整数型   入力/出力    節を表す要素組の要素番号を格納した配列  

 

〔プログラム1〕

c,d に関する解答群

ア nsize ≧ Ø       イ nsize ≧ 1       ウ nsize ≧ 2

エ parent[i] < Ø     オ parent[i] > Ø     カ size ≦ nsize

キ s:ze ≧ nsize

解答 c ←クリックすると正解が表示されます

解答 d ←クリックすると正解が表示されます

 

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

 

〔プログラム2の説明〕

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

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

 

表5 副プログラム Encode の引数の仕様

  引数    データ型    入出力                   説明  
 k   整数型    入力    節を表す要素組の要素番号  
 parent[]   整数型    入力    節の親を表す要素組の要素番号を格納した配列  
 left[]   整数型    入力    節の左側の子を表す要素組の要素番号を格納した配列  

 

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

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

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

〔プログラム2〕

 

e に関する解答群 ア k ≧ Ø      イ left[k] = −1      ウ left[k] ≧ Ø

エ parent[k] = −1      オ parent[k] ≧ Ø

 

f に関する解答群 ア left[k] = k      イ left[Parent[k]] = k

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

解答 e ←クリックすると正解が表示されます

解答 f ←クリックすると正解が表示されます


[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]