Run-length encoding (RLE) is a lossless compression method that replaces long runs of repeated values with a single count-and-value pair. Instead of storing AAAAABBB as eight characters, RLE stores (5,A)(3,B) — just six. KS3 computing covers RLE as an accessible first example of how computers save storage space without discarding any information.

What problem does run-length encoding solve?

When data contains long stretches of the same value repeated many times, storing every copy is wasteful. Imagine a black-and-white bitmap image of a snowy landscape: vast regions are white pixels. Listing each white pixel individually wastes enormous space. RLE observes that it is far more efficient to record "2,847 white pixels" than to store the value white 2,847 separate times.

This pattern — long runs of identical values — appears naturally in many types of data:

Data type Typical repeated run
Simple bitmap images Large areas of background colour
Fax transmissions Long stretches of white paper
Text files with indentation Repeated spaces or tabs at the start of lines
Colour palettes in graphics Blocks of a solid colour

How does RLE encode data?

RLE replaces each run of consecutive identical values with a pair: (count, value).

Worked example 1 — encoding a sequence:

Original: WWWWWBBWWWW

Runs:

  • 5 × W
  • 2 × B
  • 4 × W

Encoded: (5,W)(2,B)(4,W)

Storage comparison:

Version Characters stored Bits (at 8 bits each)
Original 11 characters 88 bits
Encoded 6 values (3 pairs) 48 bits (if each pair uses 2 × 8 bits)

Saving: 40 bits — a 45% reduction.

Worked example 2 — encoding a bitmap row:

A row of a bitmap contains the colours: 3 red, 6 white, 2 red, 1 blue.

Original pixel data (using initial letters): RRRWWWWWWRRB Encoded: (3,R)(6,W)(2,R)(1,B)

To decode, simply expand each pair back into its run: the receiver repeats each value the stated number of times to recover the original data exactly.

How do you decode RLE data?

Decoding is the reverse process. For each (count, value) pair, write out the value exactly count times, one after the other.

Decode: (4,0)(2,1)(3,0)(1,1)

Step by step:

Pair Expanded output
(4,0) 0000
(2,1) 11
(3,0) 000
(1,1) 1

Full decoded sequence: 00001100001 (11 values)

This is exact — no information was lost, which is why RLE is called lossless.

When does RLE work well and when does it fail?

RLE produces the greatest savings when data contains long, uninterrupted runs of the same value. It can make data larger when data alternates frequently, because every single character must now be stored as a pair.

Example of RLE making data larger:

Original: ABCDEFGH (8 characters, 8 bytes) Encoded: (1,A)(1,B)(1,C)(1,D)(1,E)(1,F)(1,G)(1,H) (16 values, 16 bytes)

In this case, RLE doubles the storage! This is why RLE is well-suited to bitmap images with large areas of flat colour, but a poor choice for complex photographic images where adjacent pixels are rarely identical.

Situation RLE result
Long repeated runs Significant compression
Short, varied data Data becomes larger
Mixed data Varies; profiling needed

How is RLE used in real file formats?

PCX and BMP: Early bitmap formats used RLE to compress simple graphics. TIFF: Supports an RLE option (PackBits) as one of several compression schemes. Fax transmission: The ITU Group 3 fax standard uses a form of RLE — fax pages are predominantly white, so runs of white are very long and compress dramatically.

Modern image formats such as PNG and JPEG use more sophisticated compression techniques for photographs. PNG uses DEFLATE (a combination of LZ77 and Huffman coding); JPEG uses lossy compression. RLE is used where simplicity and lossless behaviour matter more than maximum compression.

How does RLE differ from other types of compression?

Method How it works Best for
Run-length encoding Replaces runs of identical values with (count, value) pairs Bitmap images, fax data
Huffman coding Assigns shorter codes to more frequent characters Text, any frequency-skewed data
Lossy compression Permanently removes some data to shrink files further Photos (JPEG), audio (MP3)

RLE is lossless and simple — you can teach it and implement it in a few lines of code. That simplicity is why it appears in the KS3 computing curriculum as an introduction to how compression works.

Frequently asked questions

Is run-length encoding lossless or lossy?

RLE is lossless. The original data can be recovered exactly from the encoded version, because the decoding process simply expands each (count, value) pair. No information is discarded. This makes RLE suitable for compressing text files, program code, and simple graphics where exact reproduction is required.

Why does RLE fail on photographic images?

Photographic images have subtle colour variations between adjacent pixels — a blue sky is not a uniform single shade of blue but contains millions of slightly different colour values. Because adjacent pixels are almost never identical, runs of length 1 dominate, and every pixel becomes a (1, value) pair — doubling the storage. JPEG handles photographs by using lossy compression, accepting a small loss of quality in exchange for far better compression ratios.

How do you represent the count in binary for RLE?

In a real implementation, both the count and the value are stored in binary. A common approach is to use one byte for the count (allowing a maximum run of 255) and one byte for the value. So (5, W) might be stored as 00000101 01010111 — 5 in binary followed by the ASCII code for W. The exact encoding scheme must be agreed in advance so the decoder knows how to interpret the bit stream.

Can RLE compress any type of file?

RLE can technically be applied to any data, but its effectiveness depends entirely on how much repetition the data contains. It excels with simple bitmaps and fax data. It is useless — and harmful — when applied to already-compressed files (such as ZIP or MP3), which have been engineered to remove repetition. Attempting to RLE-compress a ZIP file will make it slightly larger.

Explore data compression step by step with Professor Turing's interactive tutoring at aitutors.me.