Run-length encoding (RLE)

5 minAS Level1.3.3

AI-drafted, independently checked · not yet teacher-reviewed

By the end of this lesson

By the end you can encode and decode data with run-length encoding, work out the compressed size, and say when RLE helps and when it backfires.

You already do this

Imagine reading AAAAAAAAAAAA aloud to a friend over the phone. By the fourth "A" you'd give up and say "twelve As".

Congratulations: you've just invented RLE.

Definition

Run-length encoding (RLE)

A lossless compression method in which each run (a sequence of consecutive, identical data items, such as characters or pixel colours) is replaced by one copy of the item and a count of how many times it repeats.

Four runs become four (count, character) pairs: 20 bytes down to 8.

Worked example: Encode a very sleepy message

Encode ZZZZZZZZzzzzzz!!! with RLE as count–character pairs. Each count and each character takes 1 byte.

Have a go first?

Worked example: Decode it back

Decode the RLE data 5A 1R 2G 1H.

Have a go first?

Quick check

Fill in the blanksQuestion 1 · Recall

Encode PPPPPPQQQRRRRRRRR with RLE, writing each run as count then character:

One-line answerQuestion 2 · Recall

Decode the RLE data 1Y 8A 1Y.

CalculateQuestion 3 · Apply

The string ABBBBBBBBBCD is compressed with RLE. Each run is stored as a 1-byte count and a 1-byte character. How many bytes does the compressed version take?

bytes

Answer the 3 questions above to continue.

Previous lessonLossy or lossless? Justify your choice Next lessonCompressing text: a dictionary of repeats