Run length encoding (RLE)
What is Run Length Encoding?
Run Length Encoding (RLE) is a simple lossless compression technique that works by replacing consecutive repeated values with a single frequency/data pair. Instead of storing each value individually, RLE stores how many times a value repeats followed by the value itself. This can dramatically reduce file size when data contains long runs of the same value.
RLE is particularly effective for bitmap images with large areas of a single colour, simple graphics, and fax transmissions. It offers little benefit - and can even increase size - for data that changes frequently with few or no repeated values.
Written as (3, A) or equivalently 3 A - both mean "the value A repeated 3 times".
Worked Examples
Text Data with Repeated Characters
Apply RLE to the string: AAABBBCCDDDDEE
Scan left to right, counting each run of identical characters:
| Run | Character | Count | Pair |
|---|---|---|---|
| AAA | A | 3 | (3, A) or 3 A |
| BBB | B | 3 | (3, B) or 3 B |
| CC | C | 2 | (2, C) or 2 C |
| DDDD | D | 4 | (4, D) or 4 D |
| EE | E | 2 | (2, E) or 2 E |
RLE output: 3 A, 3 B, 2 C, 4 D, 2 E (also written (3,A)(3,B)(2,C)(4,D)(2,E)) = 10 stored values vs 14 original characters. The longer the runs, the greater the saving.
Decoding: to reconstruct the original, expand each pair - write the character the stated number of times, in sequence.
Bitmap Image Row with Colour Runs
A single row of a black-and-white bitmap contains: WWWWWBBBBWWW (W = white pixel, B = black pixel). This represents 12 pixels.
Applying RLE produces three pairs:
| Run | Colour | Count | Pair |
|---|---|---|---|
| WWWWW | White | 5 | 5 W |
| BBBB | Black | 4 | 4 B |
| WWW | White | 3 | 3 W |
RLE output: 5 W, 4 B, 3 W (also written (5,W)(4,B)(3,W)) = 6 stored values vs 12 original pixels - a 50% reduction. Images with large areas of solid colour (logos, icons, diagrams) compress particularly well with RLE.
When RLE Increases File Size
RLE only saves space when data contains meaningful runs of repeated values. Consider applying RLE to: ABCDE
Every character appears exactly once - there are no runs longer than 1:
| Original | RLE pair |
|---|---|
| A | (1, A) |
| B | (1, B) |
| C | (1, C) |
| D | (1, D) |
| E | (1, E) |
Original: 5 values. RLE output: 1 A, 1 B, 1 C, 1 D, 1 E (also written (1,A)(1,B)(1,C)(1,D)(1,E)) = 10 stored values - twice the original size. RLE is unsuitable for this data because there are no repeated runs to exploit. In general, RLE works well when runs are long and frequent, and poorly when data alternates rapidly between different values.
Key Takeaways
- RLE replaces runs of identical consecutive values with a frequency/data pair - storing how many times the value repeats and the value itself.
- RLE is lossless: the original data can always be reconstructed exactly from the encoded pairs.
- To decode RLE, expand each pair by writing the value the stated number of times in sequence.
- RLE is most effective when data contains long runs of the same value - such as large areas of solid colour in bitmap images.
- RLE can increase file size when data alternates frequently with few or no repeated runs - each unique value becomes a pair, doubling the storage needed.