2012年 春期 応用情報技術者試験 問2

文字列を圧縮するアルゴリズム

データを圧縮するアルゴリズムの一つにランレングス法がある。ランレングス法とは、同じデータが連続して現れる箇所を、そのデータと連続している回数との組に変換する方法である。文字"a"～"z"だけから成る文字列を圧縮する方法として、圧縮の表現形式の違う二つのプログラムを比較検討する。

圧縮前と圧縮後のデータを管理する方法として配列を用いる。配列の各要素には、文字データの場合は8ビット表現の文字コードが、数値データの場合は0～255の整数が格納される。圧縮前の配列をin、圧縮後の配列をoutとする。配列inの大きさは文字列の長さと等しく、2以上、255以下である。配列outには圧縮後のデータを格納する十分な領域が確保されている。配列の添字は0から始まる。

圧縮方法その1

圧縮の表現形式として、「圧縮対象文字][連続回数」を用いる方法の処理手順を次の(1)～(5)に、そのプログラムを図1に示す。例えば、文字列"abbcccddddeeeeee"を圧縮すると、a1b2c3d4e5となる。ここで、a～zは文字データを表し、数字は対応する数値データを表す。

(1) 配列inの初めの1文字を変数prevに取り出す。連続回数を1にする。

(2) 配列inから次の1文字を取り出し、変数prevと比較する。配列inから取り出す文字がない場合、処理手順(5)へ進む。

(3) 比較した二つの文字が等しい場合、連続回数に1を加える。等しくない場合、変数prevと連続回数を配列outに追加し、(2)で取り出した文字を変数prevにコピーして、連続回数を1に戻す。

(4) 処理手順(2)に戻る。

(5) 変数prevと連続回数を配列outに追加する。

図1中の関数encode1はプログラムのメイン処理であり、配列outに追加されたデータの大きさを返す。

function encode1( in, out )
    prev ← in[0]
    runLength ← 1
    k ← 0
    for ( i を 1 から (配列 in の大きさ－1) まで 1 ずつ増やす )
        if ( ア )
            runLength ← runLength + 1
        else
            out[k] ← prev
            out[k+1] ← runLength
            k ← イ
            prev ← in[i]
            runLength ← 1
        endif
    endfor
    out[k] ← prev
    out[k+1] ← runLength
    k ← イ
    return k
endfunction

圧縮方法その2

圧縮の表現形式として、同じ文字が4回以上連続する場合に「圧縮対象文字][圧縮表現文字][連続回数」を用い、3回以下の場合はそのままとする方法の処理手順を次の(1)～(5)に、そのプログラムを図2に示す。圧縮表現文字には、圧縮対象文字と区別するために、圧縮対象文字として使用されない文字を使う。ここでは""を圧縮表現文字とする。例えば、文字列"abbcccddddeeeeee"を圧縮すると、abbcccd4e*5となる。

(1) 配列inの初めの1文字を変数prevに取り出す。連続回数を1にする。

(2) 配列inから次の1文字を取り出し、変数prevと比較する。配列inから取り出す文字がない場合、処理手順(5)へ進む。

(3) 比較した二つの文字が等しくない場合、変数prevの連続回数だけの繰返しを表す圧縮表現を配列outに追加し、(2)で取り出した文字を変数prevにコピーして、連続回数を1に戻す。等しい場合、連続回数に1を加える。

(4) 処理手順(2)に戻る。

(5) 変数prevと連続回数だけの繰返しを表す圧縮表現を配列outに追加する。

図2中の関数encode2はプログラムのメイン処理であり、配列outに追加されたデータの大きさを返す。関数outputRunは、prevがrunLength回繰り返すことを表す圧縮表現を配列outの添字kの位置に追加し、次の追加位置を返す。

function encode2( in, out )
    prev ← in[0]
    runLength ← 1
    k ← 0
    for ( i を 1 から (配列 in の大きさ－1) まで 1 ずつ増やす )
        if ( ウ )
            k ← outputRun( prev, runLength, k, out )
            エ
            runLength ← 1
        else
            runLength ← runLength + 1
        endif
    endfor
    k ← outputRun( prev, runLength, k, out )
    return k
endfunction

function outputRun( prev, runLength, k, out )
    if ( オ )
        for ( i を 1 から runLength まで 1 ずつ増やす )
            out[k] ← prev
            k ← k + 1
        endfor
    else
        out[k] ← prev
        out[k+1] ← "*"
        out[k+2] ← runLength
        k ← k + 3
    endif
    return k
endfunction

プログラムに関する考察

二つの圧縮方法におけるデータ圧縮の効果について考える。

いま、同じ文字がn個続く確率（出現率）を表1のとおり仮定する。例えば、配列inの大きさが100の場合、1割の10文字が連続しない一つの文字として存在する。また、4割の40文字が4個連続する文字の割合である。このとき、4個連続している文字列は10組となる。

圧縮後のデータの大きさを圧縮前のデータの大きさで割った値を圧縮比と定義すると、この表1の場合、「圧縮方法その1」での圧縮比はカ、「圧縮方法その2」での圧縮比はキと算出できる。

「圧縮方法その1」の場合、圧縮対象のデータによっては、圧縮後のデータが圧縮前より大きくなってしまうことがある。最悪の場合には、圧縮比はクとなってしまう。