基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成16年 春期 基本情報技術者 午後 問03
問03   文字列の圧縮

設問 1,2 に答えよ。

ハフマン符号化は,圧縮対象の文字列を構成する文字の種類に注目し, その出現回数の偏りを利用した圧縮方法である。 今,図1に示す 100 文字からなる文字列の圧縮を考える。 全角1文字を 16 ビット(2バイト)で表現する方式の場合,この文字列は, 100 文字なので,1,600 ビットの長さである。 ここで,この文字列を構成する文字の種類とその出現回数は,図2に示すとおりであるとする。

あんたがたどこさ△ひごさ△ひごどこさ△  〜(中略)〜   
くってさ△それをこのはでちょっとかくせ

   図1 対象となる文字列(△は空白を示す)

   図2 文字の種類と出現回数

基本情報技術者試験


設問1 次の記述中の に入れる正しい答えを,解答群の中から選べ。

対象となる文字列は,図2に示すように,37 種類の文字から構成されている。 37 種類の文字を固定長のビット列を用いて識別するためには,1種類の文字に ビットのビット列を対応させればよく, 対象となる文字列は, ビット/文字× 100 文字で 計算される長さで表現できる。 このとき,対象となる文字列の長さは,表に示すように,全角1文字を 16 ビットで表現する方式の場合を 100 %とすると, %となる。

   表 文字の表現方式と対象文字列の長さ

表現の方式 1文字の長さ
ビット
対象の文字列の長さ
ビット
圧縮の割合
全角1文字を 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

解答 a ←クリックすると正解が表示されます

解答 b ←クリックすると正解が表示されます

基本情報技術者試験


〔ハフマン符号化の手順〕 文字の出現回数の偏りを利用したハフマン符号化を用いれば, この文字列を更に短いビット列で表現することができる。 この文字列をハフマン符号化する手順は,次のとおりである。

(1) 文字列を構成する文字の種類を,その出現回数の多い順に並べ替える。 同じ出現回数の場合は,文字コードの昇順とする。 また,(2) で説明する仮想の文字の場合,出現回数が同じであるときの順序は, 並べ替える直前の順序に従うものとする。

(2) (1) の並べ替えの結果,最下位になった文字とその一つ上位の文字の 2文字をグループ化し,これを仮想の1文字として扱い,最下位に位置付ける。 この仮想の文字の出現回数は,グループ化した2文字の出現回数の和とする。

(3) (2) の結果,すなわち,文字の種類が一つ減った状態のものに対し,(1),(2) を, 文字の種類が2種類になるまで繰り返す。

(4) (3) で,最後に残った2種類の文字のそれぞれに,長さ1のビット列1又は 0 を対応させる。

(5) (4) の2種類の文字から戻りながら各文字にビット列を対応させる。

 (i)  1段階戻ったときの2種類の文字に対しては,直前の段階のビット列の右端に 1 又は 0 を付加したビット列をそれぞれ対応させる。

 (ii) 元の 37 種類すべての文字にビット列が対応するまで (i) を行う。

(6) この 37 種類のビット列を用いて,対象となる文字列を表現する。

基本情報技術者試験


設問2 次の記述中の に入れる正しい答えを,解答群の中から選べ。

(1) 〜 (3) の実際の操作は,図3に示すとおりである。 ここで,@ は, であり, A は, である。 最終的に各文字に対応するビット列は,図4に示すとおりとなり, 100 文字からなる圧縮対象の文字列の長さは,全角1文字を 16 ビットで 表現する方式の場合の約 %のビット数で 表現できることになる。

   図3 実際の操作

このように,ハフマン符号化では,各文字に対応するビット列の長さが, その出現回数によって変わるが,符号化したビット列を先頭から見ていくことで, 各文字に対応するビット列が一意に識別できるので,その復元は単純なアルゴリズムで 実現できる。

  図4 文字の出現回数と対応するビット列に関する情報

c,d に関する解答群

ア 25    イ 32    ウ 43    エ 57    オ 100

e に関する解答群

ア 3.0     イ 7.0    ウ 18.8    エ 30.3    オ 43.8

カ 50.0    キ 80.7    ク 85.7

解答 c ←クリックすると正解が表示されます

解答 d ←クリックすると正解が表示されます

解答 e ←クリックすると正解が表示されます


[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]