Хаффман

Тема в разделе "C/C++/C#", создана пользователем Terra, 29 ноя 2009.

  1. Terra

    Terra Гость

    Всем привет))
    Имеется реализованное сжатие по Хаффману. Первый раз сжатие файла происходит как надо, что можно наблюдать в файле "7777.txt", где лежат: название входного файла, символы, коды, длина кодов, и в выходном файле, коэффициент сжатия правдоподобный, а вот если сжать второй раз тот же файл, то... :) Причем, какого бы размера не был бы входной файл при повторном сжатии, всегда на выходе 1 Kb. Алфавит и код из 1 и 0 - "teemp.txt". Результат - в файле, который сами выберете))
    Код (C++):
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define N 100000
    #define M 8
    #pragma pack(push)
    #pragma pack(1)
    struct sym
    {
    int n;
    char ch;
    float freq;  
    char code[255];
    sym *left;
    sym *right;
    };
    #pragma pack(pop)
    void through_tree(sym *root);
    sym *makeTree(sym *psym[],int k);
    void makeCodes(sym *root);
    FILE *fp,*fp2,*fp3;
    struct read
    {
    char ch;
    char code[255];
    int len1;

    }sim[256];
    void main(void)
    {

    char mode=0;
    char c=0;
    int chh;
    int k=0;
    int kk=0;
    int fsize2=0;
    int ts;
    int kolvo[256]={0};
    sym simbols[256]={0};
    sym *psym[256];
    float summir=0;
    int mes[8];
    int j=0;
    sym *symbols=(sym*)malloc(k*sizeof(sym));
    sym **psum=(sym**)malloc(k*sizeof(sym*));
    printf("a-code\n");
    printf("d-recode\n");
    printf("Input mode\t");
    scanf("%c",&mode);
    if (mode=='a')
    {
    printf("Input name of input file\t");
    char name_in[N];
    scanf("%s",name_in);
    printf("Input name of output file\t");
    char name_out[N];
    scanf("%s",name_out);
    fp=fopen(name_in,"rt");

    if(fp==NULL)
    {
    puts("FILE NOT OPEN!!!!!!!");
    }
    else
    {
    fp2=fopen("teemp.txt","wt");
    fp3=fopen("7777.txt","wt");
    while((chh=fgetc(fp))!=EOF)
    {            
    for(int j=0; j<256; j++)
    {
    if (chh==simbols[j].ch)
    {
    kolvo[j]++;
    kk++;                        
    break;
    }
    if (simbols[j].ch==0)
    {
    simbols[j].ch=(char)chh;
    kolvo[j]=1;
    k++;
    kk++;
    break;
    }                    
    }            
    }
    for(int i=0;i<k;i++)
    simbols[i].freq=(float)kolvo[i]/kk;
    for(int i=0;i<k;i++)
    psym[i]=&simbols[i];
    sym tempp;
    for(int i=1;i<k;i++)
    for(int j=0;j<k-1;j++)
    if(simbols[j].freq<simbols[j+1].freq)
    {
    tempp=simbols[j];
    simbols[j]=simbols[j+1];
    simbols[j+1]=tempp;
    }
    for(int i=0;i<k;i++)
    {
    summir+=simbols[i].freq;       
    }
    sym *root=makeTree(psym,k);
    makeCodes(root);
    rewind(fp);
    for(int i=0;i<k;i++)
    {
    sim[i].len1=strlen(simbols[i].code);
    }
    while((chh=fgetc(fp))!=EOF)
    {
    for(int i=0;i<k;i++)
    if(chh==simbols[i].ch)
    {      
    fwrite(simbols[i].code,sim[i].len1,1,fp2);
    }
    }
    for (int i=0;i<k;i++)
    fputc(simbols[i].ch,fp2);
    //through_tree(root);
    fclose(fp2);
    fp2=fopen("teemp.txt","rt");
    if(fp2==NULL)
    {
    puts("FILE NOT OPEN!!!!!!!");
    }
    else
    {
    unsigned long long int counter1=0;
    int chhh=0;
    while((chhh=fgetc(fp2))!=EOF)
    {
    counter1++;
    }
    rewind(fp2);
    FILE *fp4=fopen(name_out,"wt");
    char simbol=0;
    for (unsigned long long int i=0;i<counter1;)
    {
    char byte=0;
    for(int bit = 0;bit<8 && i<counter1;++bit,++i)
    {
    simbol=fgetc(fp2);
    byte <<= 1;
    byte |= simbol- '0';
    }
    fputc(byte,fp4);
    }
    fclose(fp2);
    int i=0;   
    rewind(fp3);
    fprintf(fp3,"%s\n",name_in);
    fprintf(fp3,"%d\n",k);
    for(i=0;i<k;i++)
    {
    fprintf(fp3,"%c\n",simbols[i].ch);
    fprintf(fp3,"%s\n",simbols[i].code);
    sim[i].len1=strlen(simbols[i].code);
    fprintf(fp3,"%d\n",sim[i].len1);
    }
    }
    }
    //remove("7777.txt");

    }
    else
    {
    if (mode=='d')
    {
    printf("Input input file\t");
    char name_inn[256];
    scanf("%s",name_inn);
    printf("Input output file\t");
    char name_out[256];
    scanf("%s",name_out);
    FILE *fp_res=fopen(name_inn,"rt");
    if (fp_res==NULL)
    puts("FILE NOT OPEN!!!!!!!");
    else
    {
    fp3=fopen("7777.txt","rt");
    if(fp3==NULL)
    {
    puts("FILE NOT OPEN!!!!!!!");
    }
    else
    {
    char name_in[256];
    fscanf(fp3,"%s",name_in);
    FILE *res;
    res=fopen(name_out,"wb");
    int chh=0;
    unsigned long long int counter1=0;
    FILE *fp=fopen(name_in,"rb");
    while((chh=fgetc(fp))!=EOF)
    {
    counter1++;
    }
    rewind(fp);
    for (unsigned long long int i=0;i<counter1;i++)
    {
    chh=fgetc(fp);
    putc(chh,res);
    }
    /*FILE *fp5=fopen("recode.txt","wb");
    rewind(fp_res);
    for (unsigned long long int i=0;i<counter1;)
    {
    char byte=0;
    for(int bit = 0;bit<8 && i<counter1;++bit,++i)
    {
    char simbol=fgetc(fp_res);
    byte >>= 1;
    byte &= simbol- '0';
    }
    fputc(byte,fp5);
    }*/

    fcloseall();
    }
    }
    }
    else
    printf("You have pressed the wrong key\n");
    }
    }
    sym *makeTree(sym *psym[],int k)
    {
    sym *temp;
    temp=(sym*)malloc(sizeof(sym));
    temp->freq=psym[k-1]->freq+psym[k-2]->freq;
    temp->code[0]=0;
    temp->left=psym[k-1];
    temp->right=psym[k-2];
    if(k==2)
    return temp;
    else
    {
    for(int i=0;i<k;i++)
    if (temp->freq>psym[i]->freq)
    {    
    for(int j=k-1;j>i;j--)
    psym[j]=psym[j-1];                                                                   
    psym[i]=temp;
    break;
    }            
    }
    return makeTree(psym,k-1);
    }
    void through_tree(sym *root)
    {
    struct stek
    {
    sym *d;
    stek *s;
    } *st,*st1=NULL;
    sym *dr1;
    dr1=root;
    int pr=1;
    int i=0;
    for(i=0;i<2;i++)
    {
    st=(stek*)calloc(1,sizeof(stek));
    st->d=dr1;
    st->s=st1;
    st1=st;
    }
    FILE *fp5=fopen("tree.txt","wt");
    fprintf(fp5,"%c\n",fp5,dr1->code,dr1->n);
    while(st)
    {
    do
    {
    if(pr && dr1->left) dr1=dr1->left;
    else
    if(dr1->right) dr1=dr1->right;
    pr=1;
    if(dr1->left && dr1->right)
    {
    st=(stek*)malloc(sizeof(stek));
    st->d=dr1;
    st->s=st1;
    st1=st;
    }

    }
    while(dr1->left || dr1->right);
    fprintf(fp5,"%c\n",fp5,dr1->code,dr1->n);
    dr1=st->d;
    st1=st->s;
    free(st);
    st=st1;
    if(dr1->right) pr=0;
    }
    }
    void makeCodes(sym *root)
    {
    if(root->left)
    {
    strcpy(root->left->code,root->code);
    strcat(root->left->code,"0");
    makeCodes(root->left);
    }
    if(root->right)
    {
    strcpy(root->right->code,root->code);
    strcat(root->right->code,"1");
    makeCodes(root->right);
    }
    }
     

Поделиться этой страницей