Java Reference
In-Depth Information
For example, let's encode some text composed only of the letters A through E. Suppose these letters occur
with the following frequencies: A, 12 times; B, 3 times; C, 1 time; D, 9 times; and E, 15 times. We need to
arrange these letters by their frequencies in increasing order. To do so, we associate each letter with its fre-
quency of occurrence and add these pairs to a collection, such as a sorted list or a priority queue. The result is
shown in Figure 24-12a. Now we remove the two entries having the lowest frequencies and make them leaves
in a binary tree. The parent of these leaves is a node containing the sum of the frequencies in the leaves, as
illustrated in Figure 24-12b. Since the parent contains only a frequency, the letter portion of the node is
null
,
which is shown as • in the figure. We now add the contents of the parent to our list or queue, as shown to the
right of the tree in Figure 24-12b.
When we remove the next two entries from the list, we create a new leaf containing D 9 and join it to the
existing tree with a new root containing the sum of the frequencies in its two children. The result is given in
Figure 24-12c. Note that we then place the contents of this new root in its correct order within the remaining data.
Parts
d
and
e
of the figure show the remaining steps in this process.
Figure 24-12f shows the resulting binary tree with its left links and right links labeled with 0 and 1, respec-
tively. To encode a character, you begin at a leaf and traverse the tree to its root, recording 0s and 1s in reverse
order according to the left and right branches that you take. The Huffman codes for our example are as follows:
A is 10, B is 1101, C is 1100, D is 111, and E is 0. To decode a Huffman code, you traverse the tree from its root to
a leaf by taking a left branch for each 0 encountered and a right branch for each 1 encountered.
Write a program that reads a text file of alphabetic data, creates a Huffman tree, and uses the tree to compress
the file. Your program should then take the compressed file and, using your tree, decode it.
FIGURE 24-12
The steps in creating a binary tree for Huffman coding
(b)
C 1
(c)
• 4
(a)
• 4
A 12
C 1
• 13
• 4
B 3
D 9
A 12
D 9
B 3
• 13
E 15
D 9
D 9
A 12
B 3
D 9
C 1
• 4
A 12
A 12
E 15
E 15
E 15
E 15
C 1
B 3
(d)
A 12
• 13
E 15
(e)
(f)
E 15
• 25
• 25
• 40
• 40
• 25
1
0
E 15
• 13
• 25
E 15
• 25
A 12
E 15
1
0
• 13
• 13
D 9
A 12
A 12
• 4
1
0
D 9
B 3
D 9
• 4
C 1
• 4
1
0
B 3
C 1
B 3
C 1
