בניתי עץ לקידוד קוד הופמן, ויש לי בעיה בפענוח שלו (הפיכת קובץ בינארי תוים) מה הטעות???

#include <iostream>
#include <string.h>
#include "Heap.h"
#include "List.h"

struct tav
{
	char value;
	int incidence;
	tav* right;
	tav* left;
	char *son;
	char *kod;


	tav();
	tav(const tav &);
	bool operator<(tav &t) const; 
	bool operator>(tav &t) const; 

};

tav::tav()
{
	value = 0;
	incidence = 0;
	right = NULL;
	left = NULL;

	son = new char[2];
	son[1] = '\0';
	kod = new char[2];
	kod[1] = '\0';
}

tav::tav(const tav &t)
{
	value = t.value;
	incidence = t.incidence;
	right = t.right;
	left = t.left;

	son = new char[2];
	strcpy(son, t.son);
	son[1] = '\0';
	kod = new char[2];
	strcpy(kod, t.kod);
	kod[1] = '\0';
}

bool tav::operator<(tav &t) const
{
	if(incidence<t.incidence)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool tav::operator>(tav &t) const
{
	if(incidence>t.incidence)
	{
		return true;
	}
	else
	{
		return false;
	}
}

using namespace std;


class Huffman
{
private:
	tav* root;
	Heap<tav> heap;
	List<char*> vec[27];

	void sort(ifstream&);

	void build();
	bool check();
	int hamara(char);
	char hamara(int);
	void kidud(tav*);
	void tavla(char, char*); 

	char* kodTavla(char*);
	int checkval(char*);

public:
	Huffman(ifstream &);
	void print();
	void code(ifstream&);
	void decode(ifstream&);

};


Huffman::Huffman(ifstream &file)
{
	Heap<tav>();
	root = NULL;

	sort(file);
	build();
}

void Huffman::sort(ifstream &file)
{
	char ch;
	int moneA=0, moneB=0, moneC=0, moneD=0, moneE=0, moneF=0, moneG=0, moneH=0, moneI=0, moneJ=0, moneK=0, moneL=0, moneM=0, moneN=0, moneO=0, moneP=0, moneQ=0, moneR=0, moneS=0, moneT=0, moneU=0, moneV=0, moneW=0, moneX=0, moneY=0, moneZ=0, moneSpace=0;
	if(!file)
	{
		cout<<"\n\nerror";
		exit(0);
	}


	while(file.get(ch))
	{ 
		switch(ch)
		{
			case 'a':
			{
				moneA++;
				break;
			}
			case 'b':
			{
				moneB++;
				break;
			}		
			case 'c':
			{
				moneC++;
				break;
			}		
			case 'd':
			{
				moneD++;
				break;
			}
			case 'e':
			{
				moneE++;
				break;
			}
			case 'f':
			{
				moneF++;
				break;
			}
			case 'g':
			{
				moneG++;
				break;
			}
			case 'h':
			{
				moneH++;
				break;
			}
			case 'i':
			{
				moneI++;
				break;
			}
			case 'j':
			{
				moneJ++;
				break;
			}
			case 'k':
			{
				moneK++;
				break;
			}
			case 'l':
			{
				moneL++;
				break;
			}
			case 'm':
			{
				moneM++;
				break;
			}
			case 'n':
			{
				moneN++;
				break;
			}
			case 'o':
			{
				moneO++;
				break;
			}
			case 'p':
			{
				moneP++;
				break;
			}
			case 'q':
			{
				moneQ++;
				break;
			}
			case 'r':
			{
				moneR++;
				break;
			}
			case 's':
			{
				moneS++;
				break;
			}
			case 't':
			{
				moneT++;
				break;
			}
			case 'u':
			{
				moneU++;
				break;
			}
			case 'v':
			{
				moneV++;
				break;
			}
			case 'w':
			{
				moneW++;
				break;
			}
			case 'x':
			{
				moneX++;
				break;
			}
			case 'y':
			{
				moneY++;
				break;
			}
			case 'z':
			{
				moneZ++;
				break;
			}
		}

		if(ch==' ')
		{
			moneSpace++;
		}
	}

	tav a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,space;
	a.value = 'a';		a.incidence = moneA;
	b.value = 'b';		b.incidence = moneB;
	c.value = 'c';		c.incidence = moneC;
	d.value = 'd';		d.incidence = moneD;
	e.value = 'e';		e.incidence = moneE;
	f.value = 'f';		f.incidence = moneF;
	g.value = 'g';		g.incidence = moneG;
	h.value = 'h';		h.incidence = moneH;
	i.value = 'i';		i.incidence = moneI;
	j.value = 'j';		j.incidence = moneJ;
	k.value = 'k';		k.incidence = moneK;
	l.value = 'l';		l.incidence = moneL;
	m.value = 'm';		m.incidence = moneM;
	n.value = 'n';		n.incidence = moneN;
	o.value = 'o';		o.incidence = moneO;
	p.value = 'p';		p.incidence = moneP;
	q.value = 'q';		q.incidence = moneQ;
	r.value = 'r';		r.incidence = moneR;
	s.value = 's';		s.incidence = moneS;
	t.value = 't';		t.incidence = moneT;
	u.value = 'u';		u.incidence = moneU;
	v.value = 'v';		v.incidence = moneV;
	w.value = 'w';		w.incidence = moneW;
	x.value = 'x';		x.incidence = moneX;
	y.value = 'y';		y.incidence = moneY;
	z.value = 'z';		z.incidence = moneZ;
	space.value = ' ';	space.incidence = moneSpace;

	heap.Insert(a);			heap.Insert(b);	
	heap.Insert(c);			heap.Insert(d);	
	heap.Insert(e);			heap.Insert(f);	
	heap.Insert(g);			heap.Insert(h);
	heap.Insert(i);			heap.Insert(j);	
	heap.Insert(k);			heap.Insert(l);	
	heap.Insert(m);			heap.Insert(n);	
	heap.Insert(o);			heap.Insert(p);	
	heap.Insert(q);			heap.Insert(r);	
	heap.Insert(s);			heap.Insert(t);	
	heap.Insert(u);			heap.Insert(v);	
	heap.Insert(w);			heap.Insert(x);	
	heap.Insert(y);			heap.Insert(z);	
	heap.Insert(space);	


	cout<<space.value<<" incidence: "<<space.incidence<<endl;	
	cout<<a.value<<" incidence: "<<a.incidence<<endl;	
	cout<<b.value<<" incidence: "<<b.incidence<<endl;	
	cout<<c.value<<" incidence: "<<c.incidence<<endl;	
	cout<<d.value<<" incidence: "<<d.incidence<<endl;	
	cout<<e.value<<" incidence: "<<e.incidence<<endl;	
	cout<<f.value<<" incidence: "<<f.incidence<<endl;	
	cout<<g.value<<" incidence: "<<g.incidence<<endl;	
	cout<<h.value<<" incidence: "<<h.incidence<<endl;	
	cout<<i.value<<" incidence: "<<i.incidence<<endl;	
	cout<<j.value<<" incidence: "<<j.incidence<<endl;	
	cout<<k.value<<" incidence: "<<k.incidence<<endl;	
	cout<<l.value<<" incidence: "<<l.incidence<<endl;	
	cout<<m.value<<" incidence: "<<m.incidence<<endl;	
	cout<<n.value<<" incidence: "<<n.incidence<<endl;	
	cout<<o.value<<" incidence: "<<o.incidence<<endl;	
	cout<<p.value<<" incidence: "<<p.incidence<<endl;	
	cout<<q.value<<" incidence: "<<q.incidence<<endl;	
	cout<<r.value<<" incidence: "<<r.incidence<<endl;	
	cout<<s.value<<" incidence: "<<s.incidence<<endl;	
	cout<<t.value<<" incidence: "<<t.incidence<<endl;	
	cout<<u.value<<" incidence: "<<u.incidence<<endl;	
	cout<<v.value<<" incidence: "<<v.incidence<<endl;	
	cout<<w.value<<" incidence: "<<w.incidence<<endl;	
	cout<<x.value<<" incidence: "<<x.incidence<<endl;	
	cout<<y.value<<" incidence: "<<y.incidence<<endl;	
	cout<<z.value<<" incidence: "<<z.incidence<<endl;		

}

void Huffman::build()
{
	tav lft, rght, ezer;

	while(check()==false)
	{
		lft = heap.RemoveTop();
		rght = heap.RemoveTop();

		ezer.incidence = lft.incidence + rght.incidence;
		ezer.left = new tav(lft);
		strcpy(ezer.left->son,"0");
		strcpy(ezer.left->kod,"0");


		ezer.right = new tav(rght);
		strcpy(ezer.right->son,"1");
		strcpy(ezer.right->kod,"1");



		heap.Insert(ezer);
	}

	lft = heap.RemoveTop();
	strcpy(lft.son,"0");
	strcpy(lft.kod,"0");

	rght = heap.RemoveTop();
	strcpy(rght.son,"1");
	strcpy(rght.kod,"1");

	ezer.incidence = lft.incidence + rght.incidence;
	ezer.left = new tav(lft);
	ezer.right = new tav(rght);


	heap.Insert(ezer);
	root = heap.GetRoot();

	kidud(root);
}

bool Huffman::check()
{
	tav first, second;
	first = heap.RemoveTop();
	second = heap.RemoveTop();

	if(heap.IsEmpty()!=0)
	{
		heap.Insert(first);
		heap.Insert(second);
		return true;
	}
	else
	{	
		heap.Insert(first);
		heap.Insert(second);
		return false;
	}
}

void Huffman::kidud(tav* temp)
{
	if (temp)
  {		
		if(temp->incidence!=root->incidence)
		{
			if(temp->right!=NULL)
			{
				temp->right->kod = new char[strlen(temp->kod)+1];
				strcpy(temp->right->kod, temp->kod);
				strcat(temp->right->kod, "1");
			}
			if(temp->left!=NULL)
			{
				temp->left->kod = new char[strlen(temp->kod)+1];
				strcpy(temp->left->kod, temp->kod);
				strcat(temp->left->kod, "0");
			}
		}
		if(temp->value!=0)
		{
			tavla(temp->value, temp->kod);
		}

		kidud(temp->left);
		kidud(temp->right);
	}
}

void Huffman::tavla(char place, char* val)
{
	place = hamara(place);
	vec[place].Add(val);
}

char* Huffman::kodTavla(char* val)
{
	return vec[hamara(*val)].FirstElement();
}

int Huffman::checkval(char* val)
{
	for(int i=0; i<27; i++)
	{
		if(strcmp(vec[i].FirstElement(),val)==0)
		{				
			return i;
		}
	}

	return 100;
}

void Huffman::print()
{
	List<char*> l;
	int flag = 0;

	for(int i=0; i<27; i++)
	{
		cout<<"\ntav "<<hamara(i)<<" kod: ";
		cout<<vec[i].FirstElement()<<" ";
	}
}

void Huffman::decode(ifstream &file)
{
	char ch;
	tav* maslul;

	while(file.get(ch))
	{ 
		maslul = root;
		while((maslul!=NULL)&&(file.get(ch)))
		{
			if(ch=='0')
			{
				maslul = maslul->left;		
			}
			else
				if(ch=='1')
			{
				maslul = maslul->right;
			}

			if(maslul->value!=0)
			{
				cout<<maslul->value;
				maslul = NULL;
			}
		}
	}
}

void Huffman::code(ifstream &file)
{
	char ch;

	while(file.get(ch))//&&(file1.get(ch))&&(file2.get(ch)))
	{ 
		cout<<kodTavla(&ch);
	}
}

int Huffman::hamara(char tav)
{
	if(tav==' ')
	{
		return 0;
	}
	else
	{
		switch(tav)
		{	
			case 'a':
			{
				return 1;
			}
			case 'b':
			{
				return 2;
			}
			case 'c':
			{
				return 3;
			}
			case 'd':
			{
				return 4;
			}
			case 'e':
			{
				return 5;
			}
			case 'f':
			{
				return 6;
			}
			case 'g':
			{
				return 7;
			}
			case 'h':
			{
				return 8;
			}
			case 'i':
			{
				return 9;
			}
			case 'j':
			{
				return 10;
			}
			case 'k':
			{
				return 11;
			}
			case 'l':
			{
				return 12;
			}
			case 'm':
			{
				return 13;
			}
			case 'n':
			{
				return 14;
			}
			case 'o':
			{
				return 15;
			}
			case 'p':
			{
				return 16;
			}
			case 'q':
			{
				return 17;
			}
			case 'r':
			{
				return 18;
			}
			case 's':
			{
				return 19;
			}
			case 't':
			{
				return 20;
			}
			case 'u':
			{
				return 21;
			}
			case 'v':
			{
				return 22;
			}
			case 'w':
			{
				return 23;
			}
			case 'x':
			{
				return 24;
			}
			case 'y':
			{
				return 25;
			}
			case 'z':
			{
				return 26;
			}
		}
	}
	return 0;
}

char Huffman::hamara(int tav)
{
	switch(tav)
	{
		case 0:
		{
			return ' ';
		}
		case 1:
		{
			return 'a';
		}
		case 2:
		{
			return 'b';
		}
		case 3:
		{
			return 'c';
		}
		case 4:
		{
			return 'd';
		}
		case 5:
		{
			return 'e';
		}
		case 6:
		{
			return 'f';
		}
		case 7:
		{
			return 'g';
		}
		case 8:
		{
			return 'h';
		}
		case 9:
		{
			return 'i';
		}
		case 10:
		{
			return 'j';
		}
		case 11:
		{
			return 'k';
		}
		case 12:
		{
			return 'l';
		}
		case 13:
		{
			return 'm';
		}
		case 14:
		{
			return 'n';
		}
		case 15:
		{
			return 'o';
		}
		case 16:
		{
			return 'p';
		}
		case 17:
		{
			return 'q';
		}
		case 18:
		{
			return 'r';
		}
		case 19:
		{
			return 's';
		}
		case 20:
		{
			return 't';
		}
		case 21:
		{
			return 'u';
		}
		case 22:
		{
			return 'v';
		}
		case 23:
		{
			return 'w';
		}
		case 24:
		{
			return 'x';
		}
		case 25:
		{
			return 'y';
		}
		case 26:
		{
			return 'z';
		}
	}
}

אוקי יש לך כמה בעיות בסיסיות. וגם יותר מדי משתנים.

לספירת תווים אני מציע משהו כמו counting sort תעשי מערך בגודל 256 ותשתמשי ב unsigned char מתי שתקרא מהקובץ התו שתקראי ישמש כindex :

 
unsigned char ch;
int vals]256];
for(i=0;i<256;++i)vals[i]=0;
while(file.get(ch))
	{ 
vals[ch]++
}

