שלום לכולם,

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

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

בנוסף יש לי בעייה אחרת שאני הכנתי קובץ 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

}

מאוד אודה לכם על קוד עזרה שהיא.

כמה עצות בלי להסתכל על הקוד:

1) תעבוד עם קבצים בינאריים, ותשתמש ב-fread ו-fwrite.

2) קח בחשבון שבהחלט יש קבצים שאחרי קידוד huffman יהיו גדולים יותר. לדוגמא קובץ אקראי.

3) בד"כ מבצעים דחיסה כגון lempel ziv ואחריו huffman, ולא רק huffman.