Section 6.4 Huffman Codes
549
8. Write the Huffman codes for r, s, t, u in the binary tree shown.
r
s
t
u
9. a. Construct the Huffman tree for the following characters and frequencies.
Character
c
d
g
m
r
z
Frequency
28
25
6
20
3
18
b. Find the Huffman codes for these characters.
10. a. Construct the Huffman tree for the following characters and frequencies.
Character
b
n
p
s
w
Frequency
6
32
21
14
27
b. Find the Huffman codes for these characters.
11. a. Construct the Huffman tree for the following characters and frequencies.
Character
a
z
t
e
c
Frequency
27
12
15
31
15
b. Find the Huffman codes for these characters.
12. a. Construct the Huffman tree for the following characters and frequencies.
Character
?
x
w
e
t
s
a
Frequency
14
3
11
27
18 22
5
b. Find the Huffman codes for these characters.
c. A file consisting of 100,000 instances of these seven characters is stored using a fixed-length binary
encoding scheme. How many bits are required for each code and what is the total number of bits
needed?
d. Storing the same file using the Huffman code of part (b), how many bits are needed?
In Exercises 13–14, the integers could represent the results of the “quantization” step in a JPEG image compression, and the number of occurrences of each in the image. (Note that these are instances of occurrence
rather than percent frequencies; this simply means that the Huffman tree will not end up with the root value
equal to 100.)
13. Construct the Huffman tree and find the Huffman codes for the following integers and occurrences.
Integer
82
664
327 349 423 389
Occurrences 416 97
212 509 446 74
14. Construct the Huffman tree and find the Huffman codes for the following integers and occurrences.
Integer
190 205
514 333 127 901
277
Occurrences 52
723
129 233 451 820
85