אז את יכולה ליצר עלים לכל תו ולהשתמש בערכים שספרת שהם לא 0 (את יכולה להשעיר את ה0 הם יהיו בתחתית )בשביל כל עלה ולדחוף את כולם לHEAP.

מתי שאת מושכת רק ערך אחד מהheap והוא ריק סימת עם העץ.

עכשיו את עושה חיפוש על כל תו בשיטת depth first ושומרת את ה מסלול: 0 אם את הולכת שמאלה ו1 אם את הולכת ימינה. את גם צריכה לדעת כמה צעדים היו לך לכל תו. ככה את מיצרת טבלה של הרפרזנתציה של כל תו ושומרת אותה במערך קידוד. כשאת רוצה לקודד משהו את הולכת לטבלה באותה דרך כמו שספרת תווים ומשתמשת בערכים שם לעשות הכנסה של ביטים .

את צריכה דרך לעשות מניפולציה של ביטים יש אולי bit vector בSTL . בשביל להפוך את המידע חזרה למקור את פשוט רצה על העץ לפי הביטים שאת מקבלת ומתי שאת מגיעה לעלה את משתמשת בערך התו שלו וחוזרת לראש העץ. הswitch לא יעבוד כי כל קוד הוא באורך ביטי שונה.

קוד של עץ הפמן מאוד נפוץ כי משתמשים בו הרבה בדחיסה יש בzlib ו bzip2 וgzip שהם כולם קודים פתוחים אבל לרוב האימפמתציה היא ב C.

