アルゴリズム問題 出題テーマの仕組みがわかれば 50 % 以上正解できる「ハフマン符号を用いた文字列圧縮」


2022-04-08 更新

error

この記事は基本情報技術者試験の旧制度( 2022 年以前)の記事です。
この記事の題材となっている「午後問題」は現在の試験制度では出題されません。 ご注意くださいませ。

基本情報技術者試験の受験者の多くは、午後試験のアルゴリズム問題を苦手としています。 しかし、その苦手なアルゴリズム問題で、 50 % 以上の正解が得られないと、合格は望めないでしょう。

この連載では、これまでに実施された基本情報技術者試験の過去問題を例にして、最低でも 50 % 正解できる解き方を紹介します。

今回は、平成 31 年度 春期 問 8 「ハフマン符号を用いた文字列圧縮」を取り上げます。

試験の出題テーマをしっかりと学習しておく

「ハフマン符号を用いた文字列圧縮」というタイトルを見てどう思いましたか。 もしも、「えっ? ハフマン符号なんて知らないよ!」と思われたなら、それではいけません。

基本情報技術者試験には、試験の出題テーマの細目を示したシラバスという資料があります。 この中に「ハフマン符号」という言葉が、ちゃんと示されています。 そのため午前試験の問題でも、ハフマン符号が取り上げられたことがあります。

以下に例を示します。 この問題の正解は、選択肢エです。

図 ハフマン符号は午前試験に出たこともある

問 4 平成 30 年度 秋期 午前

出現頻度の異なる A , B , C , D , E の 5 文字で構成される通信データを,ハフマ
ン符号化を使って圧縮するために,符号表を作成した。 a に入る符号として,適切なものはどれか。

文字 出現頻度(%) 符号
A 26 00
B 25 01
C 24 10
D 13 a
E 12 111

ア 001  イ 010  
ウ 101  エ 110

試験の出題者は、シラバスに示されていることは、受験者が知っていることとして、詳しい説明なしで出題します。 ですから、試験の出題テーマは、しっかりと学習しておくべきです。

シラバスに示されているのは、出題テーマの細目と用語例だけなので、シラバスを見て学習するわけにはいきません。 基本情報技術者試験の対策本(市販書籍)で学習することをお勧めします。 試験の主な出題テーマ(よく出る出題テーマ)が、網羅されているからです。

アルゴリズムは手作業でやってみて体得するもの

アルゴリズムは、暗記して覚えるものではありません。 実際に手作業でやってみて、体得するものです。

先ほどの午前問題を例にして、ハフマン符号の作り方の手順(アルゴリズム)を説明しますので、紙の上に絵を描いて、実際にやってみてください。

ハフマン符号は、文字列を圧縮するための技法です。

通常の符号化では、どの文字にも同じビット数(固定長のビット数)を割り当てますが、ハフマン符号では、出現頻度が少ない文字ほど長いビット数(逆に言うと、出現頻度が多い文字ほど短いビット数)に符号化します。

この符号化では、ハフマン木を使います。 ハフマン木は、出現頻度が少ない文字ほど、そこにたどり着くまでの枝の数が多くなるようにした二分木( 2 つに枝分かれした木)です。

 

先ほどの午前問題では、文字の出現頻度が、

A = 26 %
B = 25 %
C = 24 %
D = 13 %
E = 12 %

です。

  1. これらの文字を出現頻度の多い順に書き並べて、末端の葉( leaf )とします
  2. 出現頻度の少ない順に 2 つずつ結んで節( node )を作ります。 この節には、 2 つの文字の出現頻度の合計値を書き込みます
  3. 同じ手順を、すべての文字と節を結んで根( root )ができるまで繰り返せば、ハフマン木が出来上がります

以下に上記の手順を図示します。

  1. 文字を出現頻度の多い順に書き並べる

  2. 出現頻度の少ない順に 2 つずつ結んで節を作り、 2 つの文字の出現頻度の合計値を書き込む

  3. 同じ手順を、すべての文字と節を結んで根ができるまで繰り返せば、ハフマン木が出来上がる

ハフマン木が作成できたら、根からスタートして、左に 0 を、右 1 を割り当て、根から目的の文字までの 0 と 1 を書き並べたものが、ハフマン符号になります。

根から左に 0 右に 1 を割り当てる

