平成24年春期試験午後問題 問2

問2 プログラミング

⇱問題PDF
文字列を圧縮するアルゴリズムに関する次の記述を読んで,設問1~4に答えよ。
 データを圧縮するアルゴリズムの一つにランレングス法がある。ランレングス法とは,同じデータが連続して現れる箇所を,そのデータと連続している回数との組に変換する方法である。文字"a"~"z"だけから成る文字列を圧縮する方法として,圧縮の表現形式の違う二つのプログラムを比較検討する。
 圧縮前と圧縮後のデータを管理する方法として配列を用いる。配列の各要素には,文字データの場合は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 に追加する。
 図1中の関数 encode1 はプログラムのメイン処理であり,配列 out に追加されたデータの大きさを返す。
pm02_1.gif
〔圧縮方法その2〕
 圧縮の表現形式として,同じ文字が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 に追加する。
 図2中の関数 encode2 はプログラムのメイン処理であり,配列 out に追加されたデータの大きさを返す。関数 outputRun は,prev が runLength 回繰り返すことを表す圧縮表現を配列 out の添字 k の位置に追加し,次の追加位置を返す。
pm02_2.gif
〔プログラムに関する考察)
 二つの圧縮方法におけるデータ圧縮の効果について考える。
 いま,同じ文字がn個続く確率(出現率)を表1のとおり仮定する。例えば,配列 in の大きさが100の場合,1割の10文字が連続しない一つの文字として存在する。また,4割の40文字が4個連続する文字の割合である。このとき,4個連続している文字列は10組となる。
 圧縮後のデータの大きさを圧縮前のデータの大きさで割った値を圧縮比と定義する
と,この表1の場合,(圧縮方法その1〕での圧縮比は,〔圧縮方法その
2〕での圧縮比はと算出できる。
pm02_3.gif
 〔圧縮方法その1〕の場合,圧縮対象のデータによっては,圧縮後のデータが圧縮前より大きくなってしまうことがある。①最悪の場合には,圧縮比はとなってしまう。

設問1

文字列"xyyyzzzzxxyzzzzz'の圧縮について,(1),(2)に答えよ。
  • 〔圧縮方法その1〕によって圧縮した結果を答えよ。
  • 〔圧縮方法その2〕によって圧縮した結果を答えよ。

解答例・解答の要点

  • x1y3z4x2y1z5
  • xyyyz*4xxyz*5

解説

  • 問題文に例示されている"abbcccdddeee"を〔圧縮方法その1〕で圧縮したときの圧縮前後の配列表現は以下の通りです。
    pm02_4.gif
    〔圧縮方法その1〕では、単純に[圧縮対象文字][連続回数]の形式に圧縮します。この方法に従うと、文字列"xyyyzzzzxxyzzzzz"は以下のように圧縮されます。
    • xが1回連続しているため、x1
    • yが3回連続しているため、y3
    • zが4回連続しているため、z4
    • xが2回連続しているため、x2
    • yが1回連続しているため、y1
    • zが5回連続しているため、z5
    よって、文字列"xyyyzzzzxxyzzzzz"を〔圧縮方法その1〕で圧縮した結果は、これらを連結した"x1y3z4x2y1z5"となります。

    ∴x1y3z4x2y1z5

  • 問題文に例示されている"abbcccdddeee"を〔圧縮方法その2〕で圧縮したときの圧縮前後の配列表現は以下の通りです。
    pm02_5.gif
    〔圧縮方法その2〕では、同じ文字の連続が3回以下の場合はそのまま出力し、4回以上連続する場合には[圧縮対象文字]*[連続回数]の形式に圧縮します。この方法に従うと、文字列"xyyyzzzzxxyzzzzz"は以下のように圧縮されます。
    • xが1回連続しているため、そのままで、x
    • yが3回連続しているため、そのままで、yyy
    • zが4回連続しているため、圧縮して、z*4
    • xが2回連続しているため、そのままで、xx
    • yが1回連続しているため、そのままで、y
    • zが5回連続しているため、圧縮して、z*5
    よって、文字列"xyyyzzzzxxyzzzzz"を〔圧縮方法その2〕で圧縮した結果は、これらを連結した"xyyyz*4xxyz*5"となります。

    ∴xyyyz*4xxyz*5

設問2

図1中のに入れる適切な字句を答えよ。

解答例・解答の要点

ア:in[i]とprevが等しい
イ: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が等しい」が当てはまります。

=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以下

解説

について〕
図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が等しくない

について〕
[エ]は、[ウ]の条件である「in[i]とprevが等しくない」場合に行う処理です。〔圧縮方法その2〕(3)には、比較した二つの文字が等しくない場合に行う処理として以下の3つが記述されています。
  1. 変数 prev の連続回数だけの繰返しを表す圧縮表現を配列 out に追加する
  2. (2)で取り出した文字を変数 prev にコピーする
  3. 連続回数を1に戻す
7行目の「k ← outputRun(…)」が①に対応し、9行目の「runLength ← 1」が③に対応するため、[エ]には②の「(2)で取り出した文字を変数 prev にコピーする」処理が入ることがわかります。前述のとおり"取り出した文字"は in[i] なので、prev に in[i] を代入する処理が適切です。

したがって、[エ]には「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ペア)
    〔圧縮方法その1〕では、連続回数にかかわらず各ペアを[圧縮対象文字][連続回数]の2文字で表します。よって、圧縮前のデータの大きさが100文字のとき、圧縮後のデータの大きさは「40ペア×2文字=80文字」となります。圧縮比は「圧縮後のデータの大きさ÷圧縮前のデータの大きさ」で求めますから、

     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倍にしてしまう場合です。

    ∴同じ文字が連続することが無い場合
模範解答

Pagetop