1. Мегаконкурс в апреле "Приведи друзей на codeby". Дарим деньги, подписку на журнал хакер и выдаем статус "Paid Access". Подробнее ...

    Скрыть объявление

Хаффман

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

Наш партнер Genesis Hackspace
  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);
    }
    }
     

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