問題の概要
今回のテーマは「ハフマン符号化を用いた文字列圧縮」です。
問題文中の(1)～(4)の部分で考え方、文字列の圧縮手順が説明されていますので、ハフマン符号化についてあらかじめ知っている必要はありません。
問題文で説明されているハフマン符号化による文字列の圧縮手順は以下の通りです。
(1)文字の出現回数表をつくる
(2)ハフマン木をつくる
(3)文字のビット列をつくる
(4)文字列をビット列に置き換える
設問1は実際に文字列を上記の手順で符号化した結果と圧縮率を求める問題です。
設問2は(2)ハフマン木の作成、の部分をプログラムとして記述した際の内容に関する問題、
設問3は(3)文字のビット列をつくる、と(4)文字列をビット列に置き換える、の部分をプログラムとして記述した際の内容を答える問題となっています。
問題文の例や設問1で具体的なハフマン符号化の手順を理解した上で、これに矛盾しないかたちで設問2や設問3のプログラムを考えていく流れで解ける問題となっています。
ハフマン符号化の手順
まずは問題文中の(1)～(4)で例として示されている処理について確認していきます。
問題文(1)の部分では、例として文字列α="AAAABBCDCDDACCAAAAA"として、この文字列αの圧縮を実行します。
文字列αの中に含まれている"A"、"B"、"C"、"D"の出現回数を以下のように集計しています。
次に(2)の部分でハフマン木を作成します。
ハフマン木の説明は問題文に記載されており、以下です。
・節と枝で構成される二分木
・親である節は子である節を常に二つ持ち、子の節の値の和を値として持つ
・子を持たない節(葉という)は文字に対応し、出現回数を値として持つ
・親を持たない節(根という)は文字列の文字数を値として持つ
ここで二分木という言葉が出てきましたが、二分木とは親要素を起点として2つ以下の子要素に枝分かれする木構造のことです。
言葉ではちょっと分かりにくいですが、以下の図のように枝分かれしていく構造のことを指しています。
問題文にはハフマン木の作成手順と文字列αに対するハフマン木の図が記載されています。
文字列αのハフマン木の図は以下です。
この図の一番上の19が文字列αの文字数(根)となっています。
19の節である9と10について、9が"A"以外の文字数、10が"A"の文字数(葉)を表しています。
そして9の節のうち、4が"C"の文字数(葉)、5が"A"以外かつ"C"以外の文字数(つまり"B"か"D"の文字数)を表しています。
最後に5の節のうち、2が"B"の文字数(葉)、3が"D"の文字数(葉)を表しています。
では問題文に沿って、このハフマン木を配列で表現する手順を確認してみましょう。
①「節の値を格納する1次元配列を用意する」と記載されているので、[x,x,x,x]のような形式の配列を用意します。
この時点で配列に値は入っていません。
②「文字の出現回数表に基づいて各文字に対応する葉の値を配列の先頭の要素から順に格納する」と記載されているので、
配列の値は[10,2,4,3]となります。
③問題文の指示に従い、節の値が小さい順に、2と3を選択します。
そして、2を左側の子、3を右側の子として親を作成し、2と3の和である5を配列の末尾に追加します。
この時点で配列は[10,2,4,3,5]となります。
次に、親が作成されていない節で、値が小さい順に4と5を選択します。
4を左側の子、5を右側の子として親を作成し、4と5の和である9を配列の末尾に追加します。
これで配列は[10,2,4,3,5,9]となります。
同様に、親が作成されていない節で、値が小さい順に9と10を選択。
9を左側の子、10を右側の子として親を作成し、和の19を配列の末尾に追加します。
配列は[10,2,4,3,5,9,19]となります。
④「親が作成されていない節が1つになるまで③を繰り返す」とあるので、ここで③の操作は終了します。
そして(3)で、ハフマン木から文字のビット列を以下の①、②で作成します。
①「親と左側の子をつなぐ枝に0、右側の子をつなぐ枝に1の値をもつビットを割り当てる」とあります。
②「文字ごとに根から対応する葉までたどったとき、枝のビット列を順に左から並べたものを各文字のビット表現とする。」とあり、
問題文には"B"のビット表現の作成例が以下のような図で示されています。
この図を参考にそれぞれの文字をビット列に置き換えると、以下の通りです。
・"A"⇒1
・"B"⇒010
・"C"⇒00
・"D"⇒011
よって文字列αをビット列で表現すると、以下のようになります。
α=1 1 1 1 010 010 00 011 00 011 011 1 00 00 1 1 1 1 1
以上で問題文の例として記載されている文字列αのハフマン符号化手順を確認できました。
設問1について
ではここから設問について考えていきましょう。
設問1では対象の文字列を"ABBBBBBBCCCDD"として、これをハフマン符号化によって圧縮します。
問題文の例にならって、まずは文字の出現回数をカウントすると以下の通りです。
これを1次元配列に格納すると、以下となります。
[1,7,3,2]
この4つの数字の中で、最も小さい値である1を左側の子、2を右側の子として3という親を作成し、その和を配列の末尾に追加します。
この時点の配列は以下です。
[1,7,3,2,3]
これを図にすると以下の通りです。
次に、親が作成されていない節の中で最も小さい値である3が2つ選択されることになります。
問題文に記載されている通り、同じ値を選択した場合は配列の先頭に近い方を左側の子とするため、
配列の先頭に近い3を左側の子、上記で作成した3を右側の子として6という親を作成し、その和を配列の末尾に追加します。
この時点での配列は[1,7,3,2,3,6]となり、図は以下のようになります。
同様に、親が作成されていない節で小さい値を選択し、6を左側の子、7を右側の子として13という親を作成し配列の末尾に追加します。
配列は[1,7,3,2,3,6,13]となり、図は以下の通りです。
この時点で、配列の値の中で親が作成されていない値が13のみになったので、ハフマン木の作成操作は終了です。
次に、ハフマン木から文字のビット列を作成します。
上で作成したハフマン木において、親と左側の子をつなぐ枝に0、親と右側の子をつなぐ枝に1を割り当てると、以下のような図になります。
したがって、各文字に対応するビット列は以下のようになります。
A：010
B：1
C：00
D：011
よって設問aの解答は「ア」です。
続いて、文字列"ABBBBBBBCCCDD"の各文字をビット列で表現してみると以下のようになります。
"ABBBBBBBCCCDD"⇒"0101111111000000011011"
このビット長を数えてみると、22であることが分かります。
一方で、A～Dの文字列をそれぞれ2ビットの固定長で表現した場合、例えば以下のようなビット列表現が考えられます。
A：00
B：01
C：10
D：11
これによって"ABBBBBBBCCCDD"を表現した場合には1文字に対して2ビットが対応するため、ビット長は26となります。
したがって、問題文に記載されている計算式で圧縮率を計算すると、
圧縮率
=ハフマン符号化後のビット長/2ビットの固定長で表現したときのビット長
=22/26
=0.846.....
となり、少数第三位を四捨五入して、0.85となります。
よって設問bは「イ」となります。
