データを圧縮するアルゴリズムの一つにランレングス法がある。ランレングス法とは,同じデータが連続して現れる箇所を,そのデータと連続している回数との組に変換する方法である。文字"a"~"z"だけから成る文字列を圧縮する方法として,圧縮の表現形式の違う二つのプログラムを比較検討する。 圧縮前と圧縮後のデータを管理する方法として配列を用いる。配列の各要素には,文字データの場合は8ビット表現の文字コードが,数値データの場合は0~255の整数が格納される。圧縮前の配列をin,圧縮後の配列をoutとする。配列inの大きさは文字列の長さと等しく,2以上,255以下である。配列outには圧縮後のデータを格納する十分な領域が確保されている。配列の添字は0から始まる。 [圧縮方法その1] 圧縮の表現形式として,[圧縮対象文字][連続回数]を用いる方法の処理手順を次の(1)~(5)に,そのプログラムを図1に示す。例えば,文字列"abbcccdddeeeeee"を圧縮すると,a1b2c3d4e5となる。ここで,a~zは文字データを表し,数字は対応する数値データを表す。
(1) [圧縮方法その1]によって圧縮した結果を答えよ。
(2) [圧縮方法その2]によって圧縮した結果を答えよ。
図1中の空欄に入れる適切な字句を答えよ。
図2中の空欄に入れる適切な字句を答えよ。
(1) 二つの圧縮方法における データ圧縮の効果について考える。 いま,同じ文字がn個続く確率(出現率)を表1のとおり仮定する。例えば,配列inの大きさが100の場合,1割の10文字が連続しない一つの文字として存在する。また,4割の40文字が4個連続する文字の割合である。このとき,4個連続している文字列は10組となる。 圧縮後のデータの大きさを圧縮前のデータの大きさで割った値を圧縮比と定義すると,この表1の場合,[圧縮方法その1]での圧縮比は,[圧縮方法その2]での圧縮比はと算出できる。
[圧縮方法その1]の場合,圧縮対象のデータによっては,圧縮後のデータが圧縮前より大きくなってしまうことがある。最悪の場合には,圧縮比はとなってしまう。
(2) 本文中の下線①とは,どのような場合か。20字以内で答えよ。