DataCompression/HuffmanVC2.cpp at master · reprotector/DataCompression

923 lines (817 loc) · 22.3 KB
#include<iostream>
#include<fstream>
#include<string>
#include<iomanip> //for width()
#include<cctype> //for sprintf()
#define HELP_ERROR 99
#define width_unit 5
using namespace std;
// (Templated d-heap) (on dynamic array of pointers)
// priority queue
// min (root=min) ((balanced) d-tree on dynamic array) d-heap
template<class T>
class Queue
    public:
        Queue(int d); //constructor 
        Queue();
        ~Queue(void); //destructor
        void enq(T*); //enqueue (to push)
        T* deq(void); //dequeue (to pop)
        T* front(void); //the front element
        bool empty(void) const; //is empty?
        bool full(void) const; //is full?
        void init(int d);
    //private:
        int back; //the last element in the queue
        T* *arr; //dynamic array
        int size; //current size of the queue array
        static const int SIZE=10; //size increment step size  
        int D; //max number of children for a parent>=2 
        //copy constructor and assignment are hidden to protect 
        Queue(const Queue &);
        const Queue & operator=(const Queue &);
        //utility functions to fix the heap
        //when an element added or removed 
        void reheapup(int, int); //fix heap upward
        void reheapdown(int, int); //fix heap downward
        void swap(T* &, T* &); //swap f. needed by reheapup/down functions
}; //end class
template<class T>
Queue<T>::Queue()
template<class T>
void Queue<T>::init(int d)
  if(d<2) d=2; //min a 2-heap is supported
	size=SIZE;
	arr=new T*[size];
// constructor (creates a new queue) 
template<class T>
Queue<T>::Queue(int d)
    if(d<2) d=2; //min a 2-heap is supported
    back=0;
    size=SIZE;
    arr=new T*[size];
// is queue empty?
template<class T>
bool Queue<T>::empty(void) const
    return (back<=0);
// is queue full?
template<class T>
bool Queue<T>::full(void) const
    return (back>=size);
// the front element of the queue 
template<class T>
T* Queue<T>::deq(void)
    if(empty())
        cerr<<"deq error! exiting..."<<endl;
        exit(1);
    T* rval=arr[0];
    arr[0]=arr[back-1]; //the element in the back moved to front
    --back;
    reheapdown(0, back-1); //reheapdown called to fix the order back 
    return rval;
// a copy of the front element is returned but the queue is not changed
template<class T>
T* Queue<T>::front(void)
    if(empty())
        cerr<<"deq error! exiting..."<<endl;
        exit(1);
    return arr[0];
// a new element to put in the queue
template<class T>
void Queue<T>::enq(T* foo)
    if(full()) //if the array is full then make it larger
        int nsize=size+SIZE; //the size of the new array
        T* *narr=new T*[nsize]; //new array
        for(int i=0;i<size;++i) //copy old array to the new one
            narr[i]=arr[i];
        delete[] arr; //delete reserved old array mem
        arr=narr; //pointer update
        size=nsize; //size update
    //the new element added to the back of the queue
    //and the reheapup called to fix the order back
    arr[back++]=foo; //arr[back]=foo;++back;
    reheapup(0, back-1); 
// this is a recursive function to fix back the order in the queue
// upwards after a new element added back (bottom) of the queue 
template<class T>
void Queue<T>::reheapup(int root, int bottom)
    int parent; //parent node (in the virtual tree) of the bottom element
    if(bottom > root)
        parent=(bottom-1)/D;
        //compare the two node and if the order is wrong then swap them
        //and make a recursive call to continue upward in the virtual tree
        //until the whole tree heap order is restored   
        if(*arr[parent] > *arr[bottom])
            swap(arr[parent], arr[bottom]);
            reheapup(root, parent);
// this is a recursive function to fix back the order in the queue
// downwards after a new element added front (root) of the queue 
template<class T>
void Queue<T>::reheapdown(int root, int bottom)
    int minchild, firstchild, child;
    firstchild=root*D+1; //the position of the first child of the root
    if(firstchild <= bottom) //if the child is in the queue
        minchild=firstchild; //first child is the min child (temporarily)
        for(int i=2;i <= D;++i)
            child=root*D+i; //position of the next child
            if(child <= bottom) //if the child is in the queue
                //if the child is less than the current min child
                //then it will be the new min child
                if(*arr[child] < *arr[minchild])
                    minchild=child;
        //if the min child found is less then the root(parent node)
        //then swap them and call reheapdown() recursively and
        //continue to fix the order in the virtual tree downwards
        if(*arr[root] > *arr[minchild])
            swap(arr[root], arr[minchild]);
            reheapdown(minchild, bottom);
