Huffman encoding and decoding using template
This Hufffman using encoding and decoding of characters through iterating within a file of text
//in the name of allah
#include
#include
#include
#include"code_char.h"
#include"heap_class.h"
#include"heap.h"
using namespace std;
int paus;
bool read_file(char* en_words,int *number,list *w){//this template must be used when we add to heap ,PQueue* heap(int * a)=0,int * number=0){
fstream file;
file.open(en_words,ios::in);
if(!file)
return false;
//code_ch *w=new code_ch[200];
file.seekg(0,ios::end);
int end=file.tellg();
file.seekg(0,ios::beg);
int i=0;
char ch;
while(i
file.seekg(i,ios::beg);
file.read((char*)&ch,1);
i++;
//if(ch=='\n' || ch=='\13')
//continue;
// if(ch=='\13')
// continue;
if(!number[ch]){//if is not yet inserted to list
code_ch *tmp=new code_ch;
number[ch]++;
tmp->ch=ch;
tmp->number=number[ch];//later we update this
w->push_back(*tmp);//w->push_front(tmp);///
}
else
number[ch]++;
}
//updateing the numbers
list::iterator p=w->begin();
while(p!=w->end()){ ///point
p->number=number[p->ch];
p++;
}
//copy(w->begin(),w->end(),ostream_iterator(cout,""));
return true;
}
code_ch * huffman(PQueue &p,int n){
code_ch *x;//=new code_ch;
code_ch *y;//=new code_ch;
for(int i=1;i
code_ch *z=new code_ch;
z->left=x=&p.extractMin();
z->right=y=&p.extractMin();
z->number=x->number+y->number;
p.insert(z);
}
return &p.extractMin();
}
//this function finds the code of eeach element in the huffman tree that i create.
void find_code(code_ch *h,int i=-1){///h is root
i++;
if(h->left!=NULL){
for(int k=0;k
if(h->code[0][k])
h->left->code[0][k]=true;
else
h->left->code[0][k]=false;
}
h->left->code[0][i]=false;
h->left->code_length=h->code_length+1;
find_code(h->left,i);
}
if(h->right!=NULL){
for(int k=0;k
if(h->code[0][k])
h->right->code[0][k]=true;
else
h->right->code[0][k]=false;
}
h->right->code[0][i]=true;
h->right->code_length=h->code_length+1;
find_code(h->right,i);
}
}
//this function "mirizad" tree in an array for useing when encodeing from file for each character we can find the element in the tree easily.
code_ch ** inar(code_ch *root){//,int tree_size){
static code_ch **l=new code_ch*[200];//l[197] points to an element in the tree that its character is 'a'
l[root->ch]=root;
if(root->left!=NULL)
inar(root->left);//,tree_size);
if(root->right!=NULL)
inar(root->right);//,tree_size);
return l;
}
int get_size(code_ch *root){//returns number of bits
static int size=0;
if(root->left!=NULL)
get_size(root->left);
if(root->right!=NULL)
get_size(root->right);
if(!root->left || !root->right)
size+=root->number*root->code_length;
return size;//this is number of bits
}
void encodeing(code_ch *root,char * en_file,code_ch **Arcode,int size){
//cout<<"coming in incodeing"<
fstream rfile,wfile;
rfile.open(en_file,ios::in);
wfile.open("encoded.txt",ios::out);
if(!rfile || !wfile)
throw runtime_error("cannot open the files...\n");
rfile.seekg(0,ios::end);
int end=rfile.tellg();
rfile.seekg(0,ios::beg);
int i=0,seek=0,j=0;
char ch;
//cout<<"declaring A"<
bitArray A(size);
//cout<<"this is size="<<
//cout<<"after"<
while(i
rfile.seekg(i,ios::beg);
rfile.read((char*)&ch,1);
//cout<<<" ";
//cout<<" "<
for(j=0;jcode_length;j++){
//cout<<" j="<
if(Arcode[ch]->code[0][j]){//if true
//cout<<1;
//cout<<" "<<1<<" ";
A[j+seek]=true;
}
else{
//cout<<0;
//cout<<" 0 ";;
A[j+seek]=false;
}
}
seek+=j;
//cout<<<"seek is:"<<
//cout<
i++;
}
i=0;
while(i<=size/8+1){
ch=(char)A.a[i];
wfile.seekp(i,ios::beg);
wfile.write(&ch,1);
i++;
}
//wfile.write((char*)&A.a,size/8+1); ///point
//cout<<"in file:"<<
wfile.close();
rfile.close();
//cout<<"file closed"<
}
void inorderWalk(code_ch *root){
if(root->left!=NULL)
inorderWalk(root->left);
cout<ch<<" "<number<
if(root->right!=NULL)
inorderWalk(root->right);
}
void decoding(code_ch *root,int size){//very simple only read from file and if 0 go to left else go to right
//cout<<"coming into decodig"<
//cout<<"--------------------------------------------------size="<<
code_ch *p=root;
fstream rfile,wfile;
rfile.open("encoded.txt",ios::in);
wfile.open("decoded.txt",ios::out);
//cout<<"after openning the files"<
if(!rfile || !wfile)
throw runtime_error("cannot open the files...\n");
rfile.seekg(0,ios::end);
int end=rfile.tellg();
rfile.seekg(0,ios::beg);
int i=0,j=0;
char ch;
//cout<<"before declaring A"<
//cout<<"--------------------------------------------------size="<<
bitArray A(size);
//cout<<"--------------------------------------------------size="<<
//cout<<5<
//cout<<"root hehhhhhhhhhhhhhere :"<left->number<
//cout<<"--------------------------------------------------size="<<
i=0;
while(i<=size/8+1){
rfile.seekg(i,ios::beg);
rfile.read(&ch,1);
A.a[i]=(unsigned char)ch;
i++;
}
rfile.seekg(0,ios::beg);
i=0;
while(i<=size){//while(!file.eof()){
//cout<<"in while"<
if(A[i]){//if it is true go to right
//cout<<1;
if(p->right!=NULL)
p=p->right;
else {
wfile.seekp(j,ios::beg);
wfile.write((char*)&p->ch,1);
j++;
p=root;
continue;///point
}
}
else{
//cout<<"--------------before else"<
//cout<<0;
if(p->left!=NULL){
//cout<<"in if of else"<
p=p->left;
}
else {
//cout<<"in else of it"<
wfile.seekp(j,ios::beg);
wfile.write((char*)&p->ch,1);
j++;
p=root;
continue;///point
}
}
i++;
}
// cout<<9<
rfile.close();
wfile.close();
//cout<<10<
}
int main(int argc,char **argv){
if(argc==1){
cout<<"you haven't entered a file! exiting..."<
return 1;
}
listw;
int *a=new int [200];//for saving the number of each ch
for(int i=0;i<200;i++)
a[i]=0;
bool is_read=read_file(argv[1],a,&w);
if(!is_read)
throw runtime_error("cannot open the file you entered...\n");
//cout<<"and the heap"<<
PQueue p(w);
code_ch *root=huffman(p,w.size());
find_code(root);
int size=get_size(root);
//cout<<"this is size in the main:"<<
code_ch ** Arcode=inar(root);//,int tree_size);
char *coded;
//cout<<"first puase:"<
//cin>>paus;
int paus1;
encodeing(root,argv[1],Arcode,size);//encodeing(root,argv[1],Arcode,size);
//cout<<" puase2:"<
//cin>>paus;
decoding(root,size);
cout<<"tamam"<
//cout<
return 0;
}
;> ;> ;> ;> ;> ,200> ;> ;> ;> ;> ;> ;> ;> ;> ;> ;> ;> ;> ;> ; > ;> ;> ;> ;> ;> ;> ()> ;> ;> ;>[ch]-> ;> ){> ;> ;> ;> ;>;k++){>;k++){> ;i++){> ,200> ){>
This Hufffman using encoding and decoding of characters through iterating within a file of text
//in the name of allah
#include
#include
#include
#include"code_char.h"
#include"heap_class.h"
#include"heap.h"
using namespace std;
int paus;
bool read_file(char* en_words,int *number,list
fstream file;
file.open(en_words,ios::in);
if(!file)
return false;
//code_ch *w=new code_ch[200];
file.seekg(0,ios::end);
int end=file.tellg();
file.seekg(0,ios::beg);
int i=0;
char ch;
while(i
file.seekg(i,ios::beg);
file.read((char*)&ch,1);
i++;
//if(ch=='\n' || ch=='\13')
//continue;
// if(ch=='\13')
// continue;
if(!number[ch]){//if is not yet inserted to list
code_ch *tmp=new code_ch;
number[ch]++;
tmp->ch=ch;
tmp->number=number[ch];//later we update this
w->push_back(*tmp);//w->push_front(tmp);///
}
else
number[ch]++;
}
//updateing the numbers
list
while(p!=w->end()){ ///point
p->number=number[p->ch];
p++;
}
//copy(w->begin(),w->end(),ostream_iterator
return true;
}
code_ch * huffman(PQueue
code_ch *x;//=new code_ch;
code_ch *y;//=new code_ch;
for(int i=1;i
code_ch *z=new code_ch;
z->left=x=&p.extractMin();
z->right=y=&p.extractMin();
z->number=x->number+y->number;
p.insert(z);
}
return &p.extractMin();
}
//this function finds the code of eeach element in the huffman tree that i create.
void find_code(code_ch *h,int i=-1){///h is root
i++;
if(h->left!=NULL){
for(int k=0;k
if(h->code[0][k])
h->left->code[0][k]=true;
else
h->left->code[0][k]=false;
}
h->left->code[0][i]=false;
h->left->code_length=h->code_length+1;
find_code(h->left,i);
}
if(h->right!=NULL){
for(int k=0;k
if(h->code[0][k])
h->right->code[0][k]=true;
else
h->right->code[0][k]=false;
}
h->right->code[0][i]=true;
h->right->code_length=h->code_length+1;
find_code(h->right,i);
}
}
//this function "mirizad" tree in an array for useing when encodeing from file for each character we can find the element in the tree easily.
code_ch ** inar(code_ch *root){//,int tree_size){
static code_ch **l=new code_ch*[200];//l[197] points to an element in the tree that its character is 'a'
l[root->ch]=root;
if(root->left!=NULL)
inar(root->left);//,tree_size);
if(root->right!=NULL)
inar(root->right);//,tree_size);
return l;
}
int get_size(code_ch *root){//returns number of bits
static int size=0;
if(root->left!=NULL)
get_size(root->left);
if(root->right!=NULL)
get_size(root->right);
if(!root->left || !root->right)
size+=root->number*root->code_length;
return size;//this is number of bits
}
void encodeing(code_ch *root,char * en_file,code_ch **Arcode,int size){
//cout<<"coming in incodeing"<
fstream rfile,wfile;
rfile.open(en_file,ios::in);
wfile.open("encoded.txt",ios::out);
if(!rfile || !wfile)
throw runtime_error("cannot open the files...\n");
rfile.seekg(0,ios::end);
int end=rfile.tellg();
rfile.seekg(0,ios::beg);
int i=0,seek=0,j=0;
char ch;
//cout<<"declaring A"<
bitArray A(size);
//cout<<"this is size="<
//cout<<"after"<
while(i
rfile.seekg(i,ios::beg);
rfile.read((char*)&ch,1);
//cout<
//cout<<" "<
for(j=0;jcode_length;j++){
//cout<<" j="<
if(Arcode[ch]->code[0][j]){//if true
//cout<<1;
//cout<<" "<<1<<" ";
A[j+seek]=true;
}
else{
//cout<<0;
//cout<<" 0 ";;
A[j+seek]=false;
}
}
seek+=j;
//cout<
//cout<
i++;
}
i=0;
while(i<=size/8+1){
ch=(char)A.a[i];
wfile.seekp(i,ios::beg);
wfile.write(&ch,1);
i++;
}
//wfile.write((char*)&A.a,size/8+1); ///point
//cout<<"in file:"<
wfile.close();
rfile.close();
//cout<<"file closed"<
}
void inorderWalk(code_ch *root){
if(root->left!=NULL)
inorderWalk(root->left);
cout<
if(root->right!=NULL)
inorderWalk(root->right);
}
void decoding(code_ch *root,int size){//very simple only read from file and if 0 go to left else go to right
//cout<<"coming into decodig"<
//cout<<"--------------------------------------------------size="<
code_ch *p=root;
fstream rfile,wfile;
rfile.open("encoded.txt",ios::in);
wfile.open("decoded.txt",ios::out);
//cout<<"after openning the files"<
if(!rfile || !wfile)
throw runtime_error("cannot open the files...\n");
rfile.seekg(0,ios::end);
int end=rfile.tellg();
rfile.seekg(0,ios::beg);
int i=0,j=0;
char ch;
//cout<<"before declaring A"<
//cout<<"--------------------------------------------------size="<
bitArray A(size);
//cout<<"--------------------------------------------------size="<
//cout<<5<
//cout<<"root hehhhhhhhhhhhhhere :"<
//cout<<"--------------------------------------------------size="<
i=0;
while(i<=size/8+1){
rfile.seekg(i,ios::beg);
rfile.read(&ch,1);
A.a[i]=(unsigned char)ch;
i++;
}
rfile.seekg(0,ios::beg);
i=0;
while(i<=size){//while(!file.eof()){
//cout<<"in while"<
if(A[i]){//if it is true go to right
//cout<<1;
if(p->right!=NULL)
p=p->right;
else {
wfile.seekp(j,ios::beg);
wfile.write((char*)&p->ch,1);
j++;
p=root;
continue;///point
}
}
else{
//cout<<"--------------before else"<
//cout<<0;
if(p->left!=NULL){
//cout<<"in if of else"<
p=p->left;
}
else {
//cout<<"in else of it"<
wfile.seekp(j,ios::beg);
wfile.write((char*)&p->ch,1);
j++;
p=root;
continue;///point
}
}
i++;
}
// cout<<9<
rfile.close();
wfile.close();
//cout<<10<
}
int main(int argc,char **argv){
if(argc==1){
cout<<"you haven't entered a file! exiting..."<
return 1;
}
list
int *a=new int [200];//for saving the number of each ch
for(int i=0;i<200;i++)
a[i]=0;
bool is_read=read_file(argv[1],a,&w);
if(!is_read)
throw runtime_error("cannot open the file you entered...\n");
//cout<<"and the heap"<
PQueue
code_ch *root=huffman(p,w.size());
find_code(root);
int size=get_size(root);
//cout<<"this is size in the main:"<
code_ch ** Arcode=inar(root);//,int tree_size);
char *coded;
//cout<<"first puase:"<
//cin>>paus;
int paus1;
encodeing(root,argv[1],Arcode,size);//encodeing(root,argv[1],Arcode,size);
//cout<<" puase2:"<
//cin>>paus;
decoding(root,size);
cout<<"tamam"<
//cout<
return 0;
}