![]()
平成16年 春期 基本情報技術者 午後 問03
問03 文字列の圧縮設問 1,2 に答えよ。 ハフマン符号化は,圧縮対象の文字列を構成する文字の種類に注目し, その出現回数の偏りを利用した圧縮方法である。 今,図1に示す 100 文字からなる文字列の圧縮を考える。 全角1文字を 16 ビット(2バイト)で表現する方式の場合,この文字列は, 100 文字なので,1,600 ビットの長さである。 ここで,この文字列を構成する文字の種類とその出現回数は,図2に示すとおりであるとする。
図1 対象となる文字列(△は空白を示す)
図2 文字の種類と出現回数 設問1 次の記述中の
対象となる文字列は,図2に示すように,37 種類の文字から構成されている。
37 種類の文字を固定長のビット列を用いて識別するためには,1種類の文字に
表 文字の表現方式と対象文字列の長さ
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) の並べ替えの結果,最下位になった文字とその一つ上位の文字の 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に示すとおりである。
ここで,@ は,
図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
[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]
©2004-2024 情報処理試験.jp
|
プライバシーポリシー・著作権・リンク
|
お問合わせ
| |||||||||||||