以下のように、 A 、 B 、 C 、 D 、 E という文字のハフマン符号は、それぞれ 00 、 01 、 10 、 110 、 111 です。 ここでは、 D にたどる例を示しています。

ハフマン木をたどってハフマン符号を得る

仕組みが分かっていればできる問題に確実に正解する

前置きが長くなりましたが、平成 31 年度 春期 午後 問 8 「ハフマン符号を用いた文字列圧縮」を見てみましょう。

以下に、問題と解答へのリンクがありますので、問題にざっと目を通してください。 じっくり見ると時間がかかりますので、ざっとで OK です。

平成 31 年度 春期 午後 問題 解答

この問題で注目してほしいのは、プログラムの穴埋め(空欄 c 、 d 、 e 、 f )もありますが、冒頭の空欄 a と b は、ハフマン符号の仕組みが分かっていればできることです。 それなら、冒頭の空欄 a と b に確実に解くことに集中しましょう。

空欄は、全部で 6 つあるので、空欄 a と b に正解して、残りの空欄 c 、 d 、 e 、 f の 1 つ以上に運よく正解できれば、全体の 50 % に達します。

 

以下は、問題に示されたハフマン木の例です。

注記 丸の中の数値は各節がもつ値を表す。 “A” ~ “D” は葉に対応する文字を表す。
図 1  文字列 α に対応するハフマン木の例

先ほどの午前問題で示したハフマン木と比べて若干の違いがあり、出現頻度が多い文字を右側にしています(根からスタートして、左に 0 を、右 1 を割り当てるのは同じです)。 これは、問題に示されたプログラムの内容に合わせたからでしょう。

ただし、ハフマン符号の作り方の手順を体得していれば、この例に合わせてハフマン木を作れるはずです。

 

以下は、空欄 a 、 b がある設問 1 です。

設問 1

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

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

圧縮率 =

ハフマン符号化によって圧縮したときの総ビット長

2 ビットの固定長で表現したときの総ビット長

a に関する解答群

文字 A B C D
ビット表現 010 1 00 011

文字 A B C D
ビット表現 010 0 01 111

文字 A B C D
ビット表現 100 0 101 11

文字 A B C D
ビット表現 100 1 00 01

b に関する解答群

ア 0.77  イ 0.85  
ウ 0.88  エ 0.92

文字の出現頻度は、

A = 1
B = 7
C = 3
D = 2

です。

これらを、この問題の例に合わせたハフマン木にすれば、空欄 a 、 b を解くことができます。 さあ、紙の上に絵を描いて、やってみましょう。

 

以下に、出来上がったハフマン木を示します。

図 設問 1 の例 “ABBBBBBBCCCDD” に合わせて作成したハフマン木
空欄 a

A 、B 、 C 、 D という文字のハフマン符号は、それぞれ 010 、 1 、 00 、 011 です。

したがって、空欄 a の正解は、選択肢アです。

空欄 b

A 、 B 、 C 、 D という文字を 2 ビットの固定長で表現すると、全体で 13 文字あるので、

2 × 13 = 26 ビット

です。

ハフマン符号で表現した場合は、

010 という 3 ビットの A が 1 文字
1 という 1 ビットの B が 7 文字
00 という 2 ビットの C が 3 文字
011 という 3 ビットの D が 2 文字

なので、全体で

3 × 1 + 1 × 7 + 2 × 3 + 3 × 2 = 22 ビット

です。

圧縮率は、

22 ÷ 26 ≒ 0.85

です。 したがって、空欄 b の正解は、選択肢イです。 できましたね!

今回は、「試験の出題テーマをしっかりと学習しておく」ということの重要性と、「仕組みが分かっていればできる問題に確実に正解する」という解き方を紹介しました。

今後も、この連載では、アルゴリズム問題で最低でも 50 % 正解できる解き方を、あれこれと紹介していきます。 少しでも、皆様の参考になれば幸いです。

それでは、またお会いしましょう!

label 関連タグ
新制度でも、
午前免除できます。
独習ゼミで科目 A 試験を免除しましょう。
免除試験を受けた 86% の方が、
1 年間の午前免除資格を得ています。
午前免除試験 最大 2 回の
受験チャンス !
info_outline
午前免除試験 最大 2 回の
受験チャンス !
詳しく見てみるplay_circle_filled
label これまでの『アルゴリズム問題で半分以上正解できる解き方』の連載一覧 label 著者