GCSE · Computer Science · AQA · Spec 8525

Run-length encoding (RLE)

Read a row of pixels aloud and you say 'five white, three black, two white'. That shortcut is run-length encoding, and it can backfire.

Computer Science · Data compression

Say it out loud: five white, three black, two white

Step along one row of black-and-white pixels (W = white, B = black) and watch the encoder count each run, then write it down as a pair.

Before you reach pixel 6, where the colour changes from W to B: what will the encoder write down at that moment?

 1  Read the next pixel
 2  Same colour as the run we are counting? Add 1 to the run count
 3  Different colour? Write the finished run out as: frequency, then data
 4  Start a new run with this pixel (count = 1)
 5  End of the row? Write out the last run

Pixel read	Run so far	Pairs written
1: W	W x 1	(none yet)

Output

Step 1: Pixel 1 is W. There is no run yet, so we start one and count 1.

1 / 11

Press Next to read one pixel at a time. Watch the 'Run so far' column grow, then watch what appears in 'Pairs written' the moment the colour changes.

Step 1 of 11: Pixel 1 is W. There is no run yet, so we start one and count 1..

Exam line: Each run becomes a pair: frequency first (how many), then data (what). Write the pair when the value changes, and don't forget the final run at the end of the row.

Watch out: A pair is only written when the run ENDS. While the same colour keeps coming, the encoder is just counting.

Your turn · Encode, then decode

Now you do the encoding

Compress the bit pattern 111100000011 with run-length encoding, then rebuild it to see whether anything was lost. Along the way, decode a short list of letters too.

Split the pattern into runs of identical bits: 1111 | 000000 | 11. That is four 1s, then six 0s, then two 1s (4 + 6 + 2 = 12, so every bit is accounted for).
missing step

Which line is step 2?

1111 becomes 4 11111 becomes 1 41111 becomes 4

Exam line: Encode: count each run, then write frequency then data. Decode: write each data value out its frequency number of times, in order.

Predict, then check

Two short pieces of data. Which one will RLE help, and which one might it hurt?

Data 1 is AAAAAABBBB. Data 2 is ABCD. Each is turned into frequency/data pairs. Which prediction is right?

Check your thinking

Which idea is closest to yours?

A friend compresses some data with run-length encoding and then asks you a question about it.

Which of these is closest to what you think right now?

RLE always makes data smaller. That is what compression is for.RLE has to throw some data away to get the size down.RLE only works on text, because you need letters to count.RLE saves space when the same value repeats in long runs, and decoding rebuilds the data exactly.

How sure are you?

I'm sureI think soI'm guessing

RLE always makes data smaller. That is what compression is for.

This is a common misconception

Not always. A pair stores two values: a frequency and the data. So a run of one value turns 1 value into 2 (bigger), a run of two turns 2 values into 2 (no saving), and only a run of three or more shrinks. That is why ABCD got bigger earlier, and why long runs are what RLE feeds on.

RLE has to throw some data away to get the size down.

This is a common misconception

No. RLE loses nothing, because every run's value and count are stored. You saw it when you decoded the pairs back into exactly the original pattern. That is what lossless means: the saving comes from writing repeats more briefly, not from deleting anything.

RLE only works on text, because you need letters to count.

This is a common misconception

RLE works on any sequence of values with runs in it. You have already run it on a row of pixels (an image) and on a bit pattern, as well as on letters. What matters is whether the same value appears several times in a row, not what kind of data it is.

RLE saves space when the same value repeats in long runs, and decoding rebuilds the data exactly.

This matches the evidence

Yes. Long runs shrink to one pair each, and decoding writes every value back out the stated number of times. Keep one more detail: RLE only spots identical values side by side. A repeating pattern such as ABABAB has no runs at all, so it does not shrink.

RLE: lossless, works on text, bits and images, and saves space only when the same value repeats in long runs.

Exam line: Savings come from long runs, decoding rebuilds the data exactly, and RLE works on any sequence of values that has runs.

WHAT YOU'VE LEARNED

