応用情報技術者 2012年 春期 午後 問02

解答の論理構成

• まず圧縮アルゴリズムは、問題文の〔圧縮方法その1〕で示された
  「同じデータが連続して現れる箇所を、そのデータと連続回数との組に変換する方法」です。具体的な手順は次の引用どおりです。
  ・「(1) 配列 in の初めの1文字を変数 prev に取り出す。連続回数を1とする。」
  ・「(2) 配列 in から次の1文字を取り出し、変数 prev と比較する。」
  ・「(3) …等しくない場合、変数 prev と連続回数を配列 out に追加し、…連続回数を1に戻す。」
  ・「(5) 変数 prev と連続回数を配列 out に追加する。」
• 文字列“xyyyzzzzxxyzzzzz”に上記手順を適用し、左から順に調べます。

• 末尾まで走査したので手順(5)に従い最後の z5 を追加します。
• 以上より、圧縮結果は「x1y3z4x2y1z5」です。

誤りやすいポイント

• 「連続回数が1でも必ず数字を付ける」規則を忘れ、x や y を単体で出力してしまう。
• 途中で連続回数をリセットし忘れ、x2y1 のような境目で桁を混同する。
• 末尾処理（手順(5)）を抜かし、最後の z5 を output しない。

FAQ

解答の論理構成

1. 圧縮ルールの確認
   【問題文】では、〔圧縮方法その2〕を
   「同じ文字が 4回以上 連続する場合に 圧縮対象文字、圧縮表現文字“*”、連続回数 を用い、3回以下の場合はそのまま とする」と定義しています。
   したがって
   • runLength ≥ 4 → 文字 * runLength 形式
   • runLength ≤ 3 → そのまま出力
2. 入力文字列の連続数 (run) を抽出
   文字列 “xyyyzzzzxxyzzzzz” を左から確認します。

   文字	runLength	出力形態	出力内容
   x	1	そのまま	x
   y	3	そのまま	yyy
   z	4	圧縮	z*4
   x	2	そのまま	xx
   y	1	そのまま	y
   z	5	圧縮	z*5

3. 圧縮後文字列の連結
   表の出力内容を順に連結すると
   “x” + “yyy” + “z*4” + “xx” + “y” + “z*5” = “xyyyz*4xxyz*5”
4. 以上より、模範解答「xyyyz*4xxyz*5」と一致します。

誤りやすいポイント

• 連続回数 3 と 4 の境界を取り違える
  3 回連続は非圧縮、4 回連続は圧縮です。
• “*”の位置
  圧縮時は 圧縮対象文字の直後に“*”を置きます。
  （例：zzzz → z*4、×*4z は誤り）
• 圧縮後の並び順
  生文字と圧縮表現を 出現順にそのまま 連結します。
  グループごとに並べ替えてはいけません。

FAQ

解答の論理構成

1. 手続き(2)には「配列 in から次の1文字を取り出し、変数 prev と比較する。」とあります。比較の結果が“等しい”かどうかで処理が分岐するので、図1の判定条件アは
   in[i] と prev が等しい
   となります。
2. 手続き(3)では「変数 prev と連続回数を配列 out に追加し」とあるので、文字1バイトと回数1バイトの合計2要素を書き込みます。次に追加する位置 k は現在位置に 2 を加えた値になります。したがってイは
   k+2
   となります。
3. 以上より、ア＝「in[i]とprevが等しい」、イ＝「k+2」と確定します。

誤りやすいポイント

• アを「in[i] ≠ prev」と誤って否定形で書くミス。アルゴリズム説明(2)は“比較”ですが、runLength を増やすのは一致時です。
• runLength を out に書き込む際のデータ数を勘違いし、イを「k+1」や「k+runLength」としてしまうミス。文字と回数は常に2バイト固定です。
• k の更新位置をループの最後でまとめて行うと考え、コードの流れを取り違えるケース。

FAQ

解答の論理構成

1. 圧縮方法その2の処理手順(3)には
   “比較した二つの文字が等しくない場合、変数 prev の連続回数だけの繰返しを表す圧縮表現を配列 out に追加し、(2)で取り出した文字を変数 prev にコピーして、連続回数を1に戻す”
   とあります。「等しくない場合」に処理を行うので、for ループの判定 ウ は
   “in[i]とprevが等しくない”
   となります。
2. 同じ手順(3)の後半に “(2)で取り出した文字を変数 prev にコピー” とあるため、エ には
   “prev ← in[i]”
   が入ります。
3. 関数 outputRun の仕様は “prev が runLength 回繰り返すことを表す圧縮表現を配列 out の添字 k の位置に追加し、次の追加位置を返す” です。
   圧縮方式の説明では “同じ文字が4回以上連続する場合に圧縮対象文字、圧縮表現文字、連続回数を用い、3回以下の場合はそのままとする” と明記されています。したがって オ は
   “runLengthが3以下”
   のとき元のまま出力し、それ以外（4以上）のときに “圧縮対象文字, ‘*’, 連続回数” の3バイトで出力すれば仕様と一致します。

