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

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

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

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

設問 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 であり、選択肢イが正解です。