现在的位置: 首页 > 综合 > 正文

赫夫曼文件压缩器

2013年09月04日 ⁄ 综合 ⁄ 共 3837字 ⁄ 字号 评论关闭

20081102

    可压缩任意类型的文件,但压缩率远比不上RAR,测试一张BMP图片3次赫夫曼最高压缩率27%,RAR可达3%。这说明数据结构还是很有用的,但我觉得如果能运用于实践会更好。

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
typedef struct htn
{
    unsigned long weight;
    struct htn *father;
    struct htn *lchild;
    struct htn *rchild;
}HTN;
void error();
HTN *mi(HTN *head,HTN *end);
void compress(char *iname);
HTN *btree(HTN p[511]);
void scopy(char *de,char *so);
void coding(char code[256][18],HTN ht[511],HTN *p);
void outtree(FILE *out,HTN p[511]);
FILE *outbehind(char *q);
void outinfo(FILE *in,FILE *out,char code[256][18]);
void main()
{
    char iname[20];
    printf("inname:");
    scanf("%s",iname);/*未处理溢出*/
    compress(iname);
    getch();/*getchar报警告?*/
}
void error()
{
    printf("\n\nError!");
    getch();
    exit(0);
}
HTN *mi(HTN *head,HTN *end)
{
    HTN *min=0;
    
    
    for(;head<=end;head++)
        if(head->weight&&!head->father&&(min==0||head->weight<min->weight))
            min=head;
    if(!min->weight||min->father){printf("!!%d",min);getch();return 0;}
    min->father=min;
    return min;
}
void compress(char *iname)
{
    FILE *in,*out;
    HTN ht[511]={0},*base;/*指针可置0?*/
    char code[256][18]={0};
    int i;
    /*堆管理会更好*//*位段?*//*不超过16位?*/
    
    if(!(in=fopen(iname,"rb")))error();
    while(!feof(in))ht[fgetc(in)].weight++;
    base=btree(ht);
    printf("btree finish");getch();
    coding(code,ht,base);
    printf("coding finish");getch();
    out=outbehind(iname);
    outtree(out,ht);
    printf("outtree finish");getch();
    fseek(in,0l,0);
    for(i=0;i<18;i++)printf("!%d",code[255][i]);
    getch(); 
    outinfo(in,out,code);
    printf("\n\nFinish!");
}
HTN *btree(HTN p[511])
{
    HTN *head=p,*end=p+510,*min1,*min2;
    int i;
    for(i=0;i<=510;i++)printf("%lu ",head[i].weight);getch();
    for(p+=256;p<=end;p++)
    {
        min1=mi(head,p-1);/*指针的指针?*/
        min2=mi(head,p-1);
        if(!min1||!min2){p=min1?min1:min2;p++;break;}/*当出现权为0时运行出错*/
        min1->father=min2->father=p;
        p->weight=min1->weight+min2->weight;/*文件最大2G*/
        p->lchild=min1;
        p->rchild=min2;
    }
    printf("p-end=%d",p-end);getch();
    for(i=0;i<=510;i++)printf("%lu ",head[i].weight);getch();
    p--;
    p->father=0;
    if(!min1&&!min2)error();
    if(p==head+255)p=min1?min1:min2;
    printf("\n%lu",p->weight);getch();
    return p;
}
void scopy(char *de,char *so)
{
    while((*de++=*so++)!=-1);
}
void coding(char code[256][18],HTN ht[511],HTN *p)
{
    HTN *head=ht,*end=ht+510;
    char temp[18],deep=1;
    for(;ht<=end;ht++)ht->weight=0;
    while(p)
    {
        if(p->weight==0)
        {
            p->weight=1;
            if(p->lchild)
            {
                p=p->lchild;
                temp[deep++]=0;
            }
            else
            {
                temp[deep]=-1;
                temp[0]=deep-1;
                scopy(code[p-head],temp);/*256次调用过多,可改进*/
            }
        }
        else if(p->weight==1)
        {
            p->weight=-1;
            if(p->rchild)
            {
                p=p->rchild;
                temp[deep++]=1;
            }
        }
        else
        {
            p=p->father;
            deep--;
        }
    }
}
void outtree(FILE *out,HTN p[511])
{
    HTN *head=p,*end=p+510;
    for(p+=256;p<=end;p++)
    {
        fputc(p->lchild?p->lchild-head:255,out);
        fputc(p->rchild?p->rchild-head:255,out);
    }
}
FILE *outbehind(char *q)
{
    char oname[20],*p=oname;
    FILE *out;
    while((*p++=*q++)!='.');/*未处理没有后缀的情况*/
    *p++='r';
    *p++='s';
    *p=0;
    if(!(out=fopen(oname,"wb")))error();
    while(*q)fputc(*q++,out);/*可改进?*/
    fputc(0,out);
    return(out);
}
void outinfo(FILE *in,FILE *out,char code[256][18])
{
    char t[25]={0},*p,*q;/*位运算更快?*/
    unsigned char we[9]={128,64,32,16,8,4,2,1,0},m,*w;
    while(!feof(in))
    {
        if(*t>=8)/*取一个字节*/
        {
            for(p=t+1,m=0,w=we,*t-=8;*w;w++,p++)
                if(*p)m+=*w;
            fputc(m,out);
            q=t+1;
            while((*q++=*p++)!=-1);
        }
        else/*连接*/
        {
            q=t+*t+1;
            p=code[fgetc(in)];
            *t+=*p;
            p++;
            while((*q++=*p++)!=-1);
        }
    }
}

抱歉!评论已关闭.