誤りやすいポイント

• “圧縮対象文字, ‘*’, 連続回数” という3バイト形式は “4回以上” のみで採用されることを見落とし、オ を “runLengthが4以上” と逆にしてしまう。
• encode1 の “[ア]” と同じ感覚で encode2 も “等しい場合” に if ブロックへ入ると誤解し、ウ を “in[i]とprevが等しい” と書いてしまう。
• runLength をリセットする位置を誤り、エ を for ループの先頭や末尾に書いてしまう。

FAQ

解答の論理構成

1. 圧縮比の定義を確認
   【問題文】に「圧縮後のデータの大きさを圧縮前のデータの大きさで割った値を圧縮比と定義」とある。したがって、各ラン長 n について
   圧縮比 = 圧縮後サイズ ÷ 圧縮前サイズ
   と置き、表1の出現率を重みとして期待値を取れば全体の圧縮比が得られる。
2. 〔圧縮方法その1〕の圧縮後サイズ
   同じ文字が n 個続くデータをこの方式で表すと、
   ・圧縮対象文字：1 バイト
   ・連続回数　　 ：1 バイト
   の合計 2 バイトになる。
   圧縮前サイズは n バイトなので、
   圧縮比( n ) = 2 / n
3. 表1の重み付け平均
   表1には「n=1:0.1, n=2:0.2, n=3:0.3, n=4:0.4」とある。
   よって
   0.1×2/1 + 0.2×2/2 + 0.3×2/3 + 0.4×2/4
   = 0.2 + 0.2 + 0.2 + 0.2 = 0.8
   したがって カ = 0.8。
4. 〔圧縮方法その2〕の圧縮後サイズ
   【問題文】に「同じ文字が4回以上連続する場合に…圧縮対象文字、圧縮表現文字、連続回数を用い、3回以下の場合はそのまま」とある。
   ・n = 1, 2, 3 のとき：圧縮後サイズ = n
   ・n ≥ 4 のとき（今回 n = 4 のみ）：圧縮後サイズ = 3 バイト
   よって
   圧縮比(1) = 1/1 = 1
   圧縮比(2) = 2/2 = 1
   圧縮比(3) = 3/3 = 1
   圧縮比(4) = 3/4 = 0.75
5. 再び重み付け平均
   0.1×1 + 0.2×1 + 0.3×1 + 0.4×0.75
   = 0.1 + 0.2 + 0.3 + 0.3 = 0.9
   したがって キ = 0.9。
6. 〔圧縮方法その1〕の最悪の場合
   圧縮後サイズは常に 2 バイト、圧縮前サイズは n バイトなので
   圧縮比 = 2 / n
   が最大になるのは n = 1（すべてがバラバラの文字列）であり、
   最大圧縮比 = 2 / 1 = 2
   したがって ク = 2。

誤りやすいポイント

• 出現率を「個数」ではなく「確率」として扱う計算を忘れ、単純に足し算してしまう。
• 〔圧縮方法その2〕で n = 4 を 4 バイトと勘違いし、「文字＋'*'＋回数」を 4 バイトと誤認する。
• 最悪ケース解析で n = 0 や n = 255 など現実に現れない値を当てはめてしまう。

FAQ

解答の論理構成

1. 問題文では、〔圧縮方法その1〕が「[圧縮対象文字][連続回数]」という2バイト固定フォーマットであると説明しています。
   引用：
   「圧縮の表現形式として、[圧縮対象文字][連続回数]を用いる方法」
2. 1 文字しか連続しない場合でも必ず 2 バイトを出力します。
   つまり、元データ 1 バイト → 圧縮後 2 バイトとなり、データ量が倍増します。
3. 問題文の下線付き記述
   「〔圧縮方法その1〕の場合、圧縮対象のデータによっては、圧縮後のデータが圧縮前より大きくなってしまうことがある。①最悪の場合」
   では、最もデータが増えるケースを尋ねています。
4. 圧縮効果が最も悪いのは「同じ文字が一切続かない」＝“全て 1 個ずつ”のケースです。
   このとき配列 in の各要素はすべて別文字として扱われ、2 バイト×文字数となり圧縮比は最大になります。
5. 以上より、下線①が示すケースは
   「同じ文字が連続することがない場合」
   が妥当です。

誤りやすいポイント

• 「出現率0.1」の行だけに着目し、1 個連続するケースと誤って限定する。実際には 100％が 1 個連続になる極端例が最悪。
• 〔圧縮方法その2〕と混同し、“4 個未満で展開される”条件を引用してしまう。
• 「最悪＝圧縮率が最低（最も小さい）」と勘違いし、逆に完全一致の長いランを答えてしまう。

FAQ