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

error
この記事は基本情報技術者試験の旧制度( 2022 年以前)の記事です。
この記事の題材となっている「午後問題」は現在の試験制度では出題されません。 ご注意くださいませ。
このコーナーでは毎週月曜に午後の必須選択問題から 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 の講評です。今後の参考になれば幸いです。
設問 1 では, a の正答率は高く,よく理解されていた。 b の正答率は低く,あまり理解されていなかった。ウと誤って解答した受験者が見受けられた。圧縮前の文字列のビット長は,文字数と各文字のビット表現のビット長である 2 との積で求められる。また,圧縮後の文字列のビット長は,文字のビット表現のビット長が文字の出現回数の多い順に 1 ビット, 2 ビット, 3 ビット, 3 ビットであり,文字の出現回数とその文字のビット長との積の総和で求められることが分かれば,正答できた。
設問 2 では, c の正答率は低く,あまり理解されていなかった。この繰返しの処理では,親が作成されていない二つの節から,親の節を作成すること,及び副プログラム SortNode が出力する nsize は,整列対象とした節の個数,すなわち親が作成されていない節の個数であることに気がつけば,正答できた。 d の正答率は低く,あまり理解されていなかった。キと誤って解答した受験者が見受けられた。副プログラムSortNodeは,親が作成されていない節を抽出する,すなわち配列 parent の要素の値が -1 の節を抽出することに気がつけば,正答できた。
設問 3 では, e の正答率は低く,あまり理解されていなかった。副プログラム Encode は葉から根まで再帰処理でたどる,すなわち根でなければ再帰処理を続けることに気がつけば,正答できた。 f の正答率は低く,あまり理解されていなかった。エと誤って解答した受験者が見受けられた。現在の節が親の左側の子であるということは,親の要素番号をもつ要素組の左側の子の要素番号が現在の要素番号と同じであるという条件に気がつけば,正答できた。
プログラムの作成においては,アルゴリズム及びプログラムの仕様を理解し,条件分岐や繰返しの条件を正しく実装する能力が,使用するプログラム言語を問わず求められるので,身につけておいてほしい。
来週もひきつづき「アルゴリズム問題」を出題します! 多くの方が苦手にしがちなので、これを機会にじっくり挑戦してみてください!
label 関連タグ免除試験を受けた 74.9% の方が、 科目A免除資格を得ています。
※独習ゼミは、受験ナビ運営のSEプラスによる試験対策eラーニングです。

今週の午後問題〔解答〕アルゴリズム 文字列の誤りの検出 2017 年度 秋期
update
今週の午後問題〔問題〕アルゴリズム 文字列の誤りの検出 2017 年度 秋期
update
今週の午後問題〔解答〕アルゴリズム ヒープの性質を利用したデータの整列 2018 年度 春期
update
今週の午後問題〔問題〕アルゴリズム ヒープの性質を利用したデータの整列 2018 年度 春期
update
今週の午後問題〔解答〕アルゴリズム 整数式の解析と計算 2018 年度 秋期
update
今週の午後問題〔問題〕アルゴリズム 整数式の解析と計算 2018 年度 秋期
update
今週の午後問題〔解答〕アルゴリズム ハフマン符号化を用いた文字列圧縮 2019 年度 春期
update
今週の午後問題〔問題〕アルゴリズム ハフマン符号化を用いた文字列圧縮 2019 年度 春期
update
今週の午後問題〔解答〕情報セキュリティ SSH による通信 2017 年度 秋期
update
今週の午後問題〔問題〕情報セキュリティ SSH による通信 2017 年度 秋期
update
- 基本情報技術者試験 の受験勉強をレポート頂ける方を募集中です!
- ツイッター で過去問を配信しています
姉妹サイト 「IT資格の歩き方」 では応用情報技術者以上の情報処理技術者試験の対策記事があります!
基本情報技術者試験を合格されたら、「IT資格の歩き方」で末永く、スキルアップにお役立てください!