Run-Length Encoding

RLE and the value of a simple representation

Run-Length Encoding is a classic and direct form of lossless data compression. Run-Length Encoding (RLE). It replaces each maximal run of repeated values with a count and a value. A format may also encode one-item runs, depending on its representation. The count describes how many consecutive positions use the value, not how often it appears in the complete file.

RLE exploits contiguous blocks of identical data. Global symbol frequencies and phrase dictionaries belong to other classes of methods. RLE has appeared in fax systems and image formats because its encoder and decoder are easy to implement. A decoder reproduces a run by writing the value the indicated number of times, so it does not need a complex data model. The same idea also appears as one stage in larger compression pipelines.

How run-length encoding represents data

The mechanism can be shown with a sequence of colored tiles. A new run begins whenever the next tile differs from the current value:

RED, RED, RED, RED, RED, BLUE, BLUE, BLUE, GREEN, GREEN, GREEN, GREEN, GREEN, GREEN, GREEN

A compact description is:

5 RED, 3 BLUE, 7 GREEN

RLE scans a data stream and records two fields for each maximal run of consecutive, identical values. A run ends before a symbol changes or at the end of the stream, so adjacent runs cannot contain the same value:

• The Count: The number of occurrences in the run.
• The Value: The symbol repeated in the run.

RLE example: a simple bitmap image

RLE suits simple bitmap images with limited palettes, such as icons, logos, and technical drawings. The following example compresses a monochrome 10x8 pixel arrow. This example encodes each row separately to keep the image row boundaries visible. A concrete file format may also store rows as separate units. If the rows were joined into one stream, boundary runs could merge and the number of pairs would change.

Step 1: Uncompressed data

An image can be represented as a sequence of pixel values. In this black-and-white example, 'W' represents a white pixel and 'B' represents a black pixel. Reading from left to right and top to bottom produces one linear data stream. The spaces between groups separate rows and are not image data:

WWWWWWWWWW WWWWBBWWWW WWWWBBWWWW WWWWBBWWWW BBBBWWBBBB WWWWBBWWWW WWWWBBWWWW WWWWBBWWWW

In uncompressed form, the image stores 80 pixel values (10 pixels per row * 8 rows). At one byte per pixel, this is 80 bytes, excluding headers and possible row padding.

Step 2: The RLE encoding process

The RLE encoder scans the stream and identifies maximal runs of identical values. At each step it writes the current run before moving to the next symbol:

1. The first run is 10 white pixels. The encoder writes the pair (10, W).
2. The next run is 4 white pixels. It writes (4, W).
3. Next is a run of 2 black pixels. It writes (2, B).
4. Then, a run of 4 white pixels. It writes (4, W).
5. The process continues row by row until the end of the data stream. A change from white to black or black to white starts a new run.

Step 3: Compressed output and analysis

The final RLE-encoded representation of our image would be the following sequence of (count, value) pairs:

(10, W), (4, W), (2, B), (4, W), (4, W), (2, B), (4, W), (4, W), (2, B), (4, W), (4, B), (2, W), (4, B), (4, W), (2, B), (4, W), (4, W), (2, B), (4, W), (4, W), (2, B), (4, W)

The output contains 22 pairs, or 44 fields, because each pair stores one count and one pixel value. The example encodes rows separately, so pairs at a row boundary remain separate even when the same value occurs at both sides. The count and value may occupy different numbers of bytes in a real file, and a format with control flags can represent literal fragments differently. The first line, WWWWWWWWWW, becomes (10,W), so 10 symbols become 2 fields.

The compression ratio in this simplified field model is $80 / 44 \approx 1.82:1$. Larger uniform areas increase this ratio, while the result also depends on the count representation and control fields.

RLE decompression

The decompressor receives a sequence of (count, value) pairs. For each pair, it writes the value to the output as many times as the count specifies. After all pairs, the example should contain 80 pixels, exactly the length of the original image stream.

1. Read the first pair: (10, W). Output: "WWWWWWWWWW".
2. Read the second pair: (4, W). Output: "WWWW".
3. Read the third pair: (2, B). Output: "BB".
4. ...and so on, until the end of the compressed data is reached.

Decompression only traverses the pairs and repeats each value. This cost suits applications that require fast decoding. Checking the sum of the counts can detect an incomplete or malformed stream.

The worst case for RLE

RLE is specialized. Long runs reduce the number of fields, while data without repetitions needs an extra count for each symbol. The encoded result can then be larger than the input, especially when the count occupies a fixed-size field.

Example: a string without repeated characters

Consider ABCDEFG and apply basic RLE. The encoder scans the data:

• It sees 'A'. The run of 'A's is 1. It must encode this as (1, A).
• It sees 'B'. The run of 'B's is 1. It must encode this as (1, B).
• ...and so on for every character.

The encoded output is the following. The example makes the overhead visible:

(1, A), (1, B), (1, C), (1, D), (1, E), (1, F), (1, G)

The original string has 7 characters. The output has 14 fields, with 7 counts and 7 values. If each field occupies one byte, the representation doubles the data size before headers are counted. Practical formats therefore need a threshold or a literal-run mode.

Practical RLE implementations and variants

Practical RLE formats extend the basic model with a representation for fragments where a count and value pair would not save space. The switching threshold depends on the count size, the value representation, and the header overhead.

Control flags

One variant uses a special control byte or flag. The encoder chooses a representation for each data segment, and the decoder interprets the control value before reading the following fields:

• For a run that is worthwhile, such as 3 or more identical characters, it outputs a "run follows" flag, the count, and the value.
• For a non-repetitive fragment, it outputs a "raw data follows" flag, the raw-byte count, and the raw bytes.

This hybrid approach can limit expansion because runs and literal fragments have separate representations. TIFF PackBits uses control values for runs and literal data, while BMP defines RLE8 and RLE4 variants. Variants of this technique also occur in PCX.

Applications

RLE appears as a standalone method and as one stage in larger formats and algorithms. In each application, the format defines the count meaning, value representation, and marker used to delimit data.

• Fax machines: ITU-T Recommendations T.4 and T.6 encode black-and-white images with run-length codes, including one-dimensional Modified Huffman coding and two-dimensional coding. The line structure and end-of-line markers are part of the fax format.
• Image file formats: RLE and its variants occur in formats such as BMP (Windows Bitmap), PCX, and TIFF (Tagged Image File Format). BMP names RLE8 and RLE4 according to the pixel representation, while TIFF PackBits uses a control-byte scheme.
• Stage in a larger algorithm: The Burrows-Wheeler transform used by bzip2 rearranges data without changing its contents. The bzip2 implementation performs its own RLE stage before the transform, then uses steps including move-to-front and Huffman coding.

RLE as a basic compression method

Run-Length Encoding represents predictable repetitions with a count and a value. Long runs produce compact output, while non-repetitive data requires a literal-run variant. RLE remains useful for images, fax coding, and pipelines that combine it with transforms or entropy coding.