Data compression

Data compression means reducing the number of bits needed to store or transmit a piece of data.

The specification notes that "it is common for data to be compressed" and that there are different ways to compress data — Huffman coding and run length encoding being the two you must know.

Why data is compressed

Reason	Explanation
Less storage space	More files fit on the same device
Faster transmission	Fewer bits to send means files transfer more quickly
Less bandwidth used	Important for streaming, mobile data and busy networks
Faster downloads and streaming	Video and music can play without buffering

A useful framing: compression saves space when storing and time when transmitting.

Where you meet it

• Images — JPEG, PNG
• Sound — MP3
• Video — MP4
• General files — ZIP archives
• Web pages — compressed before being sent to your browser

The link to the file-size formulae

The formulae in 3.3.6 and 3.3.7 give the uncompressed size:

$\text{image} = W \times H \times D \qquad \text{sound} = \text{rate} \times \text{res} \times \text{secs}$

A real photograph or song file is normally much smaller than these calculations suggest, precisely because compression has been applied. That is why compression questions so often ask you to compare a compressed figure against an uncompressed one.

AQA tip. A "why is data compressed?" question usually carries 2 marks, so give two developed reasons: not just "to save space" but "to reduce the storage space required, so more files fit on the same device", and "to reduce transmission time, so files download more quickly and use less bandwidth".

The principle

Huffman coding gives the most frequently used characters the shortest codes, and rarely used characters longer codes.

In ASCII every character takes the same 7 bits, whether it appears once or a hundred times. Huffman coding exploits the fact that some characters are far more common than others: making those short saves far more than the rare long codes cost.

Reading a Huffman tree

Start at the root and follow the branches to the character, collecting the 0 or 1 labelled on each branch.

The rule to remember: the closer a character is to the root, the shorter its code — and therefore the more frequently it must occur.

Encoding and decoding

To encode, replace each character with its code:

'BAD'  →  10  0  111  →  100111

To decode, read the bits one at a time, following the tree from the root, and output a character each time you reach one — then return to the root.

110 10 0  →  C  B  A  →  'CBA'

Why no separators are needed. No code is the beginning of another code — A is 0, and no other code starts with 0. This means the bit stream can be decoded unambiguously without any markers between characters, which is what makes Huffman coding work at all.

AQA tip. When reading codes off a tree, write them all out in a small table before starting any calculation. Almost every Huffman error comes from misreading a code, and a written table lets you check each one against the diagram.

This is the highest-value skill in 3.3.8, and it has three parts the specification names explicitly.

1. Bits required using Huffman coding

$\text{Huffman total} = \sum (\text{frequency} \times \text{code length})$

Method: build a table with one row per character.

Encode the word BANANA using the tree above (A=0, B=10, C=110, D=111).

Character	Frequency	Code	Length	Freq × Length
A	3	0	1	3 × 1 = 3
B	1	10	2	1 × 2 = 2
N	2	110	3	2 × 3 = 6
Total	6			11 bits

(Treating N as having the code 110 for this illustration.)

2. Bits required uncompressed in ASCII

$\text{ASCII total} = \text{number of characters} \times 7$

ASCII is 7-bit (3.3.5), so each character takes exactly 7 bits regardless of how often it appears.

BANANA has 6 characters, so:

$6 \times 7 = 42 \text{ bits}$

⚠️ Use 7, not 8. The specification names 7-bit ASCII. Using 8 is the single most common error in this calculation. If a question explicitly says each character is stored in a byte, then use 8 — but otherwise 7 is correct.

3. Bits saved

$\text{bits saved} = \text{uncompressed} - \text{compressed}$

$42 - 11 = 31 \text{ bits saved}$

You may also be asked for the saving as a percentage:

$\frac{31}{42} \times 100 \approx 74\%$

The full method, every time

1. Read every code off the tree and write them in a table.
2. Count the frequency of each character in the data.
3. Multiply frequency × code length for each, and total → compressed bits.
4. Count all the characters and multiply by 7 → uncompressed bits.
5. Subtract → bits saved.

AQA tip. Show the table. Mark schemes award marks for the frequencies, the code lengths and the products separately, so a slip in the final addition still leaves most of the marks intact.

Run length encoding replaces runs of repeated values with a pair giving the frequency and the data value.

The specification requires you to represent data as frequency/data pairs.

AQA's own worked example

"eg 0000011100000011 would become 5 0 3 1 6 0 2 1"

Reading the original left to right:

Run	Pair
five 0s	5 0
three 1s	3 1
six 0s	6 0
two 1s	2 1

Result: 5 0 3 1 6 0 2 1 — 16 values reduced to 8.

Note the order: frequency first, then the data value. Writing 0 5 instead of 5 0 reverses the meaning.

Applying it to a bitmap

RLE suits bitmap images well, because rows often contain long runs of identical pixels (3.3.6). Each row is encoded separately:

Row:  1 1 1 1 0 0 1 1
RLE:  4 1  2 0  2 1

Eight values become six.

Decoding

Reverse the process — each pair means "repeat this value this many times":

3 1  4 0  2 1   →   111 0000 11   →   111000011

When RLE works — and when it fails

Data	RLE result
00000000	8 0 — excellent, 8 values to 2
0000011100000011	5 0 3 1 6 0 2 1 — good, 16 to 8
01010101	1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 — worse, 8 values become 16

RLE only helps when the data contains long runs of repeated values. With alternating data it produces a larger result, because every single value becomes a pair.

This is the key evaluation point. RLE is excellent for simple graphics with large blocks of flat colour — logos, icons, line drawings — and poor for photographs, where adjacent pixels rarely have exactly the same value.

AQA tip. When encoding, work strictly left to right and never merge non-adjacent runs. If the data returns to a value you have already used, that starts a new pair — 5 0 3 1 6 0 correctly has two separate runs of 0s.

The specification notes there are different ways to compress data, and questions often ask you to choose or compare.

The comparison

	Huffman coding	Run length encoding
How it works	Frequent characters get shorter codes	Runs of repeated values become frequency/data pairs
Best for	Text, where some characters are far more common	Simple images, with large blocks of identical values
Poor for	Data where all values occur equally often	Data with few or no runs — it can make it larger
Needs extra data?	Yes — the tree must be stored or sent so the data can be decoded	No
Complexity	More complex — requires building and reading a tree	Very simple

Matching the method to the data

Data	Best method	Why
A page of English text	Huffman	Letters like e and t are far more frequent than q or z
A two-colour logo with large flat areas	RLE	Long runs of identical pixels
A photograph	Neither works well	No long runs, and colours are fairly evenly spread
A scanned black-and-white document	RLE	Long runs of white background

The point students miss about Huffman

The tree must be stored or transmitted along with the compressed data, otherwise the recipient cannot decode it. For a short piece of data the tree can outweigh the saving — which is why Huffman coding is most effective on large files where the tree is a tiny proportion of the total.

Lossy and lossless — context, not content

Compression methods are sometimes described as lossless (all original data recoverable, as with Huffman and RLE) or lossy (some data discarded permanently, as with JPEG and MP3). The specification does not name these terms in 3.3.8, so they are not required — but noting that Huffman and RLE both allow the original data to be reconstructed exactly is a legitimate and creditworthy observation in an evaluation answer.

AQA tip. In a "which method should be used?" question, name the method, justify it with the pattern in the data — long runs for RLE, uneven character frequencies for Huffman — and if you have room, note the drawback of the option you rejected.