平成24年春期試験午後問題 問2
問2 プログラミング
⇱問題PDF
文字列を圧縮するアルゴリズムに関する次の記述を読んで，設問1～4に答えよ。
文字列を圧縮するアルゴリズムに関する次の記述を読んで，設問1～4に答えよ。
広告
データを圧縮するアルゴリズムの一つにランレングス法がある。ランレングス法とは，同じデータが連続して現れる箇所を，そのデータと連続している回数との組に変換する方法である。文字"a"～"z"だけから成る文字列を圧縮する方法として，圧縮の表現形式の違う二つのプログラムを比較検討する。
圧縮前と圧縮後のデータを管理する方法として配列を用いる。配列の各要素には，文字データの場合は8ビット表現の文字コードが，数値データの場合は0～255の整数が格納される。圧縮前の配列を in，圧縮後の配列を out とする。配列 in の大きさは文字列の長さと等しく，2以上，255以下である。配列 out には圧縮後のデータを格納する十分な領域が確保されている。配列の添字は0から始まる。
〔圧縮方法その1〕
圧縮の表現形式として，[圧縮対象文字][連続回数]を用いる方法の処理手順を次の(1)～(5)に，そのプログラムを図1に示す。例えば，文字列"abbcccddddeeeee"を圧縮すると，a1b2c3d4e5 となる。ここで，a～zは文字データを表し，数字は対応する数値データを表す。
〔圧縮方法その2〕
圧縮の表現形式として，同じ文字が4回以上連続する場合に[圧縮対象文字][圧縮表現文字][連続回数]を用い，3回以下の場合はそのままとする方法の処理手順を次の(1)～(5)に，そのプログラムを図2に示す。圧縮表現文字には，圧縮対象文字と区別するために，圧縮対象文字として使用されない文字を使う。ここでは"*"を圧縮表現文字とする。例えば，文字列"abbcccddddeeeee"を圧縮すると abbcccd*4e*5 となる。
〔プログラムに関する考察)
二つの圧縮方法におけるデータ圧縮の効果について考える。
いま，同じ文字がn個続く確率(出現率)を表1のとおり仮定する。例えば，配列 in の大きさが100の場合，1割の10文字が連続しない一つの文字として存在する。また，4割の40文字が4個連続する文字の割合である。このとき，4個連続している文字列は10組となる。
圧縮後のデータの大きさを圧縮前のデータの大きさで割った値を圧縮比と定義する
と，この表1の場合，(圧縮方法その1〕での圧縮比はカ，〔圧縮方法その
2〕での圧縮比はキと算出できる。
〔圧縮方法その1〕の場合，圧縮対象のデータによっては，圧縮後のデータが圧縮前より大きくなってしまうことがある。①最悪の場合には，圧縮比はクとなってしまう。
圧縮前と圧縮後のデータを管理する方法として配列を用いる。配列の各要素には，文字データの場合は8ビット表現の文字コードが，数値データの場合は0～255の整数が格納される。圧縮前の配列を in，圧縮後の配列を out とする。配列 in の大きさは文字列の長さと等しく，2以上，255以下である。配列 out には圧縮後のデータを格納する十分な領域が確保されている。配列の添字は0から始まる。
〔圧縮方法その1〕
圧縮の表現形式として，[圧縮対象文字][連続回数]を用いる方法の処理手順を次の(1)～(5)に，そのプログラムを図1に示す。例えば，文字列"abbcccddddeeeee"を圧縮すると，a1b2c3d4e5 となる。ここで，a～zは文字データを表し，数字は対応する数値データを表す。
- 配列 in の初めの1文字を変数 prev に取り出す。連続回数を1にする。
- 配列 in から次の1文字を取り出し，変数 prev と比較する。配列 in から取り出す文字がない場合，処理手順(5)へ進む。
- 比較した二つの文字が等しい場合，連続回数に1を加える。等しくない場合，変数 prev と連続回数を配列 out に追加し，(2)で取り出した文字を変数 prev にコピーして，連続回数を1に戻す。
- 処理手順(2)に戻る。
- 変数 prev と連続回数を配列 out に追加する。
圧縮の表現形式として，同じ文字が4回以上連続する場合に[圧縮対象文字][圧縮表現文字][連続回数]を用い，3回以下の場合はそのままとする方法の処理手順を次の(1)～(5)に，そのプログラムを図2に示す。圧縮表現文字には，圧縮対象文字と区別するために，圧縮対象文字として使用されない文字を使う。ここでは"*"を圧縮表現文字とする。例えば，文字列"abbcccddddeeeee"を圧縮すると abbcccd*4e*5 となる。
- 配列mの初めの1文字を変数prevに取り出す。連続回数を1にする。
- 配列 in から次の1文字を取り出し，変数 prev と比較する。配列 in から取り出す文字がない場合，処理手順(5)へ進む。
- 比較した二つの文字が等しくない場合，変数 prev の連続回数だけの繰返しを表す圧縮表現を配列 out に追加し，(2)で取り出した文字を変数 prev にコピーして，連続回数を1に戻す。等しい場合，連続回数に1を加える。
- 処理手順(2)に戻る。
- 変数 prev の連続回数だけの繰返しを表す圧縮表現を配列 out に追加する。
二つの圧縮方法におけるデータ圧縮の効果について考える。
いま，同じ文字がn個続く確率(出現率)を表1のとおり仮定する。例えば，配列 in の大きさが100の場合，1割の10文字が連続しない一つの文字として存在する。また，4割の40文字が4個連続する文字の割合である。このとき，4個連続している文字列は10組となる。
圧縮後のデータの大きさを圧縮前のデータの大きさで割った値を圧縮比と定義する
と，この表1の場合，(圧縮方法その1〕での圧縮比はカ，〔圧縮方法その
2〕での圧縮比はキと算出できる。
広告
設問1
文字列"xyyyzzzzxxyzzzzz'の圧縮について，(1)，(2)に答えよ。
- 〔圧縮方法その1〕によって圧縮した結果を答えよ。
- 〔圧縮方法その2〕によって圧縮した結果を答えよ。
解答例・解答の要点
- x1y3z4x2y1z5
- xyyyz*4xxyz*5
解説
- 問題文に例示されている"abbcccdddeee"を〔圧縮方法その1〕で圧縮したときの圧縮前後の配列表現は以下の通りです。〔圧縮方法その1〕では、単純に[圧縮対象文字][連続回数]の形式に圧縮します。この方法に従うと、文字列"xyyyzzzzxxyzzzzz"は以下のように圧縮されます。
- xが1回連続しているため、x1
- yが3回連続しているため、y3
- zが4回連続しているため、z4
- xが2回連続しているため、x2
- yが1回連続しているため、y1
- zが5回連続しているため、z5
∴x1y3z4x2y1z5 - 問題文に例示されている"abbcccdddeee"を〔圧縮方法その2〕で圧縮したときの圧縮前後の配列表現は以下の通りです。〔圧縮方法その2〕では、同じ文字の連続が3回以下の場合はそのまま出力し、4回以上連続する場合には[圧縮対象文字]*[連続回数]の形式に圧縮します。この方法に従うと、文字列"xyyyzzzzxxyzzzzz"は以下のように圧縮されます。
- xが1回連続しているため、そのままで、x
- yが3回連続しているため、そのままで、yyy
- zが4回連続しているため、圧縮して、z*4
- xが2回連続しているため、そのままで、xx
- yが1回連続しているため、そのままで、y
- zが5回連続しているため、圧縮して、z*5
∴xyyyz*4xxyz*5
広告
設問2
図1中のア～イに入れる適切な字句を答えよ。
解答例・解答の要点
ア：in[i]とprevが等しい
イ：k＋2
イ：k＋2
解説
〔アについて〕図1の6～7行目に着目すると、[ア]の条件を満たす場合は runLength に1を加える処理を行うことがわかります。ここで runLength は連続回数を表す変数です。
問題文の〔圧縮方法その1〕(3)より、圧縮方法その1では、取り出した文字とその前の文字が等しい場合に、連続回数に1を加えることがわかります。よって、[ア]には「取り出した文字とその前の文字が等しい場合」という条件が入ると判断できます。
このアルゴリズムではfor文で配列 in の文字を1つずつ取り出して比較していくため、"取り出した文字"はループ変数iを使って in[i] と表せます。"その前の文字"は、問題文の〔圧縮方法その1〕(3)にある「(2)で取り出した文字を変数 prev にコピーして…」という記述から、変数 prev に格納されていることがわかります。
- "取り出した文字" … in[i]
- "その前の文字" … prev
∴ア＝in[i]とprevが等しい
〔イについて〕
図1の11行目に着目すると、[イ]を変数 k に代入しています。この変数 k が何のために使われているかを考えるためにプログラムを見ると、図1の9行目で、配列 out のk番目に変数 prev を代入しています。このことから、変数 k は、配列 out 中で次にデータを代入する位置（添字）を保持する変数であると判断できます。すなわち、[イ]を含む行は、次にデータを代入する添字を更新する処理ということになります。
図1の9～10行目では、配列 out のk番目とk＋1番目に圧縮後のデータ（圧縮対象文字と連続回数）を代入しています。次にデータを代入する位置（添字）は、k を2つ進めたk＋2番目となるので、ここでは k を k＋2 で更新しておかなければなりません。
したがって、[イ]には「k＋2」が当てはまります。
∴イ＝k＋2
広告
設問3
図2中のウ～オに入れる適切な字句を答えよ。
解答例・解答の要点
ウ：in[i]とprevが等しくない
エ：prev←in[i]
オ：runLengthが3以下
エ：prev←in[i]
オ：runLengthが3以下
解説
〔ウについて〕図2の6～9行目に着目すると、[ウ]の条件を満たす場合に、outputRun 関数を呼び出していることがわかります。outputRun 関数は、「prev が runLength 回繰り返すことを表す圧縮表現を配列 out の添字 k の位置に追加し，次の追加位置を返す」関数です。この outputRun 関数の処理は、問題文の〔圧縮方法その2〕(3)より、「比較した二つの文字が等しくない場合」に行う処理であることがわかります。
図2のプログラムも図1のプログラムと同様に、配列 in から1文字ずつ取り出しながら変数 prev と比較することを繰り返しているので、
- "取り出した文字" … in[i]
- "その前の文字" … prev
∴ウ＝in[i]とprevが等しくない
〔エについて〕
[エ]は、[ウ]の条件である「in[i]とprevが等しくない」場合に行う処理です。〔圧縮方法その2〕(3)には、比較した二つの文字が等しくない場合に行う処理として以下の3つが記述されています。
- 変数 prev の連続回数だけの繰返しを表す圧縮表現を配列 out に追加する
- (2)で取り出した文字を変数 prev にコピーする
- 連続回数を1に戻す
したがって、[エ]には「prev←in[i]」が当てはまります。
∴エ＝prev←in[i]
〔オについて〕
outputRun 関数の3～6行目に着目すると、[オ]の条件を満たす場合には、配列 out に変数 prev の文字を runLength 回代入していることがわかります。圧縮表現は、連続回数が3以下のときには圧縮対象文字を連続回数だけ繰り返した文字列、連続回数が4以上のときには[圧縮対象文字]*[連続回数]の形式の文字列であるため、[オ]の条件を満たすとき行う処理は、同じ文字の連続が3回以下のときの処理に対応していることがわかります。
したがって、[オ]には「runLengthが3以下」が当てはまります。
∴オ＝runLengthが3以下
広告
設問4
〔プログラムに関する考察〕について，(1)，(2)に答えよ。
- カ～クに入れる適切な数値を答えよ。
- 本文中の下線①とは，どのような場合か，20字以内で答えよ。
解答例・解答の要点
- カ：0.8
キ：0.9
ク：2
- 同じ文字が連続することが無い場合 (16文字)
解説
- 〔カについて〕
配列 in の大きさを100として、圧縮方法その1で圧縮した場合の、圧縮後のデータの大きさを考えます。- 1個続くのは、100×0.1＝10文字 (1文字×10ペア)
- 2個続くのは、100×0.2＝20文字 (2文字×10ペア)
- 3個続くのは、100×0.3＝30文字 (3文字×10ペア)
- 4個続くのは、100×0.4＝40文字 (4文字×10ペア)
80÷100＝0.8
したがって、[カ]には「0.8」が当てはまります。
∴カ＝0.8
〔キについて〕
同様に、配列 in の大きさを100として、〔圧縮方法その2〕で圧縮した場合の、圧縮後のデータの大きさを考えます。
ペア数は[カ]で示した数と同じですが、〔圧縮方法その2〕では、連続回数が3文字以下の場合はそのままで、4文字以上の連続の場合に[圧縮対象文字]*[連続回数]の3文字に圧縮します。つまり、4個続くペアのみ「3文字×10ペア＝30文字」に圧縮されます。これより、圧縮後のデータの大きさは「10＋20＋30＋30＝90文字」となります。
圧縮比は、
90÷100＝0.9
したがって、[キ]には「0.9」が当てはまります。
∴キ＝0.9
〔クについて〕
〔圧縮方法その1〕では、連続する文字を[圧縮対象文字][連続回数]の2文字に圧縮します。しかし、1文字だけの場合にも2文字にしてしまうため、連続しない一つの文字が多ければ逆に圧縮後のデータの大きさは増えることになってしまいます。極端な話、連続する文字が全くなければ、全部の文字を1文字から2文字にしてデータの大きさを2倍にしてしまうことになります。これが、問題文中で示している"最悪の場合"です。このとき、圧縮後のデータの大きさは、圧縮前のデータの大きさの2倍になっているので、圧縮比は「2」になります。
したがって、[ク]には「2」が当てはまります。「200%」でも問題ないでしょう。
∴ク＝2 - [ク]の解説で説明したように、"最悪の場合"とは、圧縮前のデータ中に連続する文字が存在せず、全部の文字を1文字から2文字にして圧縮後のデータの大きさを圧縮前の2倍にしてしまう場合です。
∴同じ文字が連続することが無い場合
広告
広告