550
Graphs and Trees
15. JPEG can achieve various compression levels; the higher the compression, the lower the quality of the
reconstructed image.
a. A compression ratio of 10:1 results in virtually imperceptible loss of image quality. A file of 850,000
bytes that is compressed with a 10:1 compression ratio results in a compressed file of what size?
b. At a compression ratio of 25:1, some degradation is visible in the reconstructed image. A file of 850,000
bytes that is compressed with a 25:1 compression ratio results in a compressed file of what size?
16. Explain why JPEG encoding results in less compression for gray-scale images than for full-color images.
17. Someone does a global substitution on the text file of Exercise 11, replacing all instances of “z” with “sh.”
Find the new Huffman codes.
18. Consider the following paragraph.
However, in my thoughts I could not sufficiently wonder at the intrepidity of these diminutive mortals
who durst venture to mount and walk upon my body, while one of my hands was at liberty, without
trembling at the very sight of so prodigious a creature as I must appear to them.
3
If this paragraph were to be compressed using a Huffman code, what single character, aside from punctuation or uppercase characters, would be apt to have one of the longest codes? Which would have one of the
shortest?
19. Recall the problem posed at the beginning of this chapter.
You work in the Information Systems Department at World Wide Widgets (WWW), the leading widget
manufacturer. Part numbers consist of a leading character B, C, G, R, or S to identify the part type, followed by an 8-digit number. Thus
C00347289
B11872432
S45003781
are all legitimate part numbers. WWW maintains a data file of the part numbers it uses, which, as it
turns out, is most of the potential numbers.
How can you compress this data file so it takes less storage space than the approximately 4.5 Gb required
using the ASCII encoding scheme of eight bits per character?
a. Running a frequency count on the WWW data file reveals the following information:
Character
B
C
G R
S
0
1
2
3
4
5
6
7
8
9
Frequency
2
5
1
2
1
18 13 7
12 9
6
11
7
2
4
Construct a Huffman code for these characters.
b. Compute the space requirements of the compressed file as a percent of the uncompressed file.
20. In the justification that the Huffman algorithm produces an optimal tree, the following two assertions were
made. Prove that each is true.
a. E(T ′) < E(T)
b. E(B′) = E(B) + f (x) + f ( y)
3 From Gulliver’s Travels by Jonathan Swift, London, 1726.
Graphs and Trees
15. JPEG can achieve various compression levels; the higher the compression, the lower the quality of the
reconstructed image.
a. A compression ratio of 10:1 results in virtually imperceptible loss of image quality. A file of 850,000
bytes that is compressed with a 10:1 compression ratio results in a compressed file of what size?
b. At a compression ratio of 25:1, some degradation is visible in the reconstructed image. A file of 850,000
bytes that is compressed with a 25:1 compression ratio results in a compressed file of what size?
16. Explain why JPEG encoding results in less compression for gray-scale images than for full-color images.
17. Someone does a global substitution on the text file of Exercise 11, replacing all instances of “z” with “sh.”
Find the new Huffman codes.
18. Consider the following paragraph.
However, in my thoughts I could not sufficiently wonder at the intrepidity of these diminutive mortals
who durst venture to mount and walk upon my body, while one of my hands was at liberty, without
trembling at the very sight of so prodigious a creature as I must appear to them.
3
If this paragraph were to be compressed using a Huffman code, what single character, aside from punctuation or uppercase characters, would be apt to have one of the longest codes? Which would have one of the
shortest?
19. Recall the problem posed at the beginning of this chapter.
You work in the Information Systems Department at World Wide Widgets (WWW), the leading widget
manufacturer. Part numbers consist of a leading character B, C, G, R, or S to identify the part type, followed by an 8-digit number. Thus
C00347289
B11872432
S45003781
are all legitimate part numbers. WWW maintains a data file of the part numbers it uses, which, as it
turns out, is most of the potential numbers.
How can you compress this data file so it takes less storage space than the approximately 4.5 Gb required
using the ASCII encoding scheme of eight bits per character?
a. Running a frequency count on the WWW data file reveals the following information:
Character
B
C
G R
S
0
1
2
3
4
5
6
7
8
9
Frequency
2
5
1
2
1
18 13 7
12 9
6
11
7
2
4
Construct a Huffman code for these characters.
b. Compute the space requirements of the compressed file as a percent of the uncompressed file.
20. In the justification that the Huffman algorithm produces an optimal tree, the following two assertions were
made. Prove that each is true.
a. E(T ′) < E(T)
b. E(B′) = E(B) + f (x) + f ( y)
3 From Gulliver’s Travels by Jonathan Swift, London, 1726.