// the values of 2 variables will be swapped
template<class T>
void Queue<T>::swap(T* &a, T* &b)
// destructor (because default dest. does not erase the array)
template<class T>
Queue<T>::~Queue(void)
    delete[] arr;
// Huffman Tree
    private:
        class Node
            public:
                unsigned int freq;
                unsigned char ch;
                Node *left, *right;
                //constructor
                Node(void)
                    :freq(0), ch('\0'), left(NULL), right(NULL) {}
        Node *root;
        //copy cons. and assign. op. overload prototypes are private to
        //prevent them to be used
        Tree(const Tree &); //copy constructor
        const Tree & operator=(const Tree &); //assignment oper. overload
        void chop(Node * N); //destroys the tree
        void print(ostream &, Node *, int) const; //prints the tree
        void print(Node *, int) const; //prints the tree
    public:
        Tree(void); //constructor
        ~Tree(void); //destructor
        friend ostream & operator<<(ostream &, const Tree &);
        //utility functions to get or set class members
        unsigned int get_freq(void) const;
        unsigned char get_char(void) const;
        void set_freq(unsigned int);
        void set_char(unsigned char);
        Node* get_left(void) const;
        Node* get_right(void) const;
        void set_left(Node *);
        void set_right(Node *);
        Node* get_root(void) const;
        //comparison operator overloads to compare
        //2 objects of the class
        bool operator==(const Tree &) const;
        bool operator!=(const Tree &) const;
        bool operator<(const Tree &) const;
        bool operator>(const Tree &) const;
        bool operator<=(const Tree &) const;
        bool operator>=(const Tree &) const;
        //to get H. string of a given char
        void huf(Node *, unsigned char, string, string &) const; 
        //outputs the H. char-string pairs list
        void huf_list(Node *, string) const; 
        //to get char equivalent of a H. string (if exists)
        bool get_huf_char(string, unsigned char &) const;
        string print_char(Node *) const; //prints chars 
//constructor
Tree::Tree(void)
    Node* N=new Node;
    root=N;
//recursive func to delete the whole tree
void Tree::chop(Node *N)
        chop(N->left);
        chop(N->right);
        delete N;
//destructor for tree objects
Tree::~Tree(void)
    chop(root);
unsigned int Tree::get_freq(void) const
    return root->freq;
unsigned char Tree::get_char(void) const
    return root->ch;
void Tree::set_freq(unsigned int f)
    root->freq=f;
void Tree::set_char(unsigned char c)
    root->ch=c;
Tree::Node* Tree::get_left(void) const
    return root->left;
Tree::Node* Tree::get_right(void) const
    return root->right;
void Tree::set_left(Node* N)
    root->left=N;
void Tree::set_right(Node* N)
    root->right=N;
Tree::Node* Tree::get_root(void) const
    return root;
//the recursive tree output (w/ respect to its graph) fn.
void Tree::print(ostream & ost, Node * curr, int level) const
    if(curr) //if the current node is not null then
        print(ost,curr->right,level+1); //try to go to right node
        //output the node data w/ respect to its level
        ost<<setw(level*width_unit)<<print_char(curr)<<":"
           <<curr->freq<<endl;
        print(ost,curr->left,level+1); //try to go to left node
//the recursive tree print (w/ respect to its graph) fn.
void Tree::print(Node * curr, int level) const
    if(curr) //if the current node is not null then
        print(curr->right,level+1); //try to go to right node
        //print the node data w/ respect to its level
        cout<<setw(level*width_unit)<<print_char(curr)<<":"
            <<curr->freq<<endl;
        print(curr->left,level+1); //try to go to left node
//utility fn to output a tree
ostream & operator<<(ostream &ost, const Tree &t)
    t.print(ost, t.root, 1);
    return ost;
//the comparison operator overloads to compare 2 Huffman trees
bool Tree::operator==(const Tree & T) const
    return (root->freq == T.root->freq);    
bool Tree::operator!=(const Tree & T) const
    return (root->freq != T.root->freq);    
bool Tree::operator<(const Tree & T) const
    return (root->freq < T.root->freq);    
bool Tree::operator>(const Tree & T) const
    return (root->freq > T.root->freq);    
bool Tree::operator<=(const Tree & T) const
    return (root->freq <= T.root->freq);    
bool Tree::operator>=(const Tree & T) const
    return (root->freq >= T.root->freq);    
