文字列の圧縮と復元

文字列の圧縮と復元（基本情報 平成25年秋期午後問8）

　面白そうなので、平成25年秋期午後問8のリストを打ち込んでみました。
　前26字以内に、4文字以上の同じ文字列がある場合に、’$’+[位置情報](アルファベット)+[一致文字数](アルファベット)の3文字と置換する圧縮を行います。

ソースコード

#include <stdio.h> 
#include <string.h>

void compress(char Plaindata[80], int Plength, char Compresseddata[80], int* Clength);
void Decompress(char Compresseddata[80], int Clength, char plaindata[80], int* Plength);
char IntToAlphabet(int num);
char AlphabetToInt(char a);
void hyouji(const char format[], int Cindex, const char hyouji[], char Compresseddata[80]);

int main() {
  char Plaindata[80] = "ABCDEFABCDABCDEF";
  char Compresseddata[80];
  int Plength;
  int Clength;
  Plength = strlen(Plaindata);
  Clength = -1;
  hyouji("Plength = %d  %s =「%s」\n", Plength, "変換前データ", Plaindata);
  compress(Plaindata, Plength, Compresseddata, &Clength);
  Clength = strlen(Compresseddata);
  hyouji("Clength = %d  %s =「%s」\n", Clength, "変換先データ", Compresseddata);

  /* 復元作業開始 */
  printf("\n\n");
  hyouji("Clength = %d  %s =「%s」\n", Clength, "復元前データ", Compresseddata);
  Decompress(Compresseddata, Clength, Plaindata, &Plength);
  hyouji("Plength = %d  %s =「%s」\n", strlen(Plaindata), "復元後データ", Plaindata);
}

void compress(char Plaindata[80], int Plength, char Compresseddata[80], int* Clength) {
  int Pindex, Cindex;
  int Maxfitnum, Maxdistance, Distance, Fitnum;
  char Esym = '$'; /* 制御文字記号の設定 */
  Pindex = 0;      /* 圧縮前のの文字列の文字位置を初期化 */
  Cindex = 0;        /* 圧縮後の文字列の文字位置を初期化 */
  while ((Pindex < Plength) && (Pindex < 4)) {
    Compresseddata[Cindex] = Plaindata[Pindex];
    Cindex += 1;
    Pindex += 1;
  }
  /* ディバッグ用*/
  hyouji("Cindex  = %2d  %s   Compresseddata[] =「%s」\n", Cindex, "４文字転記", Compresseddata);
  
  while (Pindex < Plength) {
    Maxfitnum = -1;
    Maxdistance = -1;
    Distance = 4;
    while ((Distance <= 26) && (Pindex - Distance >= 0)) {
      Fitnum = 0; /* 同じ文字並びの文字数を調べる */
      while ((Fitnum < Distance) && ((Pindex + Fitnum) < Plength)) {
        /* 文字列が一致するかどうかを調べる */
        if (Plaindata[Pindex + Fitnum] != Plaindata[Pindex - Distance + Fitnum]) {
          break; /* 最も内側の繰り返し処理を終了する */
        }
        Fitnum += 1;
      }
      /* 文字数が4以上、かつ、最も多いかどうか調べる */
      if ((Fitnum >= 4) && (Maxfitnum < Fitnum)) {
        Maxfitnum = Fitnum;
        Maxdistance = Distance;
      }
      Distance += 1;
    }
    if (Maxfitnum == -1) {
      Compresseddata[Cindex] = Plaindata[Pindex];
      Cindex += 1;
      Pindex += 1;
      /* ディバッグ用 */
      hyouji("Cindex  = %2d  %s     Compresseddata[] =「%s」\n", Cindex, "置換無し", Compresseddata);
    }
    else {
      Compresseddata[Cindex] = Esym;
      Compresseddata[Cindex + 1] = IntToAlphabet(Maxdistance);
      Compresseddata[Cindex + 2] = IntToAlphabet(Maxfitnum);
      Cindex += 3;
      Pindex += Maxfitnum;
      /* ディバッグ用 */
      hyouji("Cindex  = %2d  %s     Compresseddata[] =「%s」\n", Cindex, "置換あり", Compresseddata);
    }
    *Clength = Cindex;
  }
  Compresseddata[Cindex] = '\0';
}

