Data Compression, Huffman and RLE
Why compression matters, the difference between lossy and lossless, and full worked methods for both Huffman coding and run length encoding, including how to calculate the saving.
Why compress at all
Compression means reducing the number of bits needed to store a file.
Three reasons it matters, and questions expect the reason rather than just the word:
- Storage. More files fit in the same space.
- Transmission time. A smaller file takes less time to send, which matters most on a slow connection.
- Bandwidth. Less data sent means lower cost and less congestion, which is why streaming services compress heavily.
Lossy and lossless
Lossy compression permanently removes data judged to be less important. The file gets much smaller and the original cannot be recovered exactly. JPEG images and MP3 audio are lossy: MP3 removes frequencies most people cannot hear, and JPEG discards fine colour detail the eye is poor at noticing.
Lossless compression stores the same information more efficiently, so the original file is reconstructed exactly. PNG images and ZIP archives are lossless.
| Lossy | Lossless | |
|---|---|---|
| Original recoverable | No | Yes |
| Size reduction | Large | More modest |
| Suitable for | Photographs, music, video | Text, program code, spreadsheets, archives |
Removing "less important" characters from a program is not a smaller program, it is a broken one. That is exactly the reasoning a question about choosing a method wants.
- The original file: every byte of the data, nothing thrown away.
- Lossless finds repetition and records it more briefly.
- Unpack it and you get back exactly what you started with.
- Lossy throws data away permanently, and gets much smaller.
- Lossless: the file gets smaller, and decompressing gives back exactly the original.
- Lossy: the file gets much smaller, but detail is thrown away for good, so it cannot be restored exactly.
- Choose lossless when the data must be exact, and lossy when small losses do not matter.
Run length encoding
Run length encoding, or RLE, replaces a run of repeated values with a single value and a count of how many times it occurs.
Take a row of pixels: W W W W W B B W W W W W W B B B
That is 16 values. Written as run length pairs it becomes:
5W 2B 6W 3BFour pairs, eight values in total, storing exactly the same information. Nothing has been lost, so RLE is lossless.
Working out the saving
Count what each version costs in the same unit. If each character costs one byte and each count costs one byte:
- Original: 16 bytes.
- Compressed: 4 pairs of 2 bytes, which is 8 bytes.
- Saving: 8 bytes, which is 50 per cent.
Apply it to A B A B A B A B and every run has length one, so eight values become eight pairs and sixteen values. RLE only helps when the data contains long runs, which is why it suits simple graphics with blocks of flat colour and is useless on photographs.
- Count runs of the same colour along each row, and write the count then the colour.
- 72 pixels become 14 runs. The saving is big because long runs repeat.
- If the values keep changing, every run is 1 long and RLE saves nothing, and may be larger.
Huffman coding
Huffman coding gives the most frequent characters the shortest binary codes and the least frequent the longest, so the total number of bits needed falls.
Building the tree
Take the string BANANA. The frequencies are A three times, N twice and B once.
- Write each character as a node with its frequency.
- Repeatedly take the two lowest frequencies and join them under a new node whose frequency is their total.
- Carry on until one node remains, which is the root.
- Label every left branch 0 and every right branch 1.
- A character's code is the sequence of labels from the root down to it.
For BANANA that gives A as 0, N as 10 and B as 11, or a mirror image of that depending on which side you place each pair. Either is acceptable as long as it is consistent and you read it off your own tree.
Reading a code off the tree
Start at the root and follow the bits. When you reach a leaf, that is your character, and you go back to the root for the next one. Because no character's code is the start of another character's code, the stream can be decoded without any separators.
Calculating the saving
BANANA in ASCII: 6 characters at 7 bits each is 42 bits.
With the codes above:
B 11 2 bits
A 0 1 bit x 3 = 3 bits
N 10 2 bits x 2 = 4 bits
total = 9 bitsThe saving is 42 minus 9, which is 33 bits.
Build the tree, give a character's code by reading down from the root, and calculate the number of bits needed compared with ASCII. Practise all three, because a single question usually asks for all three.
- Count how often each character appears.
- Join the two smallest counts into a new node, and repeat until one node, the root, is left. Label branches 0 and 1.
- Read each code from the root down to its letter. Frequent letters get the shortest codes.
Key terms you must be able to define
- Compression
- Reducing the number of bits needed to store a file.
- Lossy compression
- Compression that permanently removes data, so the original cannot be recovered exactly.
- Lossless compression
- Compression that stores the same information more efficiently, so the original can be reconstructed exactly.
- Run length encoding
- A lossless method that replaces a run of repeated values with the value and a count.
- Huffman coding
- A lossless method that gives frequent characters shorter binary codes and rare characters longer ones.
- Huffman tree
- A binary tree built from character frequencies, from which each character's code is read off.
- Bandwidth
- The amount of data that can be transmitted in a given time.
Flashcards
Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.
Reach the top grade on this topic
Huffman and RLE are the two places on this specification where careful working is worth several marks at once.
Build the tree by always combining the two lowest frequencies. Write the running totals as you go, so the examiner can follow your method even if one branch ends up on the wrong side.
Say why your codes have no separators. A top answer notes that no code is a prefix of another, which is what makes the stream decodable, and that is a mark most candidates never earn.
Compare against the right baseline. A saving question means comparing your total against the same string in ASCII, so state the ASCII cost, state the Huffman cost, and subtract.
Justify lossy or lossless from the file type. Photographs and music tolerate lossy compression because human perception does not notice the loss. Text and code cannot, because every character carries meaning.
Mistakes that cost marks here
- Saying lossless compression removes data. It removes redundancy in how data is stored, not the data itself.
- Combining the two highest frequencies when building a Huffman tree instead of the two lowest.
- Forgetting that a Huffman code is read from the root downwards, not from the leaf upwards.
- Assuming RLE always reduces the size. On data with no runs it makes the file larger.
- Comparing a Huffman total against 8 bits per character when the question specified 7 bit ASCII, or the reverse.
Huffman coding was invented in 1951 by David Huffman, a student who took it on rather than sit a final exam. His method turned out to be provably optimal, which his own professor had failed to find.
Knowledge check
Exam-style questions
Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.
- LIt takes less time to transmit
- LIt uses less bandwidth, or takes less storage space at the other end
A compressed file contains fewer bits, so it takes less time to send, which matters particularly on a slow connection. It also uses less bandwidth, which reduces congestion on the network and lowers the cost for anybody paying for the data they use.
- LLossy compression permanently removes data, so the original cannot be recovered
- LGives a suitable lossy use such as photographs, music or video
- LLossless compression stores the same data more efficiently, so the original is recovered exactly
- LGives a suitable lossless use such as text, program code or a spreadsheet
Lossy compression achieves a large reduction by permanently discarding data judged to be less important, which means the original file cannot be reconstructed exactly. It is appropriate for photographs and music, where human perception does not register the detail that is removed, which is why JPEG and MP3 are used. Lossless compression instead finds a more efficient way of storing exactly the same information, so the original is recovered perfectly, at the cost of a more modest reduction in size. It is essential for text documents, program code and spreadsheets, where every character carries meaning and discarding any of it would corrupt the file.
- LIdentifies the runs correctly as four W, two B, six W
- LWrites them as value and count pairs
- LA photograph has very few long runs of identical pixels
- LSo RLE would give little saving and could make the file larger
The row contains four W, then two B, then six W, so under run length encoding it is stored as the pairs 4W, 2B, 6W. That is three pairs, six values in total, in place of the original twelve, and nothing has been lost. Run length encoding would be a poor choice for a photograph because photographs contain gradients and noise rather than blocks of identical colour, so almost every run has a length of one. Each single pixel would then be stored as a value and a count, which is two values where one was needed, and the compressed file would be larger than the original.
- LCounts the frequency of each character
- LCreates a node for each character with its frequency
- LRepeatedly combines the two nodes with the lowest frequencies under a new parent
- LContinues until one root node remains, and labels branches 0 and 1
- LA character's code is read by following the branch labels from the root down to that character
First count how often each character occurs: A appears five times, B twice, R twice, C once and D once. Each character becomes a node carrying its frequency. The two nodes with the lowest frequencies, C and D, are then joined under a new parent node whose frequency is their total of two. That process repeats, always taking the two lowest frequencies still available, until a single root node remains holding the total of eleven. Every left branch is then labelled 0 and every right branch 1. To obtain the code for a character you start at the root and follow the branches down to that character's leaf, writing down each label as you pass it. Because A is the most frequent it ends up nearest the root and gets the shortest code, while C and D are deepest and get the longest, which is what makes the total number of bits smaller than fixed length coding would need.
- LCalculates the ASCII size as 280 bits
- LCalculates the saving as 132 bits
- LGives approximately 47 per cent
In 7 bit ASCII the message takes 40 multiplied by 7, which is 280 bits. Huffman coding needs 148 bits, so the saving is 280 minus 148, which is 132 bits. As a percentage of the original that is 132 divided by 280, which is 0.4714, or approximately 47 per cent.