基本情報技術者 2019年 春期 午後 問08
ハフマン符号化を用いた文字列圧縮に関する次の記述を読んで、設問1〜3に答えよ。
“A”〜“D”の4種類の文字から成る文字列をハフマン符号化によって圧縮する。ハフマン符号化では、出現回数の多い文字には短いビット列を、出現回数の少ない文字には長いビット列を割り当てる。ハフマン符号化による文字列の圧縮手順は、次の(1)〜(4)のとおりである。
(1) 文字列中の文字の出現回数を求め、出現回数表を作成する。例えば、文字列“AAAABBCDCDDACCAAAAA”（以下、文字列αという）中の文字の出現回数表は、表1のとおりになる。
(2) 文字の出現回数表に基づいてハフマン木を作成する。
ハフマン木の定義は、次のとおりである。
・節と枝で構成する二分木である。
・親である節は、子である節を常に二つもち、子の節の値の和を値としてもつ。
・子をもたない節（以下、葉という）は文字に対応し、出現回数を値としてもつ。
・親をもたない節（以下、根という）は、文字列の文字数を値としてもつ。
文字列αに対応するハフマン木の例を、図1に示す。
ハフマン木は、次の手順で配列によって実現する。
① 節の値を格納する1次元配列を用意する。
② 文字の出現回数表に基づいて、各文字に対応する葉の値を、配列の先頭の要素から順に格納する。
③ 親が作成されていない節を二つ選択し、選択した順に左側の子、右側の子とする親の節を一つ作成する。この節の値を、配列中で値が格納されている最後の要素の次の要素に格納する。節の選択は節の値の小さい順に行い、同じ値をもつ節が二つ以上ある場合は、配列の先頭に近い要素に値が格納されている節を選択する。
④ 親が作成されていない節が一つになるまで③を繰り返す。
(3) ハフマン木から文字のビット列（以下、ビット表現という）を次の手順で作成する。
① 親と左側の子をつなぐ枝に0、右側の子をつなぐ枝に1の値をもつビットを割り当てる。
② 文字ごとに根から対応する葉までたどったとき、枝のビット値を順に左から並べたものを各文字のビット表現とする。
図2に示すとおり、根から矢印のようにたどると、文字列αの文字“B”のビット表現は010となる。
(4) 文字列の全ての文字を(3)で得られたビット表現に置き換えて、ビット列を作成する。
設問1：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
文字列“ABBBBBBBCCCDD”を、ハフマン符号化を用いて表現する。各文字とビット表現を示した表はaである。ハフマン符号化によって圧縮すると、文字“A”〜“D”をそれぞれ2ビットの固定長で表現したときの当該文字列の総ビット長に対する圧縮率はbとなる。ここで、圧縮率は次式で計算した値の小数第3位を四捨五入して求める。
圧縮率 ＝
aに関する解答群
bに関する解答群
ア：0.77
イ：0.85
ウ：0.88
エ：0.92
bに関する解答群
ア：0.77
イ：0.85
ウ：0.88
エ：0.92模範解答
a：ア、b：イ
解説
解答の導き方
文字列「ABBBBBBBCCCDD」の各文字が何回出るかを数えます。Aは1回、Bは7回、Cは3回、Dは2回です。
ハフマン符号化は、出現回数の少ない文字から順にまとめて木を作り、根から葉までの道筋をビット表現にする方法です。葉は文字に対応し、左へ進む枝を0、右へ進む枝を1とします。
まず、文字を表の順に並べ、出現回数の小さい節を2つずつ選びます。同じ値の節がある場合は、「配列の先頭に近い要素」を選ぶという本文の決まりに従います。
手順2では、Cの節と手順1で作った節がどちらも3です。Cは文字の出現回数表の先にあるため、Cを左側、手順1で作った節を右側にします。手順3では、値の小さい6を左側、Bの7を右側にします。
この木を根からたどると、各文字のビット表現は次のようになります。
したがって、選択肢の表と一致するのはアです。
次に、圧縮率を計算します。ハフマン符号化後のビット長は、各文字の出現回数に、その文字のビット表現の長さを掛けて合計します。
合計は、ビットです。
文字列の文字数は、文字です。各文字を2ビットの固定長で表すと、総ビット長はビットです。
よって、圧縮率は次のとおりです。
小数第3位を四捨五入すると0.85なので、該当する選択肢はイです。
誤りやすいポイント
- 文字のビット表現は、出現回数の順に決めるのではなく、作成した木の根から葉までたどって決めます。
- 同じ値の節があるときは、配列の先頭に近い節を選びます。この問題では、Cの3と手順1で作った3を選ぶときに、この決まりが関係します。
- 圧縮率は「圧縮後のビット長」を「固定長で表したときのビット長」で割ります。逆に割ると、圧縮率になりません。
- 0.85は、元の長さの約85%になったという意味です。85%削減されたという意味ではありません。
FAQ
Q: なぜBのビット表現は1ビットなのですか？
A: Bは7回出現し、ほかの文字より多く出現します。木では根から直接葉につながるため、ビット表現が1ビットになります。
A: Bは7回出現し、ほかの文字より多く出現します。木では根から直接葉につながるため、ビット表現が1ビットになります。
Q: 同じ値の節を選ぶ順番が違うと、答えも変わりますか？
A: 木の形や文字ごとのビット表現が変わることがあります。この問題では、配列の先頭に近い節を選ぶ決まりに従うことで、選ぶ順番が定まります。
A: 木の形や文字ごとのビット表現が変わることがあります。この問題では、配列の先頭に近い節を選ぶ決まりに従うことで、選ぶ順番が定まります。
Q: 圧縮率が1より小さいと、どう考えればよいですか？
A: 圧縮後のビット長が、固定長で表したときより短いということです。この問題では、圧縮率が0.85なので、圧縮後は固定長の場合の約85%の長さです。
A: 圧縮後のビット長が、固定長で表したときより短いということです。この問題では、圧縮率が0.85なので、圧縮後は固定長の場合の約85%の長さです。
関連キーワード: ハフマン符号化、出現頻度、二分木、可変長符号、圧縮率
設問2：
問題文を見る ハフマン木を作成するプログラム1の説明及びプログラム1を読んで、プログラム1中のに入れる正しい答えを、解答群の中から選べ。
〔プログラム1の説明〕
(1) 四つの1次元配列parent、left、right及びfreqの同じ要素番号に対応する要素の組み（以下、要素組という）によって、一つの節を表す。要素番号は0から始まる。四つの配列の大きさはいずれも十分に大きく、全ての要素は−1で初期化されている。
(2) 図3に、図1に示したハフマン木を表現した場合の各配列の要素がもつ値を示す。配列parentには親、配列leftには左側の子、配列rightには右側の子を表す要素組の要素番号がそれぞれ格納され、配列freqには節の値が格納される。節が葉のとき、配列leftと配列rightの要素の値は、いずれも−1である。図3では、要素番号0〜3の要素組が、順に文字“A”〜“D”の葉に対応している。節が根のとき、配列parentの要素の値は−1である。
(3) 副プログラムHuffmanは、次の①〜⑤を受け取り、ハフマン木を表現する配列を作成する。
① 葉である節の個数size
② 初期化された配列parent
③ 初期化された配列left
④ 初期化された配列right
⑤ 初期化された後、文字の出現回数が要素番号0から順に格納された配列freq
(4) 副プログラムSortNodeは、親が作成されていない節を抽出し、節の値の昇順に整列し、節を表す要素組の要素番号を順に配列nodeに格納し、その個数を変数nsizeに格納する。行番号19〜24で親が作成されていない節を表す要素組の要素番号を抽出し、行番号25で節の値の昇順に整列する。
(5) 副プログラムSort（プログラムは省略）は、節を表す要素組の要素番号の配列nodeを受け取り、要素番号に対応する要素組が表す節の値が昇順となるように整列する。節の値が同じときの順序は並べ替える直前の順序に従う。
(6) 副プログラムHuffman、SortNode及びSortの引数の仕様を、表2〜4に示す。
c, dに関する解答群
ア：nsize ≧ 0
イ：nsize ≧ 1
ウ：nsize ≧ 2
エ：parent[i] < 0
オ：parent[i] > 0
カ：size ≦ nsize
キ：size ≧ nsize
模範解答
c：ウ、d：エ
解説
解答の導き方
このプログラムは、値の小さい節を二つずつ組み合わせて、ハフマン木を作ります。節とは、木を構成する一つ一つの部分です。配列は、番号を使って複数の値を管理する入れ物です。
まず、5行目から15行目までが繰り返し処理になっています。繰り返しの前に、4行目でSortNodeを呼び出し、親がまだ作成されていない節を集めて、値の小さい順に並べています。nsizeは、その節がいくつあるかを表します。
繰り返しの中では、node[0]とnode[1]を取り出し、新しい親の節を作ります。そのため、組み合わせる節が二つ以上ある間だけ繰り返せばよいです。節が一つになれば、二つを選べないため、処理を終えます。したがって、cに入る条件は「nsize ≧ 2」です。
次に、SortNodeの20行目を考えます。19行目では、iを0からsize−1まで動かして、各節を確認しています。親がまだない節だけをnodeに追加する必要があります。
parent[i]には、その節の親の要素番号が入ります。親がまだない場合は、初期値の−1のままです。親が作られた節には、親の要素番号が格納されています。よって、親がまだない節を判定する条件は「parent[i] < 0」です。
「parent[i] > 0」では、親の要素番号が0の節を見落とします。要素番号は0から始まるため、0も親の要素番号として使われます。
図3の例でも、文字列αの葉の値は、要素番号0から順に10、2、4、3です。最初は全ての葉のparentが−1なので、SortNodeは4個の節を集めます。値の小さい順に並べると、要素番号は1、3、2、0です。そこで、値が2と3の節を組み合わせて、新しい節を作ります。
新しい節には要素番号4が使われ、値は2＋3＝5です。要素番号1と3のparentには4が入ります。次のSortNodeでは、親がまだない要素番号0、2、4が対象になります。このように、親が作成された節は対象から外れ、新しく作った節は親がまだない間は対象に含まれます。
誤りやすいポイント
- 繰り返しの条件を「節が一つ以上ある」と考えないようにします。処理では節を二つ選ぶため、必要なのは二つ以上です。
- parent[i]が0の場合も、親が作成されています。要素番号0は有効な番号なので、「parent[i] > 0」では判定できません。
- 「親がまだない節」は、葉だけを指すわけではありません。組み合わせて作った節も、さらに親が作られるまでは候補になります。
FAQ
Q: SortNodeで、親がまだない節だけを選ぶのはなぜですか？
A: すでに親が作られた節は、別の節と重ねて選ばないようにするためです。親がまだない節は、まだ別の節と組み合わせられる候補です。
A: すでに親が作られた節は、別の節と重ねて選ばないようにするためです。親がまだない節は、まだ別の節と組み合わせられる候補です。
Q: 節が一つになったら、なぜ繰り返しを終えるのですか？
A: 残った一つの節が、完成したハフマン木の根になるからです。二つの節を選んで新しい親を作る処理は、続ける必要がありません。
A: 残った一つの節が、完成したハフマン木の根になるからです。二つの節を選んで新しい親を作る処理は、続ける必要がありません。
Q: parent[i]が−1ではなく、0未満かどうかを調べるのはなぜですか？
A: 親がないことを表す値は−1で、親の要素番号は0以上です。このため、0未満かを調べれば、親がない節を判定できます。
A: 親がないことを表す値は−1で、親の要素番号は0以上です。このため、0未満かを調べれば、親がない節を判定できます。
関連キーワード: ハフマン符号化、ハフマン木、二分木、配列、昇順整列
設問3：
問題文を見る ハフマン木から文字のビット表現を作成して表示するプログラム2の説明及びプログラム2を読んで、プログラム2中のに入れる正しい答えを、解答群の中から選べ。
〔プログラム2の説明〕
(1) ビット表現を求めたい文字に対応する葉を表す要素組の要素番号を、副プログラムEncodeの引数kに与えて呼び出すと、ハフマン木から文字のビット表現を作成して表示する。
(2) 副プログラムEncodeの引数の仕様を、表5に示す。
(3) 副プログラムEncodeは、行番号2の条件が成り立つとき、副プログラムEncodeを再帰的に呼び出す。これによって、ハフマン木を葉から根までたどっていく。
(4) 根にたどり着くと次は葉に向かってたどっていく。現在の節が親の左側の子のときは0を、右側の子のときは1を表示する。
(5) 関数printは、引数で与えられた文字列を表示する。
eに関する解答群
ア：k ≧ 0
イ：left[k] = −1
ウ：left[k] ≧ 0
エ：parent[k] = −1
オ：parent[k] ≧ 0
fに関する解答群
ア：left[k] = k
イ：left[parent[k]] = k
ウ：parent[k] = k
エ：parent[left[k]] = k
模範解答
e：オ、f：イ
解説
解答の導き方
このプログラムは、指定された文字の葉から根まで親をたどり、根に着いたあと、戻りながらビットを表示します。関数が自分自身を呼び出す処理を再帰呼出しといいます。
まず、図3の配列では、根の要素番号は6です。根には親がないため、parent[6]の値は−1です。一方、葉に対応する要素番号1から根までたどると、親は順に4、5、6です。
eに入る条件
行番号3では、parent[k]を次の呼出しの要素番号として渡しています。つまり、親があるときに限って、親をたどる必要があります。
親があることを表すのは、parent[k]が−1ではない場合です。要素番号は0以上なので、この条件は「parent[k] ≧ 0」となります。したがって、eにはオが入ります。
根に着くとparent[k]は−1です。この条件が成り立たなくなるので、そこで再帰呼出しが止まります。
fに入る条件
根までたどった後は、再帰呼出しから戻りながら、現在の節が親の左側と右側のどちらの子かを判定します。左側の子なら0、右側の子なら1を表示します。
現在の節の要素番号がkなら、その親の要素番号はparent[k]です。親の左側の子の要素番号はleft[parent[k]]に格納されています。したがって、現在の節が左側の子かどうかは「left[parent[k]] = k」で判定できます。これが成り立てば0を表示し、成り立たなければ右側の子なので1を表示します。よって、fにはイが入ります。
図3の配列を使って、文字“B”に対応する要素番号1から処理を追うと、次のようになります。
根から戻るとき、各節について左側の子かどうかを調べます。
この順に表示されるビットは010です。葉から親をたどって呼出しを進め、戻るときに表示することで、根から葉へ進む経路の順にビットを出力できます。
誤りやすいポイント
- eを「left[k] = −1」と考えないようにします。これは葉かどうかの判定です。再帰呼出しを止める条件は、親が存在しない根かどうかです。
- parent[k]が−1のときに行番号3を実行すると、親の要素番号がないまま呼出しを続けてしまいます。そのため、親がある場合にだけ再帰呼出しを行います。
- fではleft[k]ではなくleft[parent[k]]を調べます。判定したいのは、現在の節kが「親の左側の子かどうか」だからです。
- 根までたどる順と、ビットを表示する順は逆です。再帰呼出しで根まで進み、戻りながらビットを表示するため、最終的には根から葉への順で表示されます。
FAQ
Q: なぜ根では再帰呼出しを止めるのですか？
A: 根には親がありません。parent[k]が−1になるので、親をたどる処理をそこで終えます。
A: 根には親がありません。parent[k]が−1になるので、親をたどる処理をそこで終えます。
Q: 左側の子でない場合、なぜ右側の子として扱えるのですか？
A: ハフマン木は、親が子を二つもつ二分木です。現在の節は親の子のどちらかなので、左側の子でなければ右側の子です。
A: ハフマン木は、親が子を二つもつ二分木です。現在の節は親の子のどちらかなので、左側の子でなければ右側の子です。
Q: 文字“B”のビット表現が010になるのはなぜですか？
A: 図2では、根から“B”までの枝のビット値が順に0、1、0です。プログラムも戻りながら同じ順序で表示するため、010になります。
A: 図2では、根から“B”までの枝のビット値が順に0、1、0です。プログラムも戻りながら同じ順序で表示するため、010になります。
関連キーワード: ハフマン符号化、二分木、再帰呼出し、配列、条件分岐
