Data Compression: RLE and Huffman Coding

Uncompressed files consume significant storage and take longer to transmit across networks. A single minute of uncompressed CD-quality audio is approximately 10 MB; an uncompressed full HD video frame is around 6 MB. Without compression, streaming, email attachments, and cloud storage as they exist today would be impractical.

Data compression reduces file size by encoding the same information more efficiently. There are two broad categories:

Type	Description	Data loss?	Examples
Lossless	Original data can be perfectly reconstructed	None	RLE, Huffman coding
Lossy	Some data is permanently discarded	Yes — irreversible	JPEG images, MP3 audio

AQA 8525 requires knowledge of run-length encoding (RLE) and Huffman coding, both of which are lossless methods. The existence of lossy compression is worth knowing for comparison, but RLE and Huffman are the assessed techniques.

Lossless compression is essential wherever the original data must be preserved exactly — executable programs, text documents, medical scans.

Run-length encoding replaces consecutive repeated values with a single frequency/data pair: the number of times the value appears followed by the value itself.

RLE achieves good compression when data contains long runs of the same value — solid-colour regions in images, silence in audio, or repeated characters in text.

Format: each pair is written as (frequency, data) or frequency data depending on the system.

Original data	RLE encoded	Pairs
AAAAAABBBCCA	(6,A)(3,B)(2,C)(1,A)	4
000000001111	(8,0)(4,1)	2
ABCABC	(1,A)(1,B)(1,C)(1,A)(1,B)(1,C)	6

The third example shows a case where RLE increases the data size — it only saves space when runs are longer than the overhead of storing the frequency/data pair.

Encoding — compress the pixel row WWWWWWWWBBBBWWWW (16 pixels: 8 white, 4 black, 4 white):

RLE pairs: (8, W)(4, B)(4, W)

Original: 16 values
Compressed: 3 pairs (6 values total) — 62.5% fewer values to store

Decoding — expand (5,A)(3,B)(2,C)(1,A):

Pair	Expansion
(5,A)	AAAAA
(3,B)	BBB
(2,C)	CC
(1,A)	A

Result: AAAAABBBCCA — 11 characters ✓

Verification: count the characters — 5 + 3 + 2 + 1 = 11. Always verify your decode length matches what the pairs predict.

RLE is effective for bitmap images with large uniform areas (logos, icons, screenshots of text editors) and ineffective for photographs, where almost every pixel has a different colour.

Huffman coding assigns shorter binary codes to characters that appear more often and longer codes to characters that appear less often. This means frequently used characters consume fewer bits, reducing the total size of the encoded data.

Standard ASCII uses 8 bits per character regardless of how often the character appears. Huffman coding tailors the code length to the actual frequency distribution.

Key principle: the more frequently a character appears, the shorter its Huffman code.

Character	Frequency	Fixed code (2 bits)	Huffman code	Huffman bits
A	5	00	1	1
B	3	01	01	2
C	2	10	001	3
D	1	11	000	3

The total character count is 11. With fixed 2-bit codes: 11 × 2 = 22 bits. With Huffman codes: (5×1) + (3×2) + (2×3) + (1×3) = 5 + 6 + 6 + 3 = 20 bits — a saving even on this small example.

A Huffman tree encodes the code for each character as a path from the root to that character's leaf node. Each left branch represents a 0 and each right branch represents a 1.

Example tree for characters A(5), B(3), C(2), D(1):

To find the code for any character, trace the path from the root and read the branch labels:

Character	Path	Code
A	root → right	1
B	root → left → right	01
C	root → left → left → right	001
D	root → left → left → left	000

Encoding the message "AAAABBC":

Character	Code	Bits
A	1	× 4 = 4
A	1
A	1
A	1
B	01	× 2 = 4
B	01
C	001	× 1 = 3

Encoded: 1 1 1 1 01 01 001 = 11 bits

Fixed 2-bit encoding of the same message: 7 × 2 = 14 bits.

To calculate how much compression Huffman coding achieves, compare the total bits in the compressed and uncompressed representations.

Worked example — text with character frequencies A=5, B=3, C=2, D=1 (11 characters total):

Uncompressed (ASCII, 8 bits per character):

$11\times 8=88\text{ bits}$

Huffman compressed (using codes from the previous slide):

$5\times 1+3\times 2+2\times 3+1\times 3=5+6+6+3=20\text{ bits}$

Bits saved:

$88-20=68\text{ bits saved}\left(\frac{68}{88}\approx 77\%\text{ reduction}\right)$

The compression ratio here is $88÷20=4.4:1$ — the compressed file is less than a quarter of the original size. In practice, the Huffman tree itself must also be transmitted alongside the compressed data so the receiver can decode it, which reduces the net saving slightly.

1. Decoding RLE in the wrong order

The format is (frequency, data) — frequency first, then the value. Decoding (3,A) gives AAA, not three separate (A) entries or A repeated three times the wrong way round.

2. Saying RLE always reduces file size

RLE increases file size when runs are short. Data like ABCDEF has no repeated values, so each pair stores one value but adds the overhead of a frequency counter — the encoded form is larger than the original.

3. Reading the Huffman tree in the wrong direction

Always start at the root and trace down to the leaf. Reading from leaf to root reverses the code. The root is the node at the top with no parent.

4. Assigning 0 to left and 1 to right inconsistently

The assignment of 0 to one branch and 1 to the other is a convention that must be applied consistently throughout the same tree. An exam question will typically label the branches or specify the convention — use whatever the question gives you.

5. Forgetting to multiply frequency by code length when totalling bits

The total compressed size is $\sum (\text{frequency}\times \text{code length})$ — not just the sum of code lengths. A character that appears 5 times contributes $5\times \text{code length}$ bits, not just $1\times \text{code length}$.