![]()
平成25年 秋期 基本情報技術者 午後 問08
問08 必須問題問8 次のプログラムの説明及びプログラムを読んで,設問1,2に答えよ。 〔プログラムの説明〕 英字 A 〜 Z から構成される文字列を圧縮する副プログラム Compress,及び 圧縮された文字列を復元する副プログラム Decompress である。 〔圧縮処理の説明〕 副プログラム Compress では,配列 Plaindata に格納されている圧縮前の文字列を受け取り, 圧縮後の文字列を配列 Compresseddata に格納する。図1に示す文字列 “ABCDEFABCDABCDEF”を例として,圧縮処理の内容を説明する。
![]() 図1 圧縮前の文字列 (1) 図1の圧縮前の文字列“ABCDEFABCD…”のように,“ABCD”という 同じ文字の並びが複数回出現する場合,二つ目以降の“ABCD”を圧縮列に 置き換えることによって,文字列の長さを短くする。図1では,Plaindata に 格納されている圧縮前の文字並び (s1),(s2) を圧縮列 (s1'),(s2') に置き換えて Compresseddata に格納している。 (2) 圧縮列は,制御記号,距離,文字数の三つの部分から成る。 A 距離と文字数は,圧縮前の文字列において,“この場所の文字並びは,何文字 前(距離)の文字から始まる何文字の長さ(文字数)の文字並びと同じである” という内容を意味する。距離と文字数の最大値は 26 とし,1,2,…,26 を A, B,…,Z で表す。図1の例では,圧縮前の文字並び (s1) は,(s1) の先頭文字の 6文字前から始まる長さ4の文字並び“ABCD”と一致するので,圧縮列 (s1') は “$JF”となる。また,圧縮前の文字並び (s2) は,(s2) の先頭文字の 10 文字前から 始まる長さ6の文字並び“ABCDEF”と一致するので,圧縮列 (s2') は“$JF”となる。 (3) 圧縮処理は,配列 Plaindata に格納されている圧縮前の文字列中で,圧縮する 文字並びを検索する検索処理と,検出した文字並びを圧縮列に置き換えて配列 Compresseddata に格納する置換処理から成る。 (4) 圧縮する文字並びの検索処理の内容を次に示す。
![]() 図2 最初の圧縮文字位置 A 圧縮文字並びの比較対象とする文字並びを比較文字並び,比較文字並びの 先頭位置を比較文字位置という。最初の比較文字位置は,図3に示すように 圧縮文字位置の4文字前とする。 ![]() 図3 最初の比較文字位置 B 比較文字位置を文字列の先頭に向かって,圧縮文字位置から最大 26 文学前まで 移動させながら,次の (a),(b) を行う。
図4は,圧縮文字位置が7文字目のときに,比較文字位置を文字列の先頭に 向かって p1,p2,p3 と移動しながら, 一致する文字を検索している様子を示している。 比較文字位置 p1と,p2 では,1文字目が一致していない。 比較文字位置 p3 では1文字目が一致し,一致する文字数は4となる。
![]() 図4 文字列の比較 (b) 圧縮する文字並びは,それよりも前にある比較文字並びの中で,一致する 文字数が4以上で最も多い比較文字並びとする。圧縮する文字並びの対応例を 図5に示す。図5では,圧縮文字位置から始まる圧縮文字並び “ABCD…” と, それよりも前方に出現する比較文字並びの中で,一致する文字数が4以上の 比較文字並びは,4文字前の (s1)“ABCD”と 10 文字前の (s0)“ABCDEF”である。したがって,一致する文字数が多い (s0) に 対応させて,(s2)“ABCDEF”を圧縮列に置き換えることになる。
![]() 図5 圧縮する文字並びの対応例 (5) (4) の検索処理の結果に対する置換処理の内容を次に示す。 A 一致する文字数が4以上の場合には,その文字数が最も多い比較文字並びに 対応する圧縮列を配列 Compresseddata に格納する。 Compress の引数の仕様は,次のとおりである。各配列の添字は,0 から始まる。
〔復元処理の説明〕 副プログラム Decompress では,配列 Compresseddata に格納されている圧縮された 文字列を受け取り,復元後の文字列を配列 Plaindata に格納する。復元処理の内容を次に示す。 (1) 配列 Compresseddata の先頭から圧縮された文字列を順に調べる。 (2) 文字が制御記号でなければ,その文字をそのまま配列 Plaindata に格納する。 (3) 文字が制御記号ならば,圧縮列の距離,文字数から,圧縮前の文字並びを 復元して配列 Plaindata に格納する。 〔副プログラム Decompress の引数の仕様〕 Decompress の引数の仕様は,次のとおりである。各配列の添字は,0 から始まる。
副プログラム Compress と Decompress で使用している関数 IntToAlphabet と AlphabetToInt の仕様は,次のとおりである。 〔関数 IntToAlphabet の仕様〕 整数1〜 26 を順に英字 A 〜 Z に変換する。IntToAlphabet の引数と返却値の仕様は, 次のとおりである。
〔関数 AlphabetToInt の仕様〕 英字 A 〜 Z を順に整数1〜 26 に変換する。AlphabetToInt の引数と返却値の仕様は,次のとおりである。
〔プログラム1〕
〔プログラム2〕
設問1 プログラム中の a に関する解答群 ウ Plength − Distance ≧ 0 エ Plength − Pindex ≧ 0 イ Plaindata[Pindex + Distance + Fitnum] ウ Plaindata[Pindex − Distance] エ Plaindata[Pindex − Distance + Fitnum] ウ Fitnum ← Fitnum + 1 エ Pindex ← Pindex + 1 オ Plength ← Plength + 1 イ Pindex ← Pindex + 3 ウ Pindex ← Pindex + Maxdistance エ Pindex ← Pindex + Maxfitnum e に関する解答群 ア Compresseddata[Pindex + Start + Fitcnt] イ Compresseddata[Pindex − Start + Fitcnt] ウ Plaindata[Pindex + Start + Fitcnt] エ Plaindata[Pindex − Start + Fitcnt]
設問2 次の記述中の ![]()
次の文字列を圧縮した文字列を副プログラム Decompress を使って復元する場合,
プログラム2のαの部分は
f に関する解答群 エ 6 ウ 7 カ 8
[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]
©2004-2024 情報処理試験.jp
|
プライバシーポリシー・著作権・リンク
|
お問合わせ
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||