540
Graphs and Trees
Practice 28 Using the variable-length code of Example 37, decode each of the following strings:
a. 11111111010100
b. 1101010101100
c. 100110001101100
■
it may be worthwhile to invest some extra effort in the encoding process if the
amount of storage space required for the file could be reduced.
Rather than using a fixed number of bits per character, an encoding scheme could
use a variable number of bits and store frequently occurring characters as sequences
with fewer bits. To store all the distinct characters, some sequences will still have to be
long, but if the longer sequences are used for characters that occur less frequently, the
overall storage required should be reduced. This approach requires knowledge of the
particular file contents, which is why it is best suited for a file whose contents will not
be frequently changed. We will study such a data compression or data compaction
scheme here, because it is best described as a series of actions taken on binary trees.
ExamplE 37
As a trivial example, suppose that a collection of data contains 50,000 instances
of the six characters a, c, g, k, p, and ?, which occur with the following percent
frequencies:
Character
a
c
g
k
p
?
Frequency
48
9
12
4
17
10
Because six distinct characters must be stored, the fixed-length scheme would
require at a minimum three bits for each character (2
3
= 8 ≥ 6). The total storage
required would then be 50,000 * 3 = 150,000 bits. Suppose instead that the following encoding scheme is used:
Character
a
c
g
k
p
?
Encoding scheme 0
1101
101
1100 1l1
100
Then the storage requirement (number of bits) is
50,000 (0.48 * 1 + 0.09 * 4 + 0.12 * 3 + 0.04 * 4 + 0.17 * 3 + 0.10 * 3) = 108,500
which is roughly two-thirds of the previous requirement.
In the fixed-length storage scheme with n bits for each character, the long
string of bits within the encoded file can be broken up into the code for successive
characters by simply looking at n bits at a time. This makes it easy to decode the
file. In the variable-length code, there must be a way to tell when the sequence for
one character ends and the sequence for another character begins.
In Practice 28 the strings can be broken into the representation of characters
in only one way. As each new digit is considered, the possibilities are narrowed
as to which character is being represented until the character is uniquely identified by the end of that character’s representation. There is never any need to guess
Graphs and Trees
Practice 28 Using the variable-length code of Example 37, decode each of the following strings:
a. 11111111010100
b. 1101010101100
c. 100110001101100
■
it may be worthwhile to invest some extra effort in the encoding process if the
amount of storage space required for the file could be reduced.
Rather than using a fixed number of bits per character, an encoding scheme could
use a variable number of bits and store frequently occurring characters as sequences
with fewer bits. To store all the distinct characters, some sequences will still have to be
long, but if the longer sequences are used for characters that occur less frequently, the
overall storage required should be reduced. This approach requires knowledge of the
particular file contents, which is why it is best suited for a file whose contents will not
be frequently changed. We will study such a data compression or data compaction
scheme here, because it is best described as a series of actions taken on binary trees.
ExamplE 37
As a trivial example, suppose that a collection of data contains 50,000 instances
of the six characters a, c, g, k, p, and ?, which occur with the following percent
frequencies:
Character
a
c
g
k
p
?
Frequency
48
9
12
4
17
10
Because six distinct characters must be stored, the fixed-length scheme would
require at a minimum three bits for each character (2
3
= 8 ≥ 6). The total storage
required would then be 50,000 * 3 = 150,000 bits. Suppose instead that the following encoding scheme is used:
Character
a
c
g
k
p
?
Encoding scheme 0
1101
101
1100 1l1
100
Then the storage requirement (number of bits) is
50,000 (0.48 * 1 + 0.09 * 4 + 0.12 * 3 + 0.04 * 4 + 0.17 * 3 + 0.10 * 3) = 108,500
which is roughly two-thirds of the previous requirement.
In the fixed-length storage scheme with n bits for each character, the long
string of bits within the encoded file can be broken up into the code for successive
characters by simply looking at n bits at a time. This makes it easy to decode the
file. In the variable-length code, there must be a way to tell when the sequence for
one character ends and the sequence for another character begins.
In Practice 28 the strings can be broken into the representation of characters
in only one way. As each new digit is considered, the possibilities are narrowed
as to which character is being represented until the character is uniquely identified by the end of that character’s representation. There is never any need to guess