Learning Objectives
By the end of this topic you will be able to:
Explain why compression is used and its benefits for storage and transmission
Distinguish between lossy and lossless compression
Describe run-length encoding (RLE) with worked examples
Describe Huffman coding and how it achieves lossless compression
Why Compress?
The Need for Compression
Compression reduces the number of bits needed to represent data. This reduces file size, lowering storage requirements and reducing transmission time and bandwidth usage.
Storage Benefits
More files fit on a given storage medium. Cloud storage costs reduced. Music libraries, photo collections, and video archives are far more practical with compression.
Transmission Benefits
Smaller files transfer faster over networks. Streaming video (Netflix, YouTube) relies heavily on compression. Reduces data usage on mobile networks.
Without compression: a 3-minute uncompressed audio file at CD quality = ~30 MB. MP3 compression reduces this to ~3 MB — 10:1 compression ratio.
Lossy vs Lossless
Lossy and Lossless Compression
Lossless
All original data can be perfectly reconstructed from the compressed version. No data is permanently removed. Used where exact accuracy is required.
Examples: PNG, GIF, FLAC, ZIP, RLE, Huffman coding.
Lossy
Data is permanently discarded — usually imperceptible to humans. Cannot reconstruct the original exactly. Used where some quality loss is acceptable for much higher compression ratios.
Examples: JPEG, MP3, AAC, MP4 (H.264).
Use lossless for: text files, executables, medical imaging, archiving. Use lossy for: music, video, web images where file size matters more than perfect accuracy.
RLE
Run-Length Encoding (RLE)
Run-length encoding replaces consecutive repeated values with a count and the value. Highly effective when data contains long runs of the same value.
Example
Original: A A A A A B B C C C C C C
RLE: 5A 2B 6C
13 values → 3 pairs = significant reduction when runs are long.
Best for: simple images (logos, pixel art), fax documents, bitmap images with large areas of the same colour.
Worst for: highly varied data with few repeated values — RLE can actually increase file size if runs are mostly length 1.
Huffman Coding
Huffman Coding
Huffman coding assigns shorter binary codes to more frequent characters and longer codes to less frequent characters, reducing the average code length. It is a lossless technique.
Step 1: count the frequency of each character in the data.
Step 2: build a Huffman tree — repeatedly merge the two lowest-frequency nodes into a new parent node until one root remains.
Step 3: assign 0 to left branches and 1 to right branches (or vice versa). Each character's code is the path from root to leaf.
Result: frequent characters get short codes (e.g. 'e' = 10), infrequent characters get longer codes (e.g. 'z' = 11010). Average code length < fixed-width encoding.
Common Mistakes
Don’t Lose Marks
!
Saying lossy compression always produces worse quality — for human perception, lossy files (MP3, JPEG) can be indistinguishable from the original. The loss is carefully chosen to be below human perceptual thresholds.
!
RLE is not always better — for images with many different colours and no long repeating runs, RLE can increase file size (it adds a count to every single value). Always relate the technique to the data type.
!
Confusing Huffman with compression ratio — Huffman produces variable-length codes. The compression achieved depends on character frequency distribution; if all characters are equally frequent, Huffman gives no benefit over fixed-width encoding.