11/4/10

Huffman encoding and decoding using template

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;
}



 

3 comments:

leave me messege