ハフマン符号の問題その１になります。
このあとなんですが、プログラミングの問題は１３
を解説して終わろうかと思います。残り３回で終わ
りますよ。
いや、そうじゃないだろ！という方。希望の言語と
かありますかね？お知らせくださいませ〜！
午後の問題を少しずつ解説していく連載です。
・赤字は「私ならここに線を引くなぁ」という場所。
・青字は私が考えたことや注釈などです。
皆さんも一緒に問題を読みながら、解答の方法をトレ
ースしてみていただけたら、幸いです。
問８ ハフマン符号
ハフマン符号化を用いた文字列圧縮に関する次の記述
を読んで、設問１～３に答えよ。
”Ａ”～”Ｄ”の４種類の文字から成る文字列をハフマン
符号化によって圧縮する。ハフマン符号化では、出現
回数の多い文字には短いビット列を、出現回数の少な
い文字には長いビット列を割り当てる。ハフマン符号
化による文字列の圧縮手順は、次の（１）～（４）の
とおりである。
（１）
文字列中の文字の出現回数を求め、出現回数表を作成
する。例えば、文字列
”ＡＡＡＡＢＢＣＤＣＤＤＡＣＣＡＡＡＡＡ”
（以下、文字列ａという）中の文字の出現回数表は、
表１のとおりになる。
（２）
文字の出現回数表に基づいてハフマン木を作成する。
ハフマン木の定義は、次のとおりである。
・節と枝で構成する二分木である。
・親である節は、子である節を常に二つもち、子の節
の値の和を値としてもつ。
・子をもたない節（以下、葉という）は文字に対応し、
出現回数を値としてもつ。
・親をもたない節（以下、根という）は、文字列の文
字数を値としてもつ。
文字列αに対応するハフマン木の例を、図１に示す。
ハフマン木は、次の手順で配列によって実現する。
１ 節の値を格納する１次元配列を用意する。
２ 文字の出現回数表に基づいて、各文字に対応する
葉の値を、配列の先頭の要素から順に格納する。
X[10,2,3,4]
３ 親が作成されていない節を二つ選択し、選択した
順に左側の子、右側の子とする親の節を一つ作成
する。この節の値を、配列中で値が格納されてい
る最後の要素の次の要素に格納する。節の選択は
節の値の小さい順に行い、同じ値をもつ節が二つ
以上ある場合は、配列の先頭に近い要紫に値が格
納されている節を選択する。
X[10,2,3,4]ならば2,3で作る
X[10,2,3,4,5] 10と4
X[10,2,3,4,5,14] 5と14
X[10,2,3,4,5,14,19]おしまい！
４ 親が作成されていない節が一つになるまで③を繰
り返す。
これね。流れ図を作ったほうがいいやつですよ。
（３）
ハフマン木から文字のビット列（以下、ビット表現と
いう）を次の手順で作成する。
１ 親と左側の子をつなぐ枝に０、右側の子をつなぐ
枝に１の値をもつビットを割り当てる。
２ 文字ごとに根から対応する葉までたどったとき、
枝のビット値を順に左から並べたものを各文字の
ビット表現とする。
図２に示すとおり、根から矢印のようにたどると、文
字列αの文字”Ｂ”のビット表現は０１０となる。
文字列の全ての文字を（３）で得られたビット表現に
置き換えて、ビット列を作成する。
図で言うと、上から下ですね。
設問１
次の記述中の（ ）に入れる正しい答えを、解答群
の中か１ら選べ。
文字列”ＡＢＢＢＢＢＢＢＣＣＣＤＤ”を、ハフマン
符号化を用いて表現する。各文字とビット表現を示し
た表は（ ａ ）である。ハフマン符号化によって圧
縮すると、文字”Ａ”～”Ｄ”をそれぞれ２ビットの固定
長で表現したときの当該文字列の総ビット長に対する
圧縮率は（ ｂ ）となる。ここで、圧縮率は次式で
計算した値の小数第３位を四捨五入して求める。
設問１
文字列”ＡＢＢＢＢＢＢＢＣＣＣＤＤ”を、ハフマン
符号化を用いて表現する。各文字とビット表現を示し
た表は（ ａ ）である。ハフマン符号化によって圧
縮すると、文字”Ａ”～”Ｄ”をそれぞれ２ビットの固定
長で表現したときの当該文字列の総ビット長に対する
圧縮率は（ ｂ ）となる。ここで、圧縮率は次式で
計算した値の小数第３位を四捨五入して求める。
出現率は
A１ B７ C3 D2
配列に入れると
X[1,7,3,2]
枝を作っていきます1と2
X[1,7,3,2,3] 3と3
X[1,7,3,2,3,3,6]7と6
X[1,7,3,2,3,3,6,13]
ゆえに
6(0) 7B(1)
3C(0) 3(1)
1A(0) 2D(1)
こんな感じなので
A010 B1 C00 D011
ａ ア
総ビット数は１３文字なので２ビット 26bit
圧縮すると010100011 に出現回数を掛けます
A１*3bit B７*1bit C3*2bit D2*3bit なので
22/26= 0.85が一番近い数字です。
ｂ イ
（次回に続く！）
