Huffman Coding: The Problem
Chapter Seventy-Five
Syllabus topic Module 2, "Trees: Applications of Tree like Huffman Coding"
Pages 235 to 237 of 411
In one line
A fixed-length code spends the same number of bits on a rare letter as on a common one, and a variable-length code can do better, provided no code is a prefix of another.
The problem
Store the text AAAAABBBCCD in bits.
Fixed length. Four distinct characters, so 2 bits each is enough: A = 00, B = 01, C = 10, D = 11. Eleven characters at 2 bits is 22 bits.
But A occurs five times and D once. Both cost 2 bits. That is the waste, and it is the whole opportunity.
Variable length. Give the common letters short codes and the rare ones long codes:
| Character | Count | Fixed | Variable |
|---|---|---|---|
| A | 5 | 00 | 0 |
| B | 3 | 01 | 10 |
| C | 2 | 10 | 110 |
| D | 1 | 11 | 111 |
Cost: 5 times 1, plus 3 times 2, plus 2 times 3, plus 1 times 3, which is 20 bits.
The difficulty variable length creates
Consider a different, careless assignment: A = 0, B = 1, C = 01.
Now decode 01. Is it C? Or is it A followed by B? There is no way to tell, and a code that cannot be decoded is useless however short it is.
The rule that fixes it:
No code may be a prefix of another code. Such a code is called prefix-free.
In the good table above, 0 is A's code and no other code begins with 0. 10 is B's and no other begins with 10. Decoding is then unambiguous: read bits until they match a code, which can only happen one way.
Measured on a real text
import math
from collections import Counter
text = ("the quick brown fox jumps over the lazy dog "
"the quick brown fox jumps over the lazy dog "
"data structures and algorithms data structures and algorithms")
counts = Counter(text)
distinct = len(counts)
fixed_bits_per_char = math.ceil(math.log2(distinct))
print("characters in the text :", len(text))
print("distinct characters :", distinct)
print("fixed length needs :", fixed_bits_per_char, "bits per character")
print("fixed length total :", len(text) * fixed_bits_per_char, "bits")
print()
print("the ten commonest characters and their shares:")
for character, count in counts.most_common(10):
name = "space" if character == " " else repr(character)
print(" %-7s %4d %5.1f%%" % (name, count, 100 * count / len(text)))
print()
rarest = counts.most_common()[-1]
commonest = counts.most_common(1)[0]
print("the commonest character appears %d times and the rarest %d times,"
% (commonest[1], rarest[1]))
print("and a fixed length code spends %d bits on each of them."
% fixed_bits_per_char)characters in the text : 149
distinct characters : 27
fixed length needs : 5 bits per character
fixed length total : 745 bits
the ten commonest characters and their shares:
space 25 16.8%
't' 12 8.1%
'r' 10 6.7%
'o' 10 6.7%
'a' 10 6.7%
'e' 8 5.4%
'u' 8 5.4%
's' 8 5.4%
'h' 6 4.0%
'd' 6 4.0%
the commonest character appears 25 times and the rarest 2 times,
and a fixed length code spends 5 bits on each of them.Huffman Coding: The Problem
Twenty-seven distinct characters, so a fixed code needs 5 bits each and 745 bits in all. The space character alone is nearly a sixth of the text and pays the same 5 bits as the rarest letter.
What a good code would do, in principle
If a character makes up a fraction p of the text, the theoretical best is about log2(1/p) bits for it. A character that is half the text deserves 1 bit; one that is a thousandth deserves about 10.
The average of that over the whole text is called the entropy, and it is the floor no prefix-free code can go below. Huffman's algorithm reaches that floor to within one bit per character, which is why it is the method taught.
import math
from collections import Counter
text = ("the quick brown fox jumps over the lazy dog "
"the quick brown fox jumps over the lazy dog "
"data structures and algorithms data structures and algorithms")
counts = Counter(text)
total = len(text)
distinct = len(counts)
fixed = math.ceil(math.log2(distinct))
entropy = -sum((c / total) * math.log2(c / total) for c in counts.values())
print("fixed length : %.2f bits per character" % fixed)
print("theoretical floor : %.2f bits per character (the entropy)" % entropy)
print()
print("so a perfect code would need about %d bits for this text,"
% math.ceil(entropy * total))
print("against %d for the fixed length one." % (fixed * total))
print("that is a saving of about %.0f%%."
% (100 * (1 - entropy / fixed)))
print()
print("what each character 'deserves', for the five commonest:")
for character, count in counts.most_common(5):
name = "space" if character == " " else repr(character)
share = count / total
print(" %-7s %5.1f%% of the text, deserves %.1f bits"
% (name, 100 * share, math.log2(1 / share)))fixed length : 5.00 bits per character
theoretical floor : 4.32 bits per character (the entropy)
so a perfect code would need about 644 bits for this text,
against 745 for the fixed length one.
that is a saving of about 14%.
what each character 'deserves', for the five commonest:
space 16.8% of the text, deserves 2.6 bits
't' 8.1% of the text, deserves 3.6 bits
'r' 6.7% of the text, deserves 3.9 bits
'o' 6.7% of the text, deserves 3.9 bits
'a' 6.7% of the text, deserves 3.9 bitsThe floor is 4.32 bits per character against the fixed 5, so about 14 per cent is available on this text. The space character, at 16.8 per cent of the text, deserves about 2.6 bits and is being charged 5.
Huffman Coding: The Problem
Chapter 77 measures what Huffman actually achieves against that floor.
Where the tree comes in
A prefix-free code and a binary tree are the same thing.
Put the characters at the leaves. Label every left edge 0 and every right edge 1. A character's code is the sequence of labels from the root to its leaf.
Then no code can be a prefix of another, automatically, because a character's leaf is never on the path to another character's leaf. The prefix-free property is not something to check; it is a consequence of putting the characters only at leaves.
That is why this is a tree chapter, and the next one builds the tree.
Quick revision
- A fixed-length code spends the same bits on every character, so common characters are overcharged.
- A variable-length code gives short codes to common characters, and must be prefix-free or it cannot be
decoded: A = 0, B = 1, C = 01 makes 01 ambiguous.
- Prefix-free means no code is a prefix of another.
- A character forming a fraction p of the text deserves about log2(1/p) bits; the average of that is the
entropy, which is the floor for any prefix-free code.
- Measured on a 149 character text: 27 distinct characters, 5 bits fixed, entropy 4.32, so about 14 per
cent is available.
- A prefix-free code is exactly a binary tree with the characters at the leaves and edges labelled 0 and
1; the prefix-free property is then automatic.
Test yourself
1. Why is a fixed-length code wasteful? It spends the same number of bits on a rare character as on a common one, so the common ones, which dominate the text, are overcharged.
2. What goes wrong with the code A = 0, B = 1, C = 01? The bits 01 could be C, or A followed by B. The code is not prefix-free, so it cannot be decoded unambiguously.
3. Define prefix-free. No character's code is a prefix of any other character's code.
4. How many bits does a character forming a fraction p of the text deserve, and what is the average called? About log2(1/p). The average over the whole text is the entropy, and it is the floor no prefix-free code can beat.
5. Give the measured figures for the chapter's text. 149 characters, 27 distinct, 5 bits each fixed for 745 bits, against an entropy of 4.32 bits per character, so about 14 per cent is available.
6. Why does putting characters only at the leaves make a code prefix-free automatically? Because a character's leaf is never on the path from the root to another character's leaf, so no character's code can be a prefix of another's.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.