Data Compression: Huffman and Run-Length Encoding
Why Compress Data?
Data compression reduces the size of a file. Smaller files download faster, cost less to transmit over a network and consume less storage space. A high-definition video without compression could occupy hundreds of gigabytes — compression makes streaming and cloud storage practical at everyday internet speeds.
This lesson covers two lossless compression techniques: Huffman coding and run-length encoding (RLE). Both methods remove redundancy from the data without discarding any information — the original file can be recovered perfectly from the compressed version.
Lossless compression reduces file size without losing any data. The original file can be perfectly reconstructed. This is essential whenever data integrity matters — for example, text files, program code, medical images and database backups.
Huffman Coding
Huffman coding exploits the fact that in any real piece of text, some characters appear far more often than others. Standard encoding uses the same number of bits for every character (for example, 7-bit ASCII uses 7 bits for every character, regardless of frequency). Huffman coding assigns shorter codes to common characters and longer codes to rare ones, so on average fewer bits are needed.
The algorithm produces a Huffman tree. To read a character’s code, you trace a path from the root of the tree to the leaf node labelled with that character. Each left branch adds a 0 to the code and each right branch adds a 1 (or the reverse — the convention is set when the tree is built). Characters that appear most often are placed nearest the root, so their codes are shortest.
Suppose a Huffman tree is given for four characters. Reading left as 0 and right as 1:
Character E (most frequent) — at depth 1 — code: 0 (1 bit).
Character T (second most frequent) — at depth 2 — code: 10 (2 bits).
Character A — at depth 3 — code: 110 (3 bits).
Character Z (least frequent) — at depth 3 — code: 111 (3 bits).
To encode the string “EETA”: E=0, E=0, T=10, A=110 → 0 0 10 110 = 7 bits total (1 + 1 + 2 + 3). In standard 7-bit ASCII, “EETA” would need 4 × 7 = 28 bits. Huffman encoding saves 21 bits for this short string.
Important: In your exam you will always be given the Huffman tree. You are not required to construct a tree from scratch — only to read codes from a given tree and calculate the total bits saved.
Calculating Bits Saved by Huffman Coding
To calculate bits saved, compare the bits needed to store the message in ASCII against the bits needed using the Huffman codes from the tree:
Problem: A message contains 10 characters. In ASCII (7 bits per character), storage = 10 × 7 = 70 bits. Using a Huffman tree, the 10 characters need a total of 28 bits. How many bits are saved?
Step 1 — ASCII bits = number of characters × 7 = 10 × 7 = 70 bits.
Step 2 — Huffman bits = sum of (frequency of each character × its code length from the tree). Here given as 28 bits.
Step 3 — Bits saved = 70 − 28 = 42 bits saved.
Follow this method exactly: calculate ASCII total first, then Huffman total, then subtract. Show each step to gain method marks.
Bits saved = (number of characters × 7) − (sum of frequency × code length for each character). Always show both totals before subtracting. Set out each step clearly so your method can be followed.
Run-Length Encoding (RLE)
Run-length encoding (RLE) works on data that contains long runs of repeated values. Instead of storing each repeated value separately, RLE stores it as a pair: the count (how many times the value repeats) followed by the value itself. These are called frequency/data pairs.
RLE is especially effective for simple bitmap images with large areas of solid colour, such as diagrams, logos or fax transmissions. It is not effective on photographic images where adjacent pixels rarely share the same value.
Consider this 16-bit bitmap row (0 = white, 1 = black):
Original data: 0000011100000011
Reading left to right: five 0s, then three 1s, then six 0s, then two 1s.
RLE frequency/data pairs: 5 0 3 1 6 0 2 1
Original: 16 values. Compressed: 8 values (4 pairs). For this row, RLE halves the data.
Remember: RLE writes the count first, then the value. So “5 0” means five zeros; “3 1” means three ones.
When RLE Works Well — and When It Doesn’t
RLE performs best when the data has long, uninterrupted runs of the same value. A solid-colour logo might compress dramatically. However, if the data alternates frequently (e.g. 010101), RLE actually increases the file size, because each single value requires its own count-value pair. You would produce 1 0 1 1 1 0 1 1 1 0 1 1 — 12 values instead of 6. Understanding this limitation is important for exam questions that ask you to evaluate whether RLE is suitable for a given scenario.
Huffman coding, by contrast, is effective for any text data since natural language always has uneven character frequencies. The two techniques suit different types of data and can even be combined in more advanced compression systems.