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

今週の午後問題

このコーナーでは毎週月曜に午後の必須選択問題から 1 問ピックアップして出題し、 解答欄 を設け、読者の皆さまにも解答してもらっています!

今週の午後問題は「 ハフマン符号化を用いた文字列圧縮」でしたが、皆さん、手応えはいかがでしょうか?

金曜になりましたので、出題の 解答 と 矢沢久雄さんによる 解説 に加えて、皆さんの正解率を公開します。

今週の午後問題
2019 年度 春期 ハフマン符号化を用いた文字列圧縮

解答と解説

設問 1a

正解

“ABBBBBBBCCCDD” という文字列のハフマン木は、以下のようになります。


このハフマン木をたどると、それぞれの文字のビット表現は、
“A” が 010
“B” が 1
“C” が 00
“D” が 011
なので、選択肢アが正解です。

設問 1b

正解

“A” ~ “D” のそれぞれを 2 ビットの固定長で表現すると、
“ABBBBBBBCCCDD”
という 13 文字の文字列は、

2 ビット × 13 文字 = 26 ビット

になります。

1 文字ある “A” が 3 ビット、
7 文字ある “B” が 1 ビット、
3 文字ある “C” が 2 ビット、
2 文字ある “D” が 3 ビット
のハフマン符号で表現すると、

3 ビット × 1 文字 + 1 ビット × 7 文字 + 2 ビット × 3 文字 + 3 ビット × 2 文字 = 22 ビット
になります。

したがって、圧縮率は、

22 ビット ÷ 26 ビット ≒ 0.85

であり、選択肢イが正解です。

設問 2c

正解

空欄 c の直前で、 SortNode が呼び出され、出力として、 node[] に親が作成されていない節を表す要素組の要素番号を格納した配列が設定され、 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)
■

空欄 c の条件が真である限り繰り返される処理では、 node[0] と node[1] の要素組の要素番号を取り出して処理を行っています。

nsize の値が 2 以上でなければ、この処理を行えないので、空欄 c は、選択肢ウの nsize ≧ 2 が正解です。

設問 2d

正解

〔プログラム 1 の説明〕の 4. に、

行番号 19 ~ 24 で親が作成されていない節を表す要素組の要素番号を抽出し

とあります。

親が作成されていないことは、 parent[i] の値が -1 であることで判断できます。選択肢の中で、これに該当するのは、選択肢エの parent[i] < 0 です。

設問 3e

正解

〔プログラム 2 の説明〕の 3. に、

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

とあります.これは、親が根でない限り、 Encode の再帰的な呼び出しを繰り返すということです。

親が根であるないことは、 parent[k] の値が -1 でないことで判断できます。選択肢の中で、これに該当するのは、選択肢オの parent[k] ≧ 0 です。

設問 3f

正解

空欄 f の条件が真のとき “0” を表示します。これは、根から葉の方向にたどっていくときに、現在の節が親の左側のときです。

親の要素番号は、 parent[k] です。その親の左側の要素番号は、 left[parent[k]] です。

これが、現在の節の要素番号 k と等しければ、現在の節が親の左側なので、その条件は、 left[parent[k]] = k であり、選択肢イが正解です。

みんなの解答

ご解答いただいた皆さん、ありがとうございました!

手応えはいかがでしたでしょうか?

 

なお、以下はこの問題の IPA の講評です。今後の参考になれば幸いです。

 問 8 では,ハフマン符号化を題材に,簡単な例での圧縮率の計算,配列で表現したハフマン木を作成する処理,及びハフマン木から文字のビット表現を作成して表示する再帰処理について出題した。
 設問 1 では, a の正答率は高く,よく理解されていた。 b の正答率は低く,あまり理解されていなかった。ウと誤って解答した受験者が見受けられた。圧縮前の文字列のビット長は,文字数と各文字のビット表現のビット長である 2 との積で求められる。また,圧縮後の文字列のビット長は,文字のビット表現のビット長が文字の出現回数の多い順に 1 ビット, 2 ビット, 3 ビット, 3 ビットであり,文字の出現回数とその文字のビット長との積の総和で求められることが分かれば,正答できた。
 設問 2 では, c の正答率は低く,あまり理解されていなかった。この繰返しの処理では,親が作成されていない二つの節から,親の節を作成すること,及び副プログラム SortNode が出力する nsize は,整列対象とした節の個数,すなわち親が作成されていない節の個数であることに気がつけば,正答できた。 d の正答率は低く,あまり理解されていなかった。キと誤って解答した受験者が見受けられた。副プログラムSortNodeは,親が作成されていない節を抽出する,すなわち配列 parent の要素の値が -1 の節を抽出することに気がつけば,正答できた。
 設問 3 では, e の正答率は低く,あまり理解されていなかった。副プログラム Encode は葉から根まで再帰処理でたどる,すなわち根でなければ再帰処理を続けることに気がつけば,正答できた。 f の正答率は低く,あまり理解されていなかった。エと誤って解答した受験者が見受けられた。現在の節が親の左側の子であるということは,親の要素番号をもつ要素組の左側の子の要素番号が現在の要素番号と同じであるという条件に気がつけば,正答できた。
 プログラムの作成においては,アルゴリズム及びプログラムの仕様を理解し,条件分岐や繰返しの条件を正しく実装する能力が,使用するプログラム言語を問わず求められるので,身につけておいてほしい。

来週もひきつづき「アルゴリズム問題」を出題します! 多くの方が苦手にしがちなので、これを機会にじっくり挑戦してみてください!

label 関連タグ
Q. 午前試験を
『免除』するには?
A. 独習ゼミで午前免除制度を活用しましょう。
免除試験を受けた 87% の方が、
1 年間の午前免除資格を得ています。
2022 年 上期 試験向け
コース申込受付中!
info_outline
2022 年 上期 試験向け
コース申込受付中!
詳しく見てみるplay_circle_filled
label これまでの『今週の午後問題』の連載一覧 label 著者