Хаффман

  • Автор темы Terra
  • Дата начала
T

Terra

Гость
#1
Всем привет))
Имеется реализованное сжатие по Хаффману. Первый раз сжатие файла происходит как надо, что можно наблюдать в файле "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);
}
}