You are to write a program that reads a plain text file, computes a Huffman code tree

for that text file, and writes out the encoded version of the text.

Your program should read the text from the file given as a command

-line

argument.

You should compute the number of occurrences of each character in the file,

and each character (and its frequency) should be placed in a new tree node.

You should build a min-

heap containing these nodes.

Build the Huffman Code Tree using the heap. As you create new internal

nodes, give them a unique character

label

, using extended ASCII characters,

starting with character 128

.

Write the pre-

order traversal

of the Huffman code tree to the file

preorder.txt

and the i

n-order traversal to the file

inorder

.txt. Write the

ASCII value for each node in the traversal. The internal nodes will have ASCII

values greater than 127 and the leaves will have values less than 128.

Write

unsigned char values using the put(int) method.

Construct a table containing the encoding for each character, storing the

encoding as a string.

Encode the original text, writing the encoded version to code.txt. This file

should be ASCII 0 and 1 characters (much easier to debug)

(5 bonus points) also create a true binary version of the encoded text, writing

it to code.bin. In the binary file, use the first two bytes to indicate the

number of characters in the text. If the last character does not

finish a byte

the

n pad the last byte with 0s.

Requirements:

You should build all the data structures that you use yourself. You must

create a binary h

eap data structure that uses an array and implements

insert and extract-

min that run in O(lg N) time.

Your makefile sh

ould build the executable named encode.

Zip all of your source code and makefile into a single .zip file for

submission.

You must use good object based organization, i.e. use classes in an

appropriate way.

Example

Suppose that the file foo.txt contains the following text:

ALLALABAMAFOOTBALL

Then executing:

encode foo.txt

should produce output

files such as the following

. Note that this is only an example

of a correct output. The tree and codes produced by your program would likely be

different.

preorder.txt contains

the bytes

:

133 132 076 065 131 130 066 079 129 128 084 070 077

inorder.

txt contains the bytes:

076 132 065 133

066 130 079 131 084 128 070 129 077

code.txt contains:

010000010001100011110111011011011100100010000

read.cpp

#include #include using namespace std; int main(int argc, char *argv[]){ unsigned char ch; ifstream in(argv[1],ios::in|ios::binary|ios::ate); size_t size = 0; // here size = in.tellg() ; // get the length of the file cout << "Size of file: " << size << endl; in.seekg(0, ios::beg); // set the pointer to the beginning for (int i =0; i

decode.cpp

#include #include using namespace std; struct treenode { unsigned char data; treenode *left, *right; };

int strchr(unsigned char s[], unsigned char c) { int i=0; while(s[i]!=c) i++; return i; }

treenode * treebuild(unsigned char pre[], unsigned char in[], int & pos, int size) { if (size==pos) return NULL; treenode *t = new treenode; t->data = pre[pos]; t->left = NULL; t->right = NULL; int loc = strchr(in, pre[pos++]); in[loc] = 0; if (loc > 0 && in[loc-1] != 0) t->left = treebuild(pre, in, pos, size); if (loc < size-1 && in[loc+1] != 0) t->right = treebuild(pre,in,pos, size); return t; }

void parse(string c, treenode *t) { treenode *p = t; for(int pos=0; pos < c.length(); pos++) { p = c[pos]=='0' ? p->left : p->right; if (p->left == NULL) { cout << p->data; p = t; } } }

int main(int argc, char* argv[]) { ifstream prefile(argv[1],ios::in|ios::binary|ios::ate), infile(argv[2],ios::in|ios::binary), codefile(argv[3]); size_t size = 0; // here size = prefile.tellg() ; // get the length of the file prefile.seekg(0, ios::beg); // set the pointer to the beginning unsigned char *pre = new unsigned char[size], *in = new unsigned char[size]; for (int i =0; i

decodebin.cpp

#include #include using namespace std; struct treenode { unsigned char data; treenode *left, *right; };

int strchr(unsigned char s[], unsigned char c) { int i=0; while(s[i]!=c) i++; return i; }

treenode * treebuild(unsigned char pre[], unsigned char in[], int & pos, int size) { if (size==pos) return NULL; treenode *t = new treenode; t->data = pre[pos]; t->left = NULL; t->right = NULL; int loc = strchr(in, pre[pos++]); in[loc] = 0; if (loc > 0 && in[loc-1] != 0) t->left = treebuild(pre, in, pos, size); if (loc < size-1 && in[loc+1] != 0) t->right = treebuild(pre,in,pos, size); return t; }

void parse(string c, treenode *t,short count) { treenode *p = t; for(int pos=0; pos < c.length(); pos++) { p = c[pos]=='0' ? p->left : p->right; if (p->left == NULL) { cout << p->data; p = t; if(--count == 0) return; } } }

int main(int argc, char* argv[]) { ifstream prefile(argv[1],ios::in|ios::binary|ios::ate), infile(argv[2],ios::in|ios::binary), codefile(argv[3],ios::in|ios::binary|ios::ate); size_t size = 0; // here size = prefile.tellg() ; // get the length of the file prefile.seekg(0, ios::beg); // set the pointer to the beginning unsigned char *pre = new unsigned char[size], *in = new unsigned char[size]; for (int i =0; i(&count),2); for (int i=0; i>=1; } } parse(code,tree,count); cout << endl; }