עריכה: שינוי ללשון נקבה (לא שמתי לב לשם רק לשאלה :-[ )

במקום לעשות מלא CASEים, את יכולה להמיר לCHAR ולהוסיף '0'.

ואת יכולה לרשום רק את הקוד החשוב? אין לי כוח לקרוא את הכל.

אני הסתבכתי בשלב של להפוך קובץ בינארי (עם אפסים ואחדים) לקובץ טקסט.

לקחתי את הקובץ טקסט שקודדתי ושמרתי בקובץ, את הקובץ הזה אני מנסה לפענח ולא מצליחה..

זו הפונקציית פיענוח:

void Huffman::decode(ifstream &file)
{
char ch;
tav* maslul;

while(file.get(ch))
{ 
maslul = root;
while((maslul!=NULL)&&(file.get(ch)))
{
if(ch=='0')
{
maslul = maslul->left; 
}
else
if(ch=='1')
{
maslul = maslul->right;
}

if(maslul->value!=0)
{
cout<<maslul->value;
maslul = NULL;
}
}
}
}

<הפונקציה הולכת בעץ עד שמגיעה לעלה ומדפיסה את ערכו>

לא עדיף לקצץ את הקוד למשל של sort למשהו כזה ?

void Huffman::sort(ifstream &file)

{

char ch;

int counter[27] = {0};

if(!file)

{

cout<<"\n\nerror";

exit(0);

}

while(file.get(ch))

{

if(ch==' ')

{

counter[26]++;

}

else if (!(ch >= 97 && ch <= 122))

{

continue;

}

counter[ch-97]++;

}

tav letter;

for (int i=0; i<26; i++)

{

letter.value = i+97;

letter.incidence = counter;

heap.Insert(letter);

cout<<letter.value<<" incidence: "<<letter.incidence<<endl;

}

letter.value = ' ';

letter.incidence = counter[27];

heap.Insert(letter);

cout<<letter.value<<" incidence: "<<letter.incidence<<endl;

}

כמו כן, יש סיבה ש son ו kod מוגדרים כפונטרים ולא כ char של אות אחת ? את מישום מה מנסה בכח להשתמש בהם כמחרוזת אותיות כאשר את רק מאכסנת שם אות אחת בפועל?

התיחסות לקובץ בינארי

לא דיבגתי את זה אז תצתרכי לעבור על זה ולבדוק את זה

int i=8;
int end_of_file=0;
while(!end_of_file)
{ 
maslul = root;
while((maslul!=NULL))
{
	if(i==8)
	{
	i=0;
		if(end_of_file=!file.get(ch)) 
			break;
	}
		if(ch&(1<<(7-i))) /* check the most seginificant bit first */
		{
		maslul = maslul->left; 
		}
		else
		{
		maslul = maslul->right;
		}
		i++;
		if(maslul->value!=0)
		{
		cout<<maslul->value;
		maslul = NULL;
		}
	}
}

תבדקי ל-מה אני מתיחס במקום ל'0' ו ה'1' זאת הדרך לעשות bit extraction אני משתמש ב C ב C++ צריך לבדוק אם זה לא שווה ל0 בשביל 1.

חוץ מזה תהיה בעיה לדעת מה הוא סוף הקובץ בגלל שהקבצים בנויים מבייטים ולא ביטים יש סיכוי שלא תשתמשי בכל הבייט האחרון אז צריך להתיחס לזה איך שהו בקוד.

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

כמו כן, יש סיבה ש son ו kod מוגדרים כפונטרים ולא כ char של אות אחת ? את מישום מה מנסה בכח להשתמש בהם כמחרוזת אותיות כאשר את רק מאכסנת שם אות אחת בפועל?

בKOD אני אחר כך משנה את אורכו (לפי המסלול שאני הולכת בעץ) ולכן הוא מוגדר כמצביע.

אם אגדרי את SON כCHAR כמדומני שלא תהייה לי אפשרות להשתמש בפונקציות של הספריה STRING.H.

הבעיה שלי:

אחרי שהפכתי קובץ טקסט לקובץ אפסים ואחדים איך אני הופכת קובץ של אפסים ואחדים לקובץ תוים???

<ניסיתי לשמור בקובץ את הפלט שיצא מהפיכת הקובץ טקסט לבינארי ואותו אחר כך להפוך לקובץ טקסט (הייתי אמורה לקבל את אותו הטקסט) אבל זה לא יצא?>

יש למשהו רעיון לפתרון???

למה ישר לכתוב לא נכון(במיוחד שזה אמור להקל). את מבצעת כל מיני דברים שלא צריך(כמו השימוש במחרוזות), ויתכן שהסרבול הזה גורם לך לחלק מהבעיות.