קוד הופמן

פורסם 2008 באוגוסט 1216 שנים

שלום לכולם,

כתבתי קוד המבצע את אלגוריתם הופמן ואני משום מה מקבל שהקובץ המקודד יותר גדול מהקובץ המקורי,

נראה לי שיש לי איזה בעייה בשמירת הקובץ, אני מנסה לשמור אותו כקובץ בינארי אבל גם כבינארי הוא יוצא גדול יותר מהמקור.

בנוסף יש לי בעייה אחרת שאני הכנתי קובץ Lookup table עם כל ערכי הASCII והערכים שלהם ע"פ העץ הבינארי שנבנה ע"פ האלגוריתם של הקוד.

אין לי כלכך רעיון\דרך איך לפענח קובץ המקודד כבר וכשיש לי את הLookup Table של אותו הקובץ.

אני כותב את כל הקוד בשפת C.

להלן הפונקציות העיקריות בקוד:

int encode(FILE* srcmsg,FILE* codemsg,FILE* dic)
{
int check=0;
tree *LEAF=NULL,*Thead=NULL;
LEAF=ConstructFrequency(srcmsg); // construct the frequency list
Thead=Constructtree(LEAF); // construct the treeaccording to the list
check=writeallcodes(Thead,dic); // make a list of all the codes
check=writeencodedmsg(Thead,codemsg,srcmsg); // write the encoding to the file
return 1;
}
tree * ConstructFrequency(FILE * srcmsg)
{
int count=0;
char ASCII, ch, str[2];
tree *plhead=NULL,*what;
for(ASCII=0;ASCII<127;ASCII++) //go over all the chars
{ // this function bildes the frequency list
// according to the frequency of the char
while((ch=fgetc(srcmsg))!=EOF) //do this loop for each letter in the file
{
if(ch==ASCII) // if the letter is what we look for add one to the count
count++;
}
rewind(srcmsg); //return to the start of the file
str[0]=ASCII;
str[1]=0;
if (count>0)
{
what=make_leaf(count,str); //call the function that makes the leafs of the list
plhead=first_insert(plhead,what); // insert the leaf to the list
count=0; // start new count
}
}
return plhead; //return the start of the list
}
tree *make_leaf(int count,char *letter)
{
tree *temp=NULL; //making the leaf of the frequency list
temp=(tree *)malloc(sizeof(tree));
temp->letter=(char *)malloc(sizeof(char)*128);
strcpy(temp->letter,letter); //insert values
temp->value=count;
temp->next=NULL;
temp->right=NULL;
temp->left=NULL;
return temp; //return the leaf addres
}
tree * first_insert(tree *head,tree *what)
{
if (!head||head->value>what->value) // insert function for the tree
{
what->next=head;
return what;
}
head->next=first_insert(head->next,what);
return head;
}
tree * Constructtree(tree *LLhead)
{
tree *root; //construction of the tree
char str[128];
if (!LLhead->next)
return LLhead;
while( LLhead->next->next && LLhead->next ) // while loop
{
sprintf(str,"%s%s", LLhead->letter, LLhead->next->letter);
root=make_leaf( LLhead->next->value + LLhead->value, str );
root->left = LLhead; //insrtion of values
root->right = LLhead->next;
LLhead = LLhead->next->next;
LLhead = first_insert(LLhead,root);
}
sprintf( str, "%s%s", LLhead->letter, LLhead->next->letter );
root = make_leaf( LLhead->next->value + LLhead->value, str );
root->left = LLhead;
root->right = LLhead->next;
return root;
}
int writeallcodes(tree *Thead,FILE *dic)
{
char acode,*stbin;
stbin=(char *)malloc(sizeof(char)*128);
*stbin=0;
for(acode=0;acode<127;acode++) //writing the dictionery
{
find(Thead,acode,stbin);
if (*stbin!=0)
{
fprintf(dic,"%c",acode);
fputs(stbin,dic);
*stbin=0;
}
}
return 1;
}
int writeencodedmsg(tree *Thead,FILE *codemsg,FILE *srcmsg)
{
char acode,stbin[128];
while((acode=fgetc(srcmsg))!=EOF)
{
find(Thead,acode,stbin); //writing the encoded file
fputs(stbin,codemsg);
}
return 1;
}
void find(tree *root,char letter,char *str)
{
if(!root)
{
*str=0;
return;
}
if (root->left&&find_letter(root->left->letter,letter))
{
*str='0';
str++;
find(root->left,letter,str);
return;
}
if (root->right&&find_letter(root->right->letter,letter))
{
*str='1';
str++;
find(root->right,letter,str);
return;
}
*str=0;
return;
}
int find_letter(char *str,char letter)
{
int i;
for(i=0;str;i++) // this dunction finds a letter
if(str==letter)
return 1; //if found return one
return 0; // if not found return 0
}