//Huffman string finder (recursive func.)
//input : a tree node to start the search, a char to find its
//        Huffman string equivalent, current Huffman string according to
//        position on the Huffman tree, and a string (by reference) to
//        copy the resulted full Huffman string end of the search
//return: none (except Huffman string by reference)
void Tree::huf(Node* N, unsigned char c, string str, string & s) const
    if(N) //if the node is not null
        //compare char of the leaf node and the given char
        if(!N->left && !N->right && N->ch == c)
            s=str; //if the char is found then copy the H. string
        else
            //continue to search if the same char still not found
            huf(N->left, c, str+"0",s);
            huf(N->right, c, str+"1",s);
//Huffman char-string lister (recursive func.)
//input : a tree node to start the search, current Huffman string according to
//        position on the Huffman tree
//output: whole list of char-H. string code list of the H. tree
void Tree::huf_list(Node* N, string str) const
    if(N) //if the node is not null
        if(!N->left && !N->right) //if it is a leaf node
            cout<<print_char(N)<<" "<<str<<endl;
        else
            //continue to search
            huf_list(N->left, str+"0");
            huf_list(N->right, str+"1");
//char finder with given Huffman string
//input : a Huffman string to traverse on the H. tree and
//        a u. char by ref. to copy the char found
//return: true if a char is found else false
bool Tree::get_huf_char(string s, unsigned char & c) const
    Node * curr=root;
    for(unsigned int i=0;i<s.size();++i)
        if(s[i]=='0') //go to left in the H. tree
            curr=curr->left;
        if(s[i]=='1') //go to right in the H. tree
            curr=curr->right;
    bool found=false;
    if(!curr->left && !curr->right) //if it is a leaf node
        found=true;
        c=curr->ch;
    return found;
//input : a H. tree node
//return: the same char as string or if the char is not printable
//        then its octal representation in the ASCII char set
string Tree::print_char(Node * N) const
    string s="";
    if(!N->left && !N->right) //if it is a leaf node
        unsigned char c=N->ch;
        //if the char is not printable then output its octal ASCII code
        if(iscntrl(c) || c==32) //32:blank char
            //calculate the octal code of the char (3 digits)
            char* cp=new char;
            for(int i=0;i<3;++i)
                sprintf(cp,"%i",c%8);
                c-=c%8;
                s=(*cp)+s;
            s='/'+s; // adds \ in front of the octal code
        else
            s=c;
    return s;
//the given bit will be written to the output file stream
//input : unsigned char i(:0 or 1 : bit to write ; 2:EOF) 
void huf_write(unsigned char i, ofstream & outfile)
    static int bit_pos=0; //0 to 7 (left to right) on the byte block
    static unsigned char c='\0'; //byte block to write
    if(i<2) //if not EOF
        if(i==1)
            c=c | (i<<(7-bit_pos)); //add a 1 to the byte
        else //i==0
            c=c & static_cast<unsigned char>(255-(1<<(7-bit_pos))); //add a 0
        ++bit_pos;
        bit_pos%=8;
        if(bit_pos==0)
            outfile.put(c);
            c='\0';
        outfile.put(c);
//input : a input file stream to read bits
//return: unsigned char (:0 or 1 as bit read or 2 as EOF) 
unsigned char huf_read(ifstream & infile)
    static int bit_pos=0; //0 to 7 (left to right) on the byte block
    static unsigned char c=infile.get();
    unsigned char i;
    i=(c>>(7-bit_pos))%2; //get the bit from the byte
    ++bit_pos;
    bit_pos%=8;
    if(bit_pos==0)
        if(!infile.eof())
            c=infile.get();
        else
    return i;     
int charTypeIdx(char c)
  if (c>='A'&&c<='Z'||c>='a'&&c<='z')
		switch (c)
			case 'a':
			case 'A':
			case 'e':
			case 'E':
			case 'i':
			case 'I':
			case 'o':
			case 'O':
			case 'u':
			case 'U':
			return 0;
			default:
			return 1;
		return 2;