void Decompress(char Compresseddata[80], int Clength, char plaindata[80], int* Plength) {
  int Pindex, Cindex;
  int Num, Fitcnt, Start;
  char Esym = '$'; /* 制御文字記号の設定 */

  if (Clength >= 1) {
    Pindex = 0;      /* 圧縮前のの文字列の文字位置を初期化 */
    Cindex = 0;        /* 圧縮後の文字列の文字位置を初期化 */
    while (Cindex < Clength) {
      if (Compresseddata[Cindex] != Esym) {
        plaindata[Pindex] = Compresseddata[Cindex];
        Pindex += 1;
        Cindex += 1;
      }
      else {
        Num = AlphabetToInt(Compresseddata[Cindex + 2]);
        Start = AlphabetToInt(Compresseddata[Cindex + 1]);
        for (Fitcnt = 0; Fitcnt < Num; Fitcnt++) {
          plaindata[Pindex + Fitcnt] = plaindata[Pindex - Start + Fitcnt];
        }
        Pindex += Num;
        Cindex += 3;
      }
    }
    Compresseddata[Cindex] = '\0';
    *Plength = Pindex;
  }
}

char IntToAlphabet(int num) {
  char a;
  a = 'A' + num - 1;
  return a;
}

char AlphabetToInt(char a) {
  int num;
  num = a - 'A' + 1;
  return num;
}

void hyouji(const char format[], int Cindex, const char hyouji[], char Compresseddata[80]) {
  Compresseddata[Cindex] = '\0';
  printf(format, Cindex, hyouji, Compresseddata);
}

問題文の例の実行結果

Plength = 16  変換前データ =「ABCDEFABCDABCDEF」
Cindex  =  4  ４文字転記   Compresseddata[] =「ABCD」
Cindex  =  5  置換無し     Compresseddata[] =「ABCDE」
Cindex  =  6  置換無し     Compresseddata[] =「ABCDEF」
Cindex  =  9  置換あり     Compresseddata[] =「ABCDEF$FD」
Cindex  = 12  置換あり     Compresseddata[] =「ABCDEF$FD$JF」
Clength = 12  変換先データ =「ABCDEF$FD$JF」

Clength = 12  復元前データ =「ABCDEF$FD$JF」
Plength = 16  復元後データ =「ABCDEFABCDABCDEF」

設問２の実行結果

Plength = 24  変換前データ =「ABCDEFGABCDEABCDFEFGABCD」
Cindex  =  4  ４文字転記   Compresseddata[] =「ABCD」
Cindex  =  5  置換無し     Compresseddata[] =「ABCDE」
Cindex  =  6  置換無し     Compresseddata[] =「ABCDEF」
Cindex  =  7  置換無し     Compresseddata[] =「ABCDEFG」
Cindex  = 10  置換あり     Compresseddata[] =「ABCDEFG$GE」
Cindex  = 13  置換あり     Compresseddata[] =「ABCDEFG$GE$ED」
Cindex  = 14  置換無し     Compresseddata[] =「ABCDEFG$GE$EDF」
Cindex  = 17  置換あり     Compresseddata[] =「ABCDEFG$GE$EDF$MG」
Clength = 17  変換先データ =「ABCDEFG$GE$EDF$MG」

Clength = 17  復元前データ =「ABCDEFG$GE$EDF$MG」
Plength = 24  復元後データ =「ABCDEFGABCDEABCDFEFGABCD」

　圧縮の場合は、最初の4文字を機械的にコピーしました。置き換わっていない文字を元の文字列から数えるなら、上の「置換無し」の他に、最初の4文字分も加えないといけません。
　しかし、そもそも復元の問題なのですから、ここでは、元にした文字列を基準にするのではなく、圧縮した文字列を基に考える方が自然です。当たり前といえば当たり前なのですが、なかなかそこまで頭が付いていきません。
　復元は、圧縮の場合とは違って、「$」が出てくるかどうかだけでコピーの仕方が変わります。「$」が出てこない文字を足していくと8文字あります。
　さらに、重複といえば A から始まる文字列ばかりが目に付いて、最後の EFGABCD が、E から始まることを見落としてしまいます。
　もっとひどいのは、問2の問題では、圧縮する元のデータが最初の例ではないことをついうっかり見落として、一生懸命に作業をしてしまうという致命的なミスをしてしまいます。
　そんな見落としが多すぎて、アルゴリズムやCの問題は一向に得点が伸びません。

printfの書式情報を変数で渡せるとは知らなんだ

　問題とは全く関係ありませんが、printfの書式情報は、変数で渡せるんですね。もしやと思ってやってみると、上の136行目の hyouji() 関数の様に、変数でもきちんと表示されています。発見でした。
　これで、引数の位置や数も変えることができたら、使い勝手がもっと良くなるんだけどなあ。