handout #27
CSE143—Computer Programming II
Programming Assignment #8
due: Wednesday,
This
assignment is worth a total of 30 points. This document explains part 1 of the
assignment, which is worth approximately half of the 30 points. Part 2 will be
available on Wednesday, 5/25.
This
program will give you practice with binary trees and priority queues. In this program you will explore how text
files can be compressed by using a coding scheme based on the frequency of
characters. We will use a coding scheme
called Huffman coding.
The
basic idea is to abandon the way that text files are usually stored. Instead of using the usual seven or eight
bits per character, Huffman's method uses only a few bits for characters that
are used often, more bits for those that are rarely used.
You
will solve this problem using a structure known as a priority queue. In a priority queue each value inserted into
the queue has a priority that determines when it will be removed. There are many ways to specify the
priorities. For this program you will
construct objects that implement the Comparable interface, with objects that
are “less” being given a higher priority (to be removed first).
The
first step is to compute the frequency of each character in the file you wish
to encode. This allows you to determine
which characters should have the fewest bits, etc. The next step is to build a “coding tree”
from the bottom up according to the frequencies. An example will probably make this the most
clear. To make the example easier, suppose we only want to
encode the five letters (a, b, c, d, e) and they have frequencies 3, 3, 1, 1,
and 2, respectively.
We
first create a leaf node for each character/frequency pair and put them into a
priority queue, so that the characters with lower frequencies appear first:
+----+ +----+ +----+
+----+ +----+
| 1 |
| 1 | | 2 | | 3
| |
3 |
+----+ +----+ +----+ +----+
+----+
'c' 'd' 'e' 'a'
'b'
Now
we pick the two nodes with the smallest frequencies (the two at the front of
the priority queue) and create a new node with those two nodes as children (the
first value from the queue becomes the left, the second value from the queue
becomes the right). We assign this new
branch node a frequency that is the sum of the frequencies of the two
children. This new node is then put back
into the priority queue:
+----+ +----+ +----+
+----+
| 2 |
| 2 | | 3 | | 3
|
+----+ +----+ +----+ +----+
'e' /
\ 'a' 'b'
+----+ +----+
| 1 | | 1 |
+----+ +----+
'c' 'd'
Continuing
in this way, we build up larger and larger subtrees.
Here are the rest of the steps:
+----+ +----+ +----+
| 3 |
|
3 | | 4 |
+----+ +----+ +----+
'a' 'b' /
\
+----+ +----+
| 2 | | 2 |
+----+ +----+
'e' / \
+----+ +----+
| 1 | | 1 |
+----+ +----+
'c'
'd'
+----+ +----+
| 4
| | 6 |
+----+ +----+
/
\ /
\
+----+ +----+
+----+ +----+
| 2 | | 2 | | 3 | | 3 |
+----+ +----+
+----+
+----+
'e' / \
'a' 'b'
+----+ +----+
| 1 | | 1 |
+----+ +----+
'c' 'd'
+----+
| 10 |
+----+
/ \
/ \
+----+ +----+
| 4 | |
6 |
+----+ +----+
/
\ /
\
+----+ +----+ +----+ +----+
| 2 |
| 2 | | 3
| | 3 |
+----+ +----+ +----+
+----+
'e' / \ 'a'
'b'
+----+ +----+
| 1 | | 1 |
+----+ +----+
'c' 'd'
Note
that the nodes with low frequencies end up far down in the tree, and nodes with
high frequencies end up near the root of the tree. It turns out that this structural description
is exactly what is needed to create an efficient encoding. The Huffman code is derived from this coding
tree simply by assigning a zero to each left branch and a one to each right
branch. The code can be read directly
from the tree. The code for a is 10, the
code for b is 11, the code for c is 010, the code for d is 011 and the code for
e is 00.
An
interesting feature of the Huffman code is that delimiters between characters
are not stored, even though different characters may be coded with different
numbers of bits. The key is that a code
created by this method exhibits what is known as the prefix property, which means that no code for a character is the
prefix of the code of any other character. Thus, to decode a message we need
only traverse our tree. When we reach a
leaf, we know that we have decoded one character, and can now start decoding the
next character.
For
our purposes, we will encode what are known as “bytes” (8 bits). This will allow us to encode standard text
files that use ASCII and binary files as well. From the point of view of your
Huffman code, you can think about the individual bytes as simple integers in
the range of 0 to 255, each representing the ASCII value of a particular
character. In part 1, you are working with a program called MakeCode. It prompts the user for a file to examine and
it computes the frequency of each character in the file. These counts are passed as an array to your
HuffmanTree constructor.
The
array passed to your constructor will have exactly 256 values in it, but your
program should not depend on this. Instead, you can use the length field of the
array to know how many there are. In
your constructor, you should use a priority queue to build up the tree as
described above. First you will add a
leaf node for each character that has a frequency greater than 0 (we don’t
include the other characters in our tree).
These should be added in increasing character order (character 0,
character 1, and so on).
Then
you build the tree. Initially you have a
bunch of leaf nodes. Your goal is to get
a single tree. While you haven’t gotten
down to a single tree, you remove two values from the priority queue and
combine them to make a new branch node which you put back into the queue, as
described above. You continue combining
subtrees until you get down to one tree.
This becomes your Huffman tree.
You are to define a
class called HuffmanTree with the following public methods (more methods will
be added in part 2 of this assignment):
|
Method |
Description |
|
HuffmanTree(int[] count) |
Constructs a Huffman tree using the given array of frequencies where count[i] is the number of occurrences of the character with ASCII value i. |
|
void write(PrintStream output) |
Writes the current tree to the given output stream in standard format. |
In
defining your class, you will also define a node class called HuffmanNode. You may decide what data fields to include
with this class.
In
writing the tree, you should produce two lines of output for each
character. The first line should have
the ASCII value of the character. The
second line should have the code (0's and 1's) for the character with this
ASCII value. For the simple example
above, the output would be (the letter a has ASCII value 97):
101
00
99
010
100
011
97
10
98
11
The
codes should be written in “traversal order.” In other words, they should be
written in the order that any standard traversal of the tree would visit them.
It
turns out that Huffman coding works best if one character is designated as “end
of file,” meaning that every file is guaranteed to end with such a character
and it will be used for no other purpose. Some operating systems have such a
character, but if we want to write a general-purpose program, we have to do
something that is not specific to any one operating system. So in addition to encoding the actual
characters that appear in the file, we will create a code for a fictitious
end-of-file character that will be used only by the Huffman encoding and
decoding programs. That means that in
addition to all of the legal characters, you are also going to introduce a
special character that will be used to signal end-of-file. We will refer to this as the “pseudo-eof”
character. Its value will be one higher
than the value of the highest character in the frequency array passed to the
constructor. It will always have a frequency of 1 because it appears exactly
once at the end of each file to be encoded.
You will have to manually add this character to your priority queue
because it will not be included as part of the frequency array.
You
will be provided with a class called PriorityQueue that you should use to build
your Huffman Tree. As with the LinkedQueue class that we saw earlier in the
quarter, the PriorityQueue class implements the Queue interface. The only difference between it and a standard
Queue is that it uses the natural ordering of the objects to decide which
object to dequeue first, with objects considered “less” returned first. You are going to be putting subtrees into
your priority queue, which means you’ll be adding values of type HuffmanNode. This means that your HuffmanNode class will
have to implement the Comparable interface.
It should use the frequency of the subtree to determine its ordering
relative to other subtrees, with lower frequencies considered “less” than
higher frequencies.
You are being given two data files for this assignment called short.txt and hamlet.txt. The file short.txt is a short input file suitable for preliminary testing. The file hamlet.txt contains the full text of Shakespeare’s play Hamlet.
In terms of correctness, your class must provide
all of the functionality described above. In terms of style, we will be grading
on your use of comments, good variable names, consistent indentation and good
coding style to implement these operations.
Remember that you will lose points if you declare variables as data
fields that can instead be declared as local variables. You should also avoid extraneous cases (e.g.,
don’t make something into a special case if it doesn’t have to be).
You should name your files HuffmanNode.java and HuffmanTree.java and you should turn it in electronically from the “assignments” link on the class web page. A collection of files needed for the assignment is included on the web page as ass8.zip. You will need to have MakeCode.java, Queue.java, PriorityQueue.java, and Scanner.java in the same directory as your files in order to run MakeCode. The zip file will also include the sample data files (short.txt and hamlet.txt) along with their code files (short.code and hamlet.code).
If you would like to read more about Huffman’s algorithm, there are many sources on the web including, for example, http://www.maths.abdn.ac.uk/~igc/tch/mx4002/notes/node59.html.