//Huffman Encoder
void encoder(string ifile, string ofile, bool verbose)
    ifstream infile(ifile.c_str(), ios::in|ios::binary);
    if(!infile)
        cerr<<ifile<<" could not be opened!"<<endl;
        exit(1);
    if(ifstream(ofile.c_str()))
        cerr<<ofile<<" already exists!"<<endl;
        exit(1);
    //open the output file
    ofstream outfile(ofile.c_str(), ios::out|ios::binary);
    if(!outfile)
        cerr<<ofile<<" could not be opened!"<<endl;
        exit(1);
    //arrays to hold frequency table for all ASCII characters in the file
	unsigned int f[3][256];
    for (int j=0;j<3;j++)
		for(int i=0;i<256;++i)
			f[j][i]=0;
    //read the whole file and count the ASCII char table frequencies
    char c;
    unsigned char ch=' ';
	unsigned char prevch;
    while(infile.get(c))
		prevch=ch;
        ch=c;
		++f[charTypeIdx(prevch)][ch];
    infile.clear(); //clear EOF flag
    infile.seekg(0); //reset get() pointer to beginning
	Queue<Tree> q[3]={3,3,3};//use a 3-(priority)heap
	Tree* tp[3];
	for (int j=0;j<3;j++)
		for(int i=0;i<256;++i)
				//output char freq table to the output file
				//divide 32 bit u. int values into 4 bytes
				outfile.put(static_cast<unsigned char>(f[j][i]>>24));
				outfile.put(static_cast<unsigned char>((f[j][i]>>16)%256));
				outfile.put(static_cast<unsigned char>((f[j][i]>>8)%256));
				outfile.put(static_cast<unsigned char>(f[j][i]%256));
				if(f[j][i]>0)
					//send freq-char pairs to the priority heap as Huffman trees
					tp[j]=new Tree;
					(*tp[j]).set_freq(f[j][i]);
					(*tp[j]).set_char(static_cast<unsigned char>(i));
					q[j].enq(tp[j]);
    //construct the main Huffman Trees
    for (int j=0;j<3;j++)
		Tree* tp2;
		Tree* tp3;
			tp[j]=q[j].deq();
			if(!q[j].empty())
				//get the 2 lowest freq. H. trees and combine them into one
				//and put back into the priority heap
				tp2=q[j].deq();
				tp3=new Tree;
				(*tp3).set_freq((*tp[j]).get_freq()+(*tp2).get_freq());
				(*tp3).set_left((*tp[j]).get_root());
				(*tp3).set_right((*tp2).get_root());
				q[j].enq(tp3);
		while(!q[j].empty()); //until all sub-trees combined into one
    //find H. strings of all chars in the H. trees and put into a string matrix
	string H_table[3][256];
	for (int j=0;j<3;j++){
		unsigned char uc;
		for(unsigned short us=0;us<256;++us)
			H_table[j][us]="";
			uc=static_cast<unsigned char>(us);
			(*tp[j]).huf((*tp[j]).get_root(), uc, "", H_table[j][us]);
    /*if(verbose)
        cout<<*tp<<endl; //output the Huffman tree
        //output the char-H. string list 
        (*tp).huf_list((*tp).get_root(), "");
        cout<<"frequency table is "<<sizeof(unsigned int)*256<<" bytes"<<endl;
	unsigned int total_chars=(*tp[0]).get_freq()+(*tp[1]).get_freq()+(*tp[2]).get_freq();
    cout<<"total chars to encode:"<<total_chars<<endl;
    //output Huffman coded chars into the output file
    unsigned char ch2;
    while(infile.get(c))
		prevch=ch;
        ch=c;
        //send the Huffman string to output file bit by bit
		for(unsigned int i=0;i<H_table[charTypeIdx(prevch)][ch].size();++i)
			if(H_table[charTypeIdx(prevch)][ch].at(i)=='0')
			if(H_table[charTypeIdx(prevch)][ch].at(i)=='1')
            huf_write(ch2, outfile);
    ch2=2; // send EOF
    huf_write(ch2, outfile);
    infile.close();
    outfile.close();
} //end of Huffman encoder
//Huffman Decoder
void decoder(string ifile, string ofile, bool verbose)
    ifstream infile(ifile.c_str(), ios::in|ios::binary);
    if(!infile)
        cerr<<ifile<<" could not be opened!"<<endl;
        exit(1);
    if(ifstream(ofile.c_str()))
        cerr<<ofile<<" already exists!"<<endl;
        exit(1);
    //open the output file
    ofstream outfile(ofile.c_str(), ios::out|ios::binary);
    if(!outfile)
        cerr<<ofile<<" could not be opened!"<<endl;
        exit(1);
    //read frequency tables from the input file
	unsigned int f[3][256];
    char c;
    unsigned char ch;
    unsigned int j=1;
	for (int h=0;h<3;h++)
		for(int i=0;i<256;++i)
			//read 4 bytes and combine them into one 32 bit u. int value
			f[h][i]=0;
			for(int k=3;k>=0;--k)
				infile.get(c);
				f[h][i]+=ch*(j<<(8*k));
    //re-construct the Huffman trees
	//Queue<Tree> q[3]={3,3,3}; //use a 3-(priority)heap (again)
	int n = 256, v = 3;
	Queue<Tree> q[n];
	for(int i=0; i<n; ++i)
		q[n].init(v);
	Tree* tp[3];
	for (int j=0;j<3;j++)
		for(int i=0;i<256;++i)
			if(f[j][i]>0)
				//send freq-char pairs to the priority heap as Huffman trees
				tp[j]=new Tree;
				(*tp[j]).set_freq(f[j][i]);
				(*tp[j]).set_char(static_cast<unsigned char>(i));
				q[j].enq(tp[j]);
    //construct the main Huffman Trees (as in Encoder func.)
    for (int j=0;j<3;j++){
		Tree* tp2;
		Tree* tp3;
			tp[j]=q[j].deq();
			if(!q[j].empty())
				//get the 2 lowest freq. H. trees and combine them into one
				//and put back into the priority heap
				tp2=q[j].deq();
				tp3=new Tree;
				(*tp3).set_freq((*tp[j]).get_freq()+(*tp2).get_freq());
				(*tp3).set_left((*tp[j]).get_root());
				(*tp3).set_right((*tp2).get_root());
				q[j].enq(tp3);
		while(!q[j].empty()); //until all sub-trees combined into one
    /*if(verbose)
        cout<<*tp<<endl; //output the Huffman tree
        //output the char-H. string list 
        (*tp).huf_list((*tp).get_root(), "");
        cout<<"frequency table is "<<sizeof(unsigned int)*256<<" bytes"<<endl;
    //read Huffman strings from the input file
    //find out the chars and write into the output file
    string st;
    unsigned char ch2;
	unsigned char prevch=' ';
	unsigned int total_chars=(*tp[0]).get_freq()+(*tp[1]).get_freq()+(*tp[2]).get_freq();
    cout<<"total chars to decode:"<<total_chars<<endl;
	while(total_chars>0) //continue until no char left to decode 
        st=""; //current Huffman string
            //read H. strings bit by bit
            ch=huf_read(infile);
            if(ch==0)
                st=st+'0';
            if(ch==1)
                st=st+'1';
        } //search the H. tree
		while(!(*tp[charTypeIdx(prevch)]).get_huf_char(st, ch2)); //continue until a char is found
        //output the char to the output file
        outfile.put(static_cast<char>(ch2));
		prevch=ch2;
        --total_chars;
    infile.close();
    outfile.close();
} //end of Huffman decoder
void usage_msg ( const string & pname )
    cerr << "Usage: " << pname << " : valid flags are :" << endl
        << " -i input_file  : required" << endl
        << " -o output_file : required" << endl
        << " -e  : turn on encoding mode ( default )" << endl
        << " -d  : turn on decoding mode" << endl
        //<< " -v  : verbose mode" << endl
        << " -h  : this help screen" << endl;
int main( int argc, char * argv[] )
    string in_name;
    string out_name;
    bool encode = true;
	bool verbose = false;
    for ( int i = 1 ; i < argc ; ++i )
        if ( !strcmp( "-h", argv[i] ) || !strcmp( "--help", argv[i] ) )
            usage_msg( argv[0] );
            exit( HELP_ERROR );
        else if ( !strcmp( "-i", argv[i] ) )
            cerr << "input file is '" << argv[++i] << "'" << endl;
            in_name = argv[i];
        else if ( !strcmp( "-o", argv[i] ) )
            cerr << "output file is '" << argv[++i] << "'" << endl;
            out_name = argv[i];
        else if ( !strcmp( "-d", argv[i] ) )
            encode = false;
        else if ( !strcmp( "-e", argv[i] ) )
            encode = true;
        else if ( !strcmp( "-v", argv[i] ) )
            verbose = true;
    if ( !in_name.size() || !out_name.size() )
        cerr << "input and output file are required, nothing to do!" << endl;
        usage_msg( argv[0] );
        exit( HELP_ERROR );
    if ( encode )
        cerr << "running in encoder mode" << endl;
        encoder( in_name, out_name, verbose );
        cerr << "running in decoder mode" << endl;
        decoder( in_name, out_name, verbose );
    cerr << "done .... " << endl;
    return 0;
Provide feedback

Saved searches

Use saved searches to filter your results more quickly

FilesExpand file tree

HuffmanVC2.cpp

Latest commit

History

HuffmanVC2.cpp

File metadata and controls
