What is Run-Length Encoding?
Run-Length Encoding (RLE) is one of the simplest compression algorithms. It works by finding runs — sequences of the same value repeated consecutively — and replacing them with just two pieces of information: how many times the value repeats, and what the value is.
It is easy to understand with an example. Imagine this string of characters:
AAAAAABBBCCCCCDDDDDD
Instead of storing all 20 characters, RLE compresses it to:
6A 3B 5C 6D
That is only 8 values instead of 20 — a massive saving!
RLE in Images
RLE is particularly useful for images that have large areas of the same colour — like logos, cartoons, diagrams, and simple graphics. Consider a row of pixels in a black-and-white image:
White White White White White Black Black Black White White
Uncompressed: 10 values. With RLE: 5 White, 3 Black, 2 White — just 6 values.
Early fax machines used a form of RLE to compress documents before sending. A typical page of text has large white areas with occasional black marks — perfect for RLE.
When RLE Works Well (and When It Does Not)
RLE is very effective when data contains long runs of the same value. It is ineffective — or even makes files larger — when data changes frequently with few repetitions.
| Data type | RLE effectiveness |
|---|---|
| Simple diagrams | Excellent |
| Black & white text | Good |
| Photographs | Poor |
| Random data | Makes it larger |
For a photograph, almost every pixel is a different colour, so RLE cannot find any useful runs to compress.
If you apply RLE to data with no runs, the compressed version adds a count before every single value, which makes the file bigger than the original!
A Worked Example
Let's compress this binary sequence using RLE:
000000001111000011111111
Reading the runs:
- 8 zeros: 8, 0
- 4 ones: 4, 1
- 4 zeros: 4, 0
- 8 ones: 8, 1
Compressed: 8,0 | 4,1 | 4,0 | 8,1 — 8 values instead of 24. That is a 3:1 compression ratio.
Real-World Use
RLE is used in:
- BMP images (Windows bitmap format)
- TIFF files (scanned documents)
- PCX images (older graphics format)
- As a sub-step inside more complex compression algorithms
Modern compression tools usually combine RLE with other techniques (like Huffman coding) to achieve better results on diverse data.
Practice Problems
Use RLE to compress the following string. State the compressed result and the compression ratio: WWWWWWBBBBWWWWWWWWWWBB
Show answer
Explain why RLE would be a poor choice for compressing a JPEG photograph, and suggest a better-suited use case.