decode.cpp

huffman decode all you need is input a data so that it will decode

#include<iostream>
#include<fstream>
#include<cmath>
#define debug if(0)
#include "MinHeapTree.h"
using namespace std;
class node{
	public:
	int v;
	node *r,*l;
	char *code;
	int asc;
	node(int i,int ch){
		v=i;
		r=0;
		l=0;
		asc=ch;
		code=0;
	}
	~node(){
		delete r;
		delete l;
		delete code;
	}
	void setcode(char *co,char *ac){
		if(code)delete code;
		code=new char[strlen(co)+2];
		strcpy(code,co);
		strcat(code,ac);
		if(l)l->setcode(code,"0");
		if(r)r->setcode(code,"1");
	}
	void add(node * newer1,node * newer2){
		v = newer1->v ;
		l=newer1;
		if(newer2){
			v += newer2->v ;
			r=newer2;
		}
	}
};
int compare(node *a,node *b){
	return a->v-b->v;
}

class Huffman_code{
	public:
		unsigned char c;
		int n;
		char**code;
		Huffman_code(){
			code=0;
			n=0;
		}
		void print(ostream *fout,int i){
			if(n){
				if(i!=256){
					(*fout)<<(int)(unsigned char)c;
					if(c=='\n')(*fout)<<"\t\'\\n\'";  
					else if(c=='\r')(*fout)<<"\t\'\\r\'";  
					else if(c=='\t')(*fout)<<"\t\'\\t\'";  
					else (*fout)<<"\t\'"<<c<<"\'";  
				}else (*fout)<<"EOF\teof";
				(*fout)<<"\t"<<n<<"\t";
				if(code)if(*code)(*fout)<<(*code);
				(*fout)<<endl;
			}
		}
};
class readbit{
	istream *fin;
	unsigned char binary;
	char temp;
	public:
		readbit(istream *instream){
			fin=instream;
			binary=0;
		}
		bool read(bool *bit){
			if(binary){
				if(temp & binary)*bit=true;
				else *bit=false;
				binary>>=1;
				return true;
			}else{
				if(fin->read(&temp,1)){
					binary=128;
					return read(bit);
				}else return false;
			}
		}
};
class writebit{
	ofstream *fout;
	char temp;
	int i;
	public:
		int allsize;
	writebit(ofstream *fileopen){
		fout=fileopen;
		i=7;
		temp=0;
		allsize=0;
	}
	void write(char code){
		for(unsigned char j=128;j!=0;j>>=1){
			if(code & j)write("1");
			else write("0");
		}
	}
	void write(char *code){
		if(*code){
			allsize++;
			if(*code=='1')temp+=(char)pow((double)2,i);
			i--;
			if(i<0){
				i+=8;
				fout->write(&temp,1);
				temp=0;
			}
			write(++code);
		}
		
	}
	void close(){
		if(i!=7)fout->write(&temp,1);
		fout->close();
	}
};
class Huffmantable{
	Huffman_code hc[257];
	node *root;
	public:
		Huffmantable(){
			root=0;
			for(int i=0;i<256;i++){
				hc[i].c=(char)i;
			}
			hc[256].c=1;
			hc[256].n=1;
		}
		void add(unsigned char c){
			hc[(int)c].n++;
			
		}
		node* readhct(readbit *rb){
			bool bit=1;
			node *newnode;
			if(root){
				rb->read(&bit);
			}
			if(bit){
				newnode=new node(-1,-2);
				if(!root)root=newnode;
				newnode->l=readhct(rb);
				newnode->r=readhct(rb);
				return newnode;
			}else{
				unsigned char temp=0;
				rb->read(&bit);
				if(bit){
					temp=0;
					for(unsigned char i=128;i>0;i>>=1){
						rb->read(&bit);
						if(bit)temp|=i;
					}
					newnode=new node(-1,(unsigned char)temp);
					hc[temp].n=1;
					hc[temp].code=&newnode->code;
					return newnode;
				}else {
					newnode=new node(1,-1);
					hc[256].code=&newnode->code;
					return newnode;
				}
			}
		}
		void writehct(node *n,writebit *wf){
			if(n!=root){
				if(n->asc > -2){
					wf->write("0");
					if(n->asc == -1)wf->write("0");
					else {
						wf->write("1");
						wf->write((char)n->asc);
					}
				}else wf->write("1");
			}
			if(n->l)writehct(n->l,wf);
			if(n->r)writehct(n->r,wf);
		}
		
		
		void buildtree(){
			minheaptree <node*> *mht=new minheaptree <node*>(compare);
			node* tn1;
			node* tn2;
			if(root)delete root;
			root=0;
			for(int i=0;i<257;i++){
				if(hc[i].n){
					if(i==256)tn1=new node(1,-1);
					else tn1=new node(hc[i].n,hc[i].c);
					hc[i].code=&tn1->code;
					mht->add(tn1);
				}
			
			}
			cout<<endl;
			while(!mht->isempty()){
				tn2=0;
				if(root)mht->add(root);
				tn1= mht->minimum();
				if(!mht->isempty()){
					tn2= mht->minimum();
				}
				root=new node(-1,-2);
				root->add(tn1,tn2);
			}
			root->setcode("","");
			delete mht;
		}
		void print(ostream *fout=&cout){
			(*fout)<<"Huffman encoding table:\n";
			(*fout)<<"Decimal-character-frequency-Huffman_code\n";
			for(int i=0;i<257;i++)
				hc[i].print(fout,i);
		}
		void zipfile(char *readfile,char *writefile){
			ifstream fin(readfile,ios::binary);
			ofstream fout(writefile,ios::binary);
			writebit wf(&fout);
			writehct(root,&wf);
			unsigned char temp;
			int bs=0,as=0;
			while(fin.read((char *)&temp,1)){
				bs+=8;
				wf.write( *(hc[(int)temp].code) );
				as+=strlen(*(hc[(int)temp].code));
				
			}
			as+=strlen(*(hc[256].code));
			wf.write( *(hc[256].code) );
			wf.close();
			printf("Huffman to ASCII encoding ratio = %d/%d = %.2f%%\n",as,bs,100.0*as/bs);
			printf("Huffman(include tree) to ASCII encoding ratio = %d/%d = %.2f%%\n",wf.allsize,bs,100.0*wf.allsize/bs);
		}
		void unzipfile(char *readfile,char *writefile){
			ifstream fin(readfile,ios::binary);
			ofstream fout(writefile,ios::binary);
			node * pointer=0;
			bool bit;
			readbit rb(&fin);
			
			if(root)delete root;
			root=0;
			root=readhct(&rb);
			root->setcode("","");
			pointer=root;
			while(rb.read(&bit)){
				
				if(bit) pointer=pointer->r;
				else pointer=pointer->l;
				if(pointer->asc > -2){
					if(pointer->asc >= 0){
						fout<<(char)pointer->asc;
						pointer=root;
					} else{
						fin.close();
						fout.close();
						return;
					}
				}
				
			}
			
		}
};

int main(int argc,char*argv[]){
	Huffmantable ht;
	if(argc<2)return 0;
	cout<<"unziping..."<<endl;
	if( argc==2 )ht.unzipfile(argv[1],"9517144.txt");
	else ht.unzipfile(argv[1],argv[2]);
	ofstream fout("codebook.txt");
	ht.print(&fout);
	ht.print();
}