文字列の圧縮

平成25年度秋期基本情報技術者試験に出題された文字列の圧縮を行うアルゴリズムを MATLAB で作成してみた。

MATLAB コード

文字列の圧縮を行う MATLAB コードを示す。

英字 A ～ Z から構成される文字列を圧縮する副プログラム Compress，及び圧縮された文字列を復元する副プログラム Decompress である。

副プログラム Compress では，配列 Plaindata に格納されている圧縮前の文字列を受け取り，圧縮後の文字列を配列 Compressedata に格納する。

Compress の引数の仕様は，次のとおりである。

引数名	データ型	入力／出力	意味
Plaindata[]	文字型	入力	圧縮前の文字列が格納されている 1 次元配列 ABCDEFABCDABCDEF
Plength	整数型	入力	圧縮前の文字列の長さ（1 以上）
Compresseddata[]	文字型	出力	圧縮後の文字列が格納される 1 次元配列
Clength	整数型	出力	圧縮後の文字列の長さ

ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
% 圧縮前の文字列が格納されている１次元の配列
Plaindata = "ABCDEFABCDABCDEF";
% 圧縮前の文字列の長さ
Plength = length(Plaindata);
% 制御記号の設定
Esym = "$";

Pindex = 1;
Cindex = 1;

% 初期の圧縮データ設定
Compresseddata = repmat(' ', 1, Plength + 10); % 余分に長めに確保

% 最初の4文字をそのままコピー
while Pindex < Plength + 1 && Pindex < 5
    Compresseddata(Cindex) = Plaindata(Pindex);
    Cindex = Cindex + 1;
    Pindex = Pindex + 1;
end

% 圧縮ループ
while Pindex < Plength + 1
    Maxfitnum = -1;
    Maxdistance = -1;
    Distance = 4;
    while Distance <= 26 && (Pindex - Distance) >= 1
        Fitnum = 0;
        % 同じ文字並びの文字数を調べる
        while Fitnum < Distance && (Pindex + Fitnum) <= Plength
            % 文字が一致するかどうかを調べる
            if Plaindata(Pindex + Fitnum) ~= Plaindata(Pindex - Distance + Fitnum)
                break;
            end
            Fitnum = Fitnum + 1;
        end
        % 文字列が4以上、かつ、最も多いかどうかを調べる
        if Fitnum >= 4 && Maxfitnum < Fitnum
            Maxfitnum = Fitnum;
            Maxdistance = Distance;
        end
        Distance = Distance + 1;
    end
    
    if Maxfitnum == -1
        Compresseddata(Cindex) = Plaindata(Pindex);
        Cindex = Cindex + 1;
        Pindex = Pindex + 1;
    else
        Compresseddata(Cindex) = Esym;
        Compresseddata(Cindex + 1) = ABC(Maxdistance);
        Compresseddata(Cindex + 2) = ABC(Maxfitnum);
        Cindex = Cindex + 3;
        Pindex = Pindex + Maxfitnum;
    end
end

Compresseddata = Compresseddata(1:Cindex - 1);
Clength = length(Compresseddata);

% 結果を表示
disp(Compresseddata);
disp(Clength);

上記のコードを実行した結果は以下のとおり。