素ハフマン圧縮プログラム。

Programming C 圧縮

なんか、ハフマン符号化が少しわかった気がするぞ。あと二分木とか。プログラムを書いてようやく。実践を伴わない知識っていうのは宙に浮いてるようで、なんか居心地が悪い。実際に使ってみると、なんだか錨で固定したような気分になれるなあ。二分木に関しては「たぶんこんな感じのデータ構造だったっけ？」と適当に使ったから、スゲー間抜けなことしてるかも。というかそんなこと言い出したら全部そうか。

まず元データを読み込み、バイトごとの出現回数を数える。この出現回数表を書庫の先頭に記述。その回数からハフマン木を作成。ハフマン木により、1バイト->ビット列の変換表を作成。元データを頭から読み込み、先の変換表により書庫に追記。
というプログラムを作成。
以下ソース。

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

#define HCODEMAX 256

typedef struct{
  unsigned char c;
  int count;
} item;
struct node{
  item data;
  struct node *lbranch, *rbranch;
};

struct node** isort_count(struct node *table[], int length){
  int i, j;
  struct node *tmp;
  for(i=1;i<length;++i){
    tmp = table[i];
    for(j=i;j>0 && table[j-1]->data.count>tmp->data.count;--j)
      table[j] = table[j-1];
    table[j] = tmp;
  }
  return table;
}
struct node* mknode(struct node *lbranch, struct node *rbranch){
  struct node *n;
  n = (struct node *)malloc(sizeof(struct node));
  n->data.count = 0;
  n->lbranch = lbranch;
  n->rbranch = rbranch;
  return n;
}
struct node* mktree(struct node *table[], int length){
  struct node *root, *n;

  if(length == 1) return table[0];
  n = mknode(table[0], table[1]);
  n->data.count = table[0]->data.count + table[1]->data.count;
  table[1] = n;
  isort_count(&table[1], length-1);
  root = mktree(&table[1], length-1);

  return root;
}
int print_table(FILE *fp, struct node *table[]){
  int i;
  for(i=0;i<256;++i){
    if(table[i]->data.count > 0){
      fwrite(&(table[i]->data.c), 1, 1, fp);
      fwrite(&(table[i]->data.count), 4, 1, fp);
    }
  }
}
int mkhtable(char *htable[], struct node *root, char *precode){
  char lcode[HCODEMAX], rcode[HCODEMAX];
  strcpy(lcode, precode);
  strcpy(rcode, precode);

  if(root->lbranch != NULL)
    mkhtable(htable, root->lbranch, strcat(lcode, "0"));
  if(root->rbranch != NULL)
    mkhtable(htable, root->rbranch, strcat(rcode, "1"));
  if(root->lbranch == NULL && root->rbranch == NULL){
    htable[root->data.c] = (char *)malloc(sizeof(char)*HCODEMAX);
    strcpy(htable[root->data.c], precode);
  }

  return 1;
}
int putbits(char *bitstream, FILE *fp){
  static int length = 0;
  static unsigned char bits = 0;
  if(bitstream != NULL){
    while(*bitstream != '\0'){
      bits = (bits << 1) | (*bitstream - '0');
      ++length;
      if(length == 8){
        fwrite(&bits, 1, 1, fp);
        length = 0;
        bits = 0;
      }
      ++bitstream;
    }
  } else {
    if(length != 0){
      bits = bits << 8 - length;
      fwrite(&bits, 1, 1, fp);
      fwrite(&length, 1, 1, fp);
    }
  }
  return 1;
}
int write_archive(FILE *arch, FILE *plain, char *htable[]){
  int c;
  while((c = fgetc(plain)) != EOF) putbits(htable[c], arch);
  putbits(NULL, arch);
  return 1;
}
int compress(char *plainname){
  char archname[256];
  int i;
  FILE *plain, *arch;
  struct node *table[256], *root;
  char *htable[256];

  strcpy(archname, plainname);
  strcat(archname, ".huf");

  if((plain = fopen(plainname, "r")) == NULL){
    perror("cannot open plain");
    return -1;
  }
  if((arch = fopen(archname, "w")) == NULL){
    perror("cannot open arch");
    return -1;
  }

  for(i=0;i<256;++i){
    table[i] = mknode(NULL, NULL);
    table[i]->data.count = 0;
    table[i]->data.c = i;
  }
  while((i=fgetc(plain)) != EOF) ++table[i]->data.count;

  print_table(arch, table);

  isort_count(table, 256);
  for(i=0;table[i]->data.count == 0;++i);
  root = mktree(&table[i], 256-i);

  for(i=0;i<256;++i) htable[i] = NULL;
  mkhtable(htable, root, "");

  fseek(plain, 0, SEEK_SET);

  i = 0;
  fwrite(&i, 2, 1, arch);
  write_archive(arch, plain, htable);

  fclose(plain);
  fclose(arch);
  return 1;
}
int main(int argc, char *argv[]){
  if(argc>1)
    if(!compress(argv[argc-1]))
      puts("cannot compress");
  return 0;
}

test