Project: Huffman Compression

In this project, you will implement a Huffman tree like figure 12.12 in page 479 using the input characters and their frequencies in figure 12.5 (page 476).

Please read the following instruction carefully and follow it closely.

1) Print your Huffman tree in the following format: (50 points)

58

- 33

- - 18

. . . and so on

- - 15 : e

- 25

. . . and so on

where for the internal nodes just print weight, but for the leaves print weight : value. Print a sequence of "bar followed by one space" before each node according to their levels.

Hint: pre-order traversal

2) Encode "tea" and print the encoded bits. (15 points)

3) Decode the bits and print the decoded string. (15 points)

You can refer to the textbook for some code but I suggest you write by yourself from scratch to greatly simplify, just finishing the above tasks only. Make it as concise as possible. For example, you may design a skeleton like this

class HuffNode

class HuffTree ( int freq[] = {10, 15, ...}; int code[] = {a, e, ...}; getCode(), getChar(); createTree(); main(); ...) No need for <AnyType> or file operations etc.

As usual, submit only one file named "YOUR_USERNAME_prj.java". For example, Lixin Fu's file would be l_fu_prj.java. To test on Linux, you can ftp the file there (WinSCP, hostname: linux.uncg.edu) then telnet to the Linux machine (by double click "PuTTY", fill in "linux.uncg.edu, then type username/passwd in the black window). In the command line type "javac l_fu_prj.java" and "java l_fu_prj" (for Lixin Fu). Any submission that does not pass compile or cannot run will lose 20 points immediately.

Proper commenting contributes 20 points. The header comment lines: (you fill out contents)

/***************************************************

Project name: huffman tree

Filename:

Student Name:

Date:

Tasks

1.

2.

3.

Computing requirements:

Language: Java

Platform: Linux

Submission requirements:

ANYTHING ELSE YOU MAY WANT TO SAY HERE

***************************************************/