544
Graphs and Trees
Table 6.1 shows the steps in Huffman encoding/decoding for data compression.
praCTiCe 30 Find the Huffman codes for the characters of Practice 29.
■
praCTiCe 29 Construct the Huffman tree for the following characters and frequencies:
Character
w
q
h
e
Frequency
10
12
20
58
■
table 6.1
Encoding Step 1
On the original CLEARTEXT file, perform a frequency analysis; that is, create a file
FREQUENCY that contains data of the form
a—18
b—7
and so forth.
Encoding Step 2
Using FREQUENCY, create a file CODETABLE that contains the Huffman code for each
character, i.e.,
a—001
b—1110
and so forth.
Encoding Step 3
Using CLEARTEXT and CODETABLE, create a file called CODED that contains the
compressed data.
Decoding
Using CODED and CODETABLE, decode the data to recover CLEARTEXT.
The CODED file is the data-compressed version of CLEARTEXT, and presumably it requires less storage space. However, the CODETABLE file must also be
stored in order to be able to decode the file.
Justification
Although the algorithm to construct the Huffman tree T is easy enough to describe,
we must justify that it gives us the minimum possible value for E(T).
First, if we have an optimal tree T for m characters, the nodes with the lowest frequencies can always be assumed to be the left and right children of some
node. To prove this assumption, label the two nodes with the lowest frequencies
x and y. If x and y are not siblings in the tree, then find two siblings p and q at
the lowest level of the tree, and consider the case where x and y are not at that
level (Figure 6.58a). Because f(x) is one of the two smallest values, we know that
f(x) ≤ f( p). If f(x) < f( p), then interchanging x and p in the tree would result in a
new tree T′ with E(T′) < E(T ) (Figure 6.58b: the larger frequency is now at a lesser depth—see Exercise 20a), but this would contradict the fact that T was optimal.
Therefore f(x) = f( p), and x and p can be interchanged in the tree with no effect
on E(T). Similarly, y and q can be interchanged, resulting in Figure 6.58c, in which
x and y are siblings. If x or y are at the same level as p and q to begin with, they can
certainly be interchanged with p or q without affecting E(T ) (Figure 6.58d).
Graphs and Trees
Table 6.1 shows the steps in Huffman encoding/decoding for data compression.
praCTiCe 30 Find the Huffman codes for the characters of Practice 29.
■
praCTiCe 29 Construct the Huffman tree for the following characters and frequencies:
Character
w
q
h
e
Frequency
10
12
20
58
■
table 6.1
Encoding Step 1
On the original CLEARTEXT file, perform a frequency analysis; that is, create a file
FREQUENCY that contains data of the form
a—18
b—7
and so forth.
Encoding Step 2
Using FREQUENCY, create a file CODETABLE that contains the Huffman code for each
character, i.e.,
a—001
b—1110
and so forth.
Encoding Step 3
Using CLEARTEXT and CODETABLE, create a file called CODED that contains the
compressed data.
Decoding
Using CODED and CODETABLE, decode the data to recover CLEARTEXT.
The CODED file is the data-compressed version of CLEARTEXT, and presumably it requires less storage space. However, the CODETABLE file must also be
stored in order to be able to decode the file.
Justification
Although the algorithm to construct the Huffman tree T is easy enough to describe,
we must justify that it gives us the minimum possible value for E(T).
First, if we have an optimal tree T for m characters, the nodes with the lowest frequencies can always be assumed to be the left and right children of some
node. To prove this assumption, label the two nodes with the lowest frequencies
x and y. If x and y are not siblings in the tree, then find two siblings p and q at
the lowest level of the tree, and consider the case where x and y are not at that
level (Figure 6.58a). Because f(x) is one of the two smallest values, we know that
f(x) ≤ f( p). If f(x) < f( p), then interchanging x and p in the tree would result in a
new tree T′ with E(T′) < E(T ) (Figure 6.58b: the larger frequency is now at a lesser depth—see Exercise 20a), but this would contradict the fact that T was optimal.
Therefore f(x) = f( p), and x and p can be interchanged in the tree with no effect
on E(T). Similarly, y and q can be interchanged, resulting in Figure 6.58c, in which
x and y are siblings. If x or y are at the same level as p and q to begin with, they can
certainly be interchanged with p or q without affecting E(T ) (Figure 6.58d).