設問 1，2 に答えよ。
ハフマン符号化は，圧縮対象の文字列を構成する文字の種類に注目し， その出現回数の偏りを利用した圧縮方法である。 今，図１に示す 100 文字からなる文字列の圧縮を考える。 全角１文字を 16 ビット（２バイト）で表現する方式の場合，この文字列は， 100 文字なので，1,600 ビットの長さである。 ここで，この文字列を構成する文字の種類とその出現回数は，図２に示すとおりであるとする。
| あんたがたどこさ△ひごさ△ひごどこさ△ ～（中略）～
くってさ△それをこのはでちょっとかくせ |
図１ 対象となる文字列（△は空白を示す）
図２ 文字の種類と出現回数
設問１ 次の記述中の 
に入れる正しい答えを，解答群の中から選べ。
対象となる文字列は，図２に示すように，37 種類の文字から構成されている。
37 種類の文字を固定長のビット列を用いて識別するためには，１種類の文字に
ビットのビット列を対応させればよく，
対象となる文字列は，
ビット／文字× 100 文字で
計算される長さで表現できる。
このとき，対象となる文字列の長さは，表に示すように，全角１文字を
16 ビットで表現する方式の場合を 100 ％とすると，
％となる。
表 文字の表現方式と対象文字列の長さ
| 表現の方式 | １文字の長さ ビット |
対象の文字列の長さ ビット |
圧縮の割合 ％ |
| 全角１文字を 16 ビットで表現 | 16 | 1,600 | 100 |
| 37 種類の文字を固定長で表現 | |
（省略） | |
a に関する解答群
ア 1 イ 6 ウ 7 エ 16 オ 20
カ 33 キ 37 ク 47 ケ 100
b に関する解答群
ア 2.3 イ 6.0 ウ 6.3 エ 16.2 オ 16.7
カ 37.0 キ 37.5 ク 43.2
〔ハフマン符号化の手順〕 文字の出現回数の偏りを利用したハフマン符号化を用いれば， この文字列を更に短いビット列で表現することができる。 この文字列をハフマン符号化する手順は，次のとおりである。
(1) 文字列を構成する文字の種類を，その出現回数の多い順に並べ替える。 同じ出現回数の場合は，文字コードの昇順とする。 また，(2) で説明する仮想の文字の場合，出現回数が同じであるときの順序は， 並べ替える直前の順序に従うものとする。
(2) (1) の並べ替えの結果，最下位になった文字とその一つ上位の文字の ２文字をグループ化し，これを仮想の１文字として扱い，最下位に位置付ける。 この仮想の文字の出現回数は，グループ化した２文字の出現回数の和とする。
(3) (2) の結果，すなわち，文字の種類が一つ減った状態のものに対し，(1)，(2) を， 文字の種類が２種類になるまで繰り返す。
(4) (3) で，最後に残った２種類の文字のそれぞれに，長さ１のビット列１又は 0 を対応させる。
(5) (4) の２種類の文字から戻りながら各文字にビット列を対応させる。
(i) １段階戻ったときの２種類の文字に対しては，直前の段階のビット列の右端に 1 又は 0 を付加したビット列をそれぞれ対応させる。
(ii) 元の 37 種類すべての文字にビット列が対応するまで (i) を行う。
(6) この 37 種類のビット列を用いて，対象となる文字列を表現する。
設問２ 次の記述中の
に入れる正しい答えを，解答群の中から選べ。
(1) ～ (3) の実際の操作は，図３に示すとおりである。
ここで，① は，
であり，
② は，
である。
最終的に各文字に対応するビット列は，図４に示すとおりとなり，
100 文字からなる圧縮対象の文字列の長さは，全角１文字を 16 ビットで
表現する方式の場合の約 
％のビット数で
表現できることになる。
図３ 実際の操作
図４ 文字の出現回数と対応するビット列に関する情報
c，d に関する解答群
ア 25 イ 32 ウ 43 エ 57 オ 100
e に関する解答群
ア 3.0 イ 7.0 ウ 18.8 エ 30.3 オ 43.8
カ 50.0 キ 80.7 ク 85.7
[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]