A quick recap of today's lesson.

Write down how many, then what, and a long boring row of data shrinks to a few pairs.

What you need to know

A run is a stretch of the same value repeated one straight after another.
RLE stores each run as a pair of numbers or symbols: the frequency (how many) first, then the data (what).
Decoding writes each data value out its frequency number of times, which rebuilds the original data exactly.
RLE saves space when runs are long, but it can make data bigger when values rarely repeat.

The big picture

Run-length encoding squashes data by replacing each run of identical values with a pair: how many times it repeats (the frequency), then the value itself (the data). Decoding rebuilds the original exactly, so nothing is lost. It saves space when runs are long, and it can make data bigger when nothing repeats.

Key points

1Run-length encoding is a compression method: each run of identical values is replaced by a frequency/data pair.

2It is lossless. Decoding the pairs gives back exactly the original data, so nothing has been discarded.

3To judge whether it saved space, count the values stored before and after. Each pair stores two values.

4A run of one value doubles in size, a run of two stays the same, and a run of three or more shrinks.

5RLE only spots identical values side by side. A repeating pattern such as ABABAB has no runs, so it does not shrink.

6It works on any sequence of values, including text, bit patterns and rows of pixels in an image.

.we-_R_18slubsnpfiv5ubrb_ [data-we-step]{display:flex !important}.we-_R_18slubsnpfiv5ubrb_ [data-we-solution]{display:block !important}.we-_R_18slubsnpfiv5ubrb_ [data-we-reveal]{display:none !important}

Worked example

Problem

Compress the 15 characters KKKKKKQQQQQQQRS using run-length encoding. Then decide whether RLE has saved space by counting the values stored before and after.

⚠ Watch out

Believing compression always makes data smaller. Every run, even a run of one, needs its own frequency, so data with few repeats can grow. Count values, not pairs: one pair is two values.

🧠

Memory hook

'How many, then what.' Say it every time you write a pair. And remember ABCD: when nothing repeats, RLE turns 4 values into 8.

✓

Check yourself

A row of 20 pixels is all black. What does RLE store, and what kind of row would stop it helping? (Answer: 20 B, two values for twenty; rows of mostly one- or two-pixel runs.)

Flashcards

(10)

What is a 'run' in run-length encoding?

A stretch of the same value repeated one straight after another, such as BBBB in BBBBWW.

What does a frequency/data pair record?

How many times the value repeats (frequency), then the value itself (data): 'how many, then what'.

How do you decode a list of frequency/data pairs?

Write each data value out as many times as its frequency says, keeping the pairs in order.

What does it mean to say RLE is lossless?

Decoding rebuilds the original data exactly. Nothing is thrown away to get the saving.

When does RLE save the most space?

When the data has long runs of the same value, because a whole run shrinks to a single pair.

When can RLE make data bigger?

When values rarely repeat. Each run of one value needs a frequency as well, so it doubles in size.

Why count values, not pairs, when judging an RLE saving?

Because every pair is two stored values: a frequency and a data value. Compare the totals either side.

What happens to a run of 1, a run of 2 and a run of 3 or more?

A run of 1 doubles (1 value becomes 2), a run of 2 stays the same size, a run of 3 or more gets smaller.

Does ABABAB shrink under RLE?

No. RLE only spots identical values side by side, and a repeating pattern has no runs: it stores 1 A 1 B 1 A 1 B 1 A 1 B.

What kinds of data can RLE be used on?

Any sequence of values that can contain runs: text, binary data and the pixels of an image.

Tap any card to flip it, or use Study as deck to go through them one at a time. In the full lesson these run as a spaced-repetition deck — you rate each card Hard, Good or Easy and the tricky ones keep coming back until they stick.

Learning with Lightbulb is opening soon

You can use this lesson now. Join the waitlist and we'll let you know when the full Lightbulb experience is ready.

Keep me posted

Say it out loud: five white, three black, two white

Now you do the encoding

Which idea is closest to yours?

More AQA GCSE Computer Science topics