nen.h

Huffman compression by Visual C++2008

#include <string.h>
#include "fstream.h"
#include <stdlib.h>
#include <conio.h>

#define NUM_CHAR 256
#define NUM_BIT 8
struct treenode {

	unsigned int freq;
	unsigned char ch;
	treenode *left;
	treenode *right;

};
struct PQ {

	int heap_size;
	treenode *A[NUM_CHAR];
};

struct bit_buffer{
	char content[NUM_BIT];
	int post;
};
int parent (int i)
{
	return (i-1) / 2;
}

int left_child(int i)
{
	return i*2 + 1;
}

int right_child(int i)
{
	return i*2 + 2;
}

void create_pq(PQ *p)
{
	p->heap_size = 0;
}

class Compress {
protected:
	unsigned int freq[NUM_CHAR];
	unsigned char ch;
	int nbits;
	int current_byte;

public:
	Compress();
	unsigned int get_frequencies (char *NameFileIn);
	void heapify (PQ *p, int i);
	void insert_pq (PQ *p, treenode *r);
	treenode *extract_min_pq (PQ *p);
	treenode *build_huffman ();
	void traverse (treenode *r,int level,char code_so_far[],char *codes[ ]);
	void bitout(fstream &FileOut, char bit);
	void encode_file(char *NameFileIn, char *NameFileOut, char *codes[ ]);
};


Compress::Compress()
{
	for(int i=0;i<NUM_CHAR;++i)
		freq[i] = 0;
}

unsigned int Compress::get_frequencies(char *NameFileIn)
{
	unsigned int n;
	fstream	FileIn(NameFileIn,ios::in|ios::binary);

	for (n=0;;n++)
	{
		FileIn.get(ch);	
		if (FileIn.eof())
			break;

		freq[ch]++;
	}
	FileIn.close();
	return n;
}
void Compress::heapify(PQ *p, int i)
{
	int l, r, smallest;
	treenode *t;

	l = left_child (i);
	r = right_child (i);
	if (l < p->heap_size && p->A[l]->freq < p->A[i]->freq)
		smallest = l;
	else
		smallest = i;
	if (r < p->heap_size && p->A[r]->freq < p->A[smallest]->freq)
		smallest = r;

	if (smallest != i) 
	{
		t = p->A[i];
		p->A[i] = p->A[smallest];
		p->A[smallest] = t;
		this->heapify (p, smallest);
	}
}
void Compress::insert_pq(PQ *p, treenode *r)
{
	int i;

	p->heap_size++;
	i = p->heap_size - 1;

	while ((i > 0) && (p->A[parent(i)]->freq > r->freq)) 
	{
		p->A[i] = p->A[parent(i)];
		i = parent (i);
	}
	p->A[i] = r;
}

treenode* Compress::extract_min_pq(PQ *p)
{
	treenode *r;
	if (p->heap_size == 0) 
	{
		exit (1);
	}
	r = p->A[0];
	p->A[0] = p->A[p->heap_size-1];
	p->heap_size--;
	this->heapify (p, 0);
	return r;
}

treenode* Compress::build_huffman()
{
	int i, n;
	treenode *x, *y, *z;
	PQ p;

	create_pq (&p);

	for (i=0; i< NUM_CHAR; i++) 
	{
		x = (treenode*)malloc (sizeof (treenode));
		x->left = NULL;
		x->right = NULL;
		x->freq = freq[i];
		x->ch = (char) i;
		this->insert_pq (&p, x);
	}
	n = p.heap_size-1;
	for (i=0; i< n; i++) 
	{
		z = (treenode*)malloc (sizeof (treenode));
		x = this->extract_min_pq (&p);
		y = this->extract_min_pq (&p);
		z->left = x;
		z->right = y;
		z->freq = x->freq + y->freq;
		this->insert_pq (&p, z);
	}

	return this->extract_min_pq (&p);
}

void Compress::traverse(treenode *r,int level,char code_so_far[],char *codes[ ])
{
	if ((r->left == NULL) && (r->right == NULL)) 
	{
		code_so_far[level] = 0;

		codes[r->ch] = strdup (code_so_far);
	} 
	else 
	{
		code_so_far[level] = '0';
		this->traverse (r->left, level+1, code_so_far, codes);

		code_so_far[level] = '1';
		this->traverse (r->right, level+1, code_so_far, codes);
	}
}

void Compress::bitout(fstream &FileOut, char bit)
{
	current_byte <<= 1;


	if (bit == '1')
		current_byte |= 1;
	nbits++;

	if (nbits == NUM_BIT)
	{
		FileOut.put ((unsigned char)current_byte);
		nbits = 0;
		current_byte = 0;
	}
}


void Compress::encode_file(char *NameFileIn, char *NameFileOut, char *codes[ ])
{
	int i;
	int n = 0;
	char *s;
	current_byte =0;
	nbits = 0;
	for(int i=0;i<NUM_CHAR;++i)
		if(freq[i])
			++n;  // So ky tu co trong File
	fstream FileIn(NameFileIn,ios::in|ios::binary);
	fstream FileOut(NameFileOut,ios::out|ios::binary);
	FileOut.write((char*)(&n),sizeof(n));
	for(i=0;i<NUM_CHAR;++i)
		if(freq[i])
		{
			FileOut.put(unsigned char(i));
			FileOut.write((char *)(&freq[i]),sizeof(int));
		}
		for(;;)
		{
			FileIn.get(ch);
			if(FileIn.eof())
				break;
			for (s=codes[ch]; *s; s++)
				this->bitout (FileOut, *s);
		}
		n = nbits;
		while(nbits)
			this->bitout(FileOut,'0');
		FileOut.put(char(n));
		FileIn.close();
		FileOut.close();
}