Huffman Coding
Learn Huffman Coding for GCSE Computer Science with this free worksheet and full mark scheme — Foundation and Higher exam-style questions with worked answers. Huffman coding compresses data by giving the most frequent characters the shortest binary codes.
Free downloads
These worksheets and mark schemes are original, written for Virtus Academy and checked against the current AQA specification. Every worksheet comes with a full mark scheme.
Topic overview
Huffman coding is a lossless compression method that gives frequently occurring characters shorter binary codes than rare ones.
A fixed-length encoding such as ASCII uses the same number of bits for every character, which wastes space when some characters appear far more often than others. Huffman assigns short codes to common characters and longer codes to rare ones, so the total is smaller.
The codes are read from a Huffman tree, following branches from the root and recording 0 for left and 1 for right until a character is reached. Because no code is a prefix of another, the stream can be decoded unambiguously without separators — which is what makes variable-length codes workable at all.
Revision notes
The principle
Frequently occurring characters receive shorter codes; rare characters receive longer ones.
This reduces the total size compared with a fixed-length encoding, where every character uses the same number of bits regardless of how often it appears.
Reading the tree
Start at the root and follow branches to a character.
Record 0 for each left branch and 1 for each right branch. The sequence of digits collected is that character's code. The tree is built so that more frequent characters sit closer to the root.
Why decoding works
No character's code is a prefix of another character's code.
This means a stream of bits can be decoded without separators — follow the tree from the root until a character is reached, output it, then return to the root and continue.
Key points
- Huffman coding is a lossless method.
- Frequent characters get shorter codes.
- Rare characters get longer codes.
- Codes are read from a Huffman tree.
- Left is 0 and right is 1.
- No code is a prefix of another.
Worked examples
Example 1
A character's path from the root is left, right, right. State its Huffman code. [2 marks]
Working
Example 2
Explain why Huffman coding produces a smaller file than fixed-length encoding. [2 marks]
Working
Example 3
Explain why no Huffman code is a prefix of another. [2 marks]
Working
Common mistakes
Giving all characters the same code length.
The whole point is that lengths vary by frequency.
Reversing the 0 and 1 convention.
Left is 0 and right is 1.
Saying Huffman coding is lossy.
It is lossless — the original is perfectly recoverable.
Forgetting the prefix property.
It is what makes decoding without separators possible.
Exam tips
- Record 0 for left and 1 for right.
- Read from the root each time.
- Explain the saving through character frequency.
- Remember Huffman coding is lossless.
Key terms
- Huffman coding
- Lossless compression using variable-length codes.
- Huffman tree
- The tree from which codes are read.
- Prefix property
- No code being the start of another code.
- Fixed-length encoding
- Using the same bit count for every character.
Related topics
Written and reviewed against the current AQA specification. Spotted an error? Let us know.