Section 6.4 Huffman Codes
541
at what the character might be and then backtrack if our guess proves wrong.
This ability to decode uniquely without false starts and backtracking comes about
because the code is an example of a prefix code. In a prefix code, the code for any
character is never the prefix of the code for any other character. (A prefix code is
therefore an “antiprefix” code!)
ExamplE 38
Consider the code
Character
a
b
c
Encoding scheme 01
101
011
which is not a prefix code. Given the string 01101, it could represent either ab
(01–101) or ca (011–01). Furthermore, in processing the string 011011 digit by
digit as a computer would do, the decoding could begin with ab (01–101) and only
encounter a mismatch at the last digit. Then the process would have to go all the
way back to the first digit in order to recognize cc (011–011).
As an aside, Morse code is a variable-length code. Morse’s encoding scheme
for telegraphic communication, invented in 1838, uses strings of dots and dashes
to represent letters of the alphabet. The most frequently occurring letter of the
alphabet in English text is the letter “e,” which is assigned the shortest code, a
single dot. The Morse code for
“hello world”
is
“.... . .-.. .-.. --- .-- --- .-. .-.. -..”
Here you can see that “e” is a single dot, that “l” is dot-dash-dot-dot, and that “r”
is dot-dash-dot. Morse code is not a prefix code, however; note that the “r” code is
the first part of the “l” code. To avoid this kind of ambiguity, Morse code inserts
a pause between the code for each letter. To decode, you wait for the pause and at
that point you have the code for exactly one letter.
In our approach to prefix codes, we will build binary trees with the characters
as leaves. Once the tree is built, a binary code can be assigned to each character
by simply tracing the path from the root to that leaf, using 0 for a left branch and 1
for a right branch. Because no leaf precedes any other leaf on some path from the
root, the code will be a prefix code. The binary tree for the code of Example 37 is
shown in Figure 6.57.
?
g
a
p
c
k
Figure 6.57
541
at what the character might be and then backtrack if our guess proves wrong.
This ability to decode uniquely without false starts and backtracking comes about
because the code is an example of a prefix code. In a prefix code, the code for any
character is never the prefix of the code for any other character. (A prefix code is
therefore an “antiprefix” code!)
ExamplE 38
Consider the code
Character
a
b
c
Encoding scheme 01
101
011
which is not a prefix code. Given the string 01101, it could represent either ab
(01–101) or ca (011–01). Furthermore, in processing the string 011011 digit by
digit as a computer would do, the decoding could begin with ab (01–101) and only
encounter a mismatch at the last digit. Then the process would have to go all the
way back to the first digit in order to recognize cc (011–011).
As an aside, Morse code is a variable-length code. Morse’s encoding scheme
for telegraphic communication, invented in 1838, uses strings of dots and dashes
to represent letters of the alphabet. The most frequently occurring letter of the
alphabet in English text is the letter “e,” which is assigned the shortest code, a
single dot. The Morse code for
“hello world”
is
“.... . .-.. .-.. --- .-- --- .-. .-.. -..”
Here you can see that “e” is a single dot, that “l” is dot-dash-dot-dot, and that “r”
is dot-dash-dot. Morse code is not a prefix code, however; note that the “r” code is
the first part of the “l” code. To avoid this kind of ambiguity, Morse code inserts
a pause between the code for each letter. To decode, you wait for the pause and at
that point you have the code for exactly one letter.
In our approach to prefix codes, we will build binary trees with the characters
as leaves. Once the tree is built, a binary code can be assigned to each character
by simply tracing the path from the root to that leaf, using 0 for a left branch and 1
for a right branch. Because no leaf precedes any other leaf on some path from the
root, the code will be a prefix code. The binary tree for the code of Example 37 is
shown in Figure 6.57.
?
g
a
p
c
k
Figure 6.57