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

矢沢 久雄
2022-04-08 更新

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

この符号化では、ハフマン木を使います。 ハフマン木は、出現頻度が少ない文字ほど、そこにたどり着くまでの枝の数が多くなるようにした二分木（ 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 を書き並べたものが、ハフマン符号になります。

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

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

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

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

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

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

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

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

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

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

文字の出現頻度は、

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

です。

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

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

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

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

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 % 正解できる解き方を、あれこれと紹介していきます。 少しでも、皆様の参考になれば幸いです。

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

アルゴリズム問題 2進数がわかれば 50 ％ 以上正解できる「符号付き2進数の乗算」

update 2022-05-06

アルゴリズム問題 具体化すれば 50 ％ 以上正解できる「ビットの検査」

update 2022-05-06

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

update 2022-04-08

アルゴリズム問題 こんなもん出来るかと思う問題でも 50 ％ 以上正解する「 Bitap 法による文字列探索」

update 2022-04-08

矢沢 久雄

『プログラムはなぜ動くのか』（日経BP）が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”

大手電気メーカーでＰＣの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識０ベースのＩＴエンジニアや一般書店フェアなどの一般的なＰＣユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。

主な著作物

• 「プログラムはなぜ動くのか」（日経BP）
• 「コンピュータはなぜ動くのか」（日経BP）
• 「出るとこだけ! 基本情報技術者」 (翔泳社)
• 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」（翔泳社）
• 「ｉｆとｅｌｓｅの思考術」（ソフトバンククリエイティブ）　など多数