学习霍夫曼编码

霍夫曼编码广泛用于数据压缩算法，其重要性不言而喻。

内容：写一个程序读ASCII文件，统计各字符的频率并制定霍夫曼编码表，最后将此文件的内容根据编码表翻译为二进制文件，计算压缩率。

代码清单：

#include...
typedef struct{
    float weight;
    int parent, lc, rc;
}node;
#define INIT_SLEN 512

int main(int ac, char **av){
    FILE *pf;
    unsigned int C[128], total, nz, slen, sz, cb;
    char *S, code[128][20];
    node T[256];

    if(ac != 3){
        printf("usage: %s <ascii-infile> <outfile>\n", av[0]); exit(1); }
    if(!(pf = fopen(av[1],"r"))){
        perror("fopen"); exit(1); }
    memset(&C,0,sizeof C);
    total=0;
    for(int c; (c = fgetc(pf)) != EOF; ) C[c]++,total++;//计算各字符出现次数
    fclose(pf);
    nz=0;
    memset(T,0,sizeof T);
    for(int i=0; i<128; i++){
        if(C[i]) ++nz;//nz统计共有几种字符
        T[i].weight=(float)C[i]/(float)total;/*计算该字符频度*/}
    for(int i=1, j=128; i<nz; i++){
        int minP=-1, minQ=-1;//T[minP]的权重最小，minQ次小
        for(int k=j-1; k>0; --k){
            if(T[k].weight==0.0f || T[k].parent>0) continue;
            if(minP<0) minP=k;
            else if(minQ<0) minQ=k;
            else if(T[k].weight<T[minP].weight) minQ=minP, minP=k;
            else if(T[k].weight<T[minQ].weight) minQ=k; }
        //填充新霍夫曼树节点，权重是那俩的和，左右子树是那俩节点
        T[j].weight=T[minP].weight + T[minQ].weight;
        T[j].lc=minP, T[j].rc=minQ;
        T[minP].parent=j, T[minQ].parent=j;
        ++j; }
    for(int i=0; i<128; i++){
        if(C[i]==0){ code[i][0]='\0'; continue;}
        char tmp[32];//临时存放C[i]的编码
        int pt=32;
        tmp[--pt]='\0';
        for(int k=i, f=T[k].parent; k; k=f, f = T[f].parent)
            tmp[--pt]= (T[f].lc==k)? '0' : '1';//左分支编码0否则1
        strcpy(&code[i][0], &tmp[pt]);/*复制到编码表code里*/}
    S=(char*)malloc(sizeof(char)*INIT_SLEN);
    if(!S){ perror("bad alloc"); exit(1); }
    slen=0, sz=INIT_SLEN;
    if(!(pf=fopen(av[1],"r"))){ perror("fopen"); exit(1); }
    for(int n, c; (c=fgetc(pf)) != EOF;){
        n=strlen(code[c]);//该字符对应编码的长度
        while(slen+n>=sz){//存不下就扩容
            char *newS=realloc(S,sizeof(char)*2*sz);
            if(!newS){ free(S); perror("bad realloc"); exit(1); }
            S=newS;
            sz *= 2; }
        strcpy(S+slen,code[c]);//根据编码表翻译成01序列（ASCII形式)
        slen+=n; }
    fclose(pf);
    pf=fopen(av[2],"wb");//打开输出文件准备写二进制数据
    if(!pf){ perror("bad out-file"); free(S); exit(1); }
    cb=0;
    for(int i=0; i<slen; i+=8){
        int t = (i+8<=slen) ? 8: slen-i;//取长为t的零一序列
        unsigned char b=0;//根据序列计算二进制码到b
        while(t>0){if(S[i]=='1') b |= 1<<(t-1);
            --t; }
        fputc(b,pf);/*写b并计数*/ ++cb; }
    free(S);
    fclose(pf);
    printf("old=%dB, new=%dB(%f%%)\n",total,cb,cb*100.0/total);
}

到网上找一个文本文件，运行一下：新文件大小约是原文件的70%，只用这一招果然不太行。