How Compression Works | Run-Length Encoding — When Repetition Becomes a Number

Sometimes compression begins with the most ordinary question imaginable: how many times did the same thing happen in a row?

Consider this sequence:

AAAAAAAAAAAAAA

We could store fourteen copies of A.

Or we could write:

14 × A

Nothing profound seems to have happened. Yet this tiny move captures one of the oldest and most durable ideas in lossless compression: when identical symbols occur consecutively, store the value once and record the length of the run.

This is Run-Length Encoding, usually shortened to RLE.

RLE is simple enough for a Primary student to understand, but it opens into serious questions about representation, boundaries, worst-case expansion, sparse data, bitmaps, transformations and why modern compressors often use several simple ideas in sequence instead of one giant idea that tries to do everything.

Quick Read

Run-Length Encoding replaces repeated consecutive symbols with a symbol plus a count.
It works extremely well when long runs occur frequently.
It can make data larger when values change often.
The exact representation of runs matters: count limits, escape markers and literal blocks all affect efficiency.
RLE often becomes much more useful after a transform rearranges data so similar values cluster.
Bitmaps, masks, sparse arrays, monochrome images and repeated control values are natural RLE territory.
PackBits-style schemes combine literal runs and repeated runs to avoid catastrophic expansion.
RLE remains important because simplicity, speed and composability can matter as much as theoretical elegance.

The One-Sentence Answer

Run-Length Encoding compresses data by replacing a consecutive run of identical values with one copy of the value plus information describing how long the run lasts.

The Smallest Possible Example

Take:

AAAAABBBBCCCCCCCC

A simple RLE representation might be:

5A 4B 8C

The decoder reads “five As, four Bs, eight Cs” and reconstructs the exact original.

The representation is lossless because every run length and symbol is preserved.

Why Consecutive Repetition Matters

Now take a different sequence:

ABABABABABABABAB

This sequence is highly repetitive in an ordinary human sense, but ordinary RLE sees almost no long runs. Every symbol changes immediately.

A naive encoding might become:

1A 1B 1A 1B 1A 1B ...

That is worse than the original.

This distinction is fundamental. RLE does not compress “repetition” in the broadest possible sense. It compresses runs: repetition aligned consecutively in the current representation.

Representation Decides Whether a Run Exists

Suppose an image contains a large white background with a few black marks. Stored row by row, many rows may contain hundreds of consecutive white pixels. RLE loves this.

But rotate the image, interleave channels differently or scramble pixel order and the same visual content may produce shorter runs.

The data has not become less repetitive in any deep sense. The representation has hidden the runs.

This connects directly to our earlier article on transforms:

good transform → similar values cluster → longer runs → RLE becomes useful

RLE Can Be Brilliant on Bitmaps

Monochrome or limited-colour images are classic RLE territory.

Imagine a scanned form with huge white regions and thin black text. A row might contain:

220 white, 3 black, 18 white, 2 black, 397 white

That description can be dramatically smaller than storing every pixel independently.

This is why fax-like and bitmap-oriented systems historically found run-length ideas especially attractive. The source naturally contains long uniform regions.

RLE Loves Sparse Data

Suppose an array contains mostly zeros:

0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 2 0 0 0 ...

Instead of storing every zero, we can describe zero runs and occasional non-zero values.

Sparse matrices, masks, occupancy maps and other data structures can benefit from run-oriented representations when empty or default states cluster.

The default value becomes cheap because absence repeats.

Runs Can Be Values or Events

RLE does not have to mean repeated characters.

We can run-length encode:

identical pixel colours;
zeros in transformed coefficients;
unchanged sensor states;
repeated flags;
empty cells;
categorical labels;
boolean masks;
identical database values after sorting.

The deeper abstraction is simply:

same state continues → record duration instead of restating state

Time Series Can Become Runs

Suppose a machine reports ON every second for ten minutes, then OFF for two minutes, then ON again.

Storing 720 separate states is unnecessary if changes are rare.

We can instead record intervals:

ON × 600
OFF × 120
ON × ...

Run length has become duration.

The First Problem: How Do We Know Whether a Number Is a Count or Data?

If ordinary data itself can contain numbers, a format needs a rule distinguishing literal values from run descriptions.

Different RLE schemes solve this differently:

store every item as an explicit count-value pair;
use special escape markers;
reserve count ranges for repeated runs and other ranges for literal blocks;
encode only runs above a minimum length;
use a separate bit indicating literal or repeated mode.

The idea is simple. The format design is not.

Naive RLE Can Expand Data Badly

Suppose every literal symbol becomes a pair:

A → 1A
B → 1B
C → 1C

A source with no runs can nearly double in size.

This is why real RLE formats rarely use the most naive imaginable scheme. They distinguish repeated runs from literal sequences and encode whichever is cheaper.

Literal Blocks Rescue Incompressible Regions

Suppose the next ten bytes are all different:

A B C D E F G H I J

Instead of writing ten count-value pairs, a better scheme can say:

literal block of length 10: ABCDEFGHIJ

Then when a long repeated run appears, switch modes:

repeat Z 40 times

This hybrid design is far more robust.

PackBits Shows the Pattern

Apple’s PackBits format is a classic example of a practical RLE-style design. It uses control bytes to distinguish literal blocks from repeated runs.

The important lesson is broader than the specific byte values used by PackBits:

Do not force repeated-run notation onto regions that are not repetitive.

Compression should adapt representation to local structure.

How Long Must a Run Be Before It Pays?

Suppose a repeated-run marker costs one byte, the count costs one byte and the repeated value costs one byte. A run description costs three bytes.

Then encoding AA as a run may be worse than storing two literal As. Encoding AAA may merely break even. Encoding AAAAAAAAAA clearly wins.

The threshold depends on the format.

This is another Minimum Description Length decision:

use run notation only when run overhead < literal cost saved

Counts Have Limits

If the count field is one byte, perhaps a run can represent at most 255 items, or slightly fewer depending on reserved values.

A run of 10,000 zeros then needs several run records.

Larger count fields support long runs but increase overhead for short runs.

Even the count representation is an optimisation problem.

Runs Can Be Encoded With Variable-Length Counts

Instead of reserving a fixed number of bits for every count, a system can use a variable-length integer representation.

Short runs then receive short counts. Extremely long runs pay more bytes.

This mirrors Huffman coding’s basic economic idea: common small values should not always pay the same price as rare large values.

RLE After a Transform Can Be Far Stronger Than RLE Before It

This is where simple compression ideas become powerful in combination.

The Burrows–Wheeler Transform tends to cluster symbols that appear in similar contexts. Its output often contains longer runs than the original text.

Move-to-front coding can then turn repeated local symbols into many small numbers, often including zeros. RLE can compress the zero runs. Entropy coding can compress the resulting symbol distribution further.

transform → expose runs → RLE → entropy code

No single stage has to perform the whole miracle.

Zero Runs Matter in Transform Coding

Transforms often create coefficients where many values become zero or cluster around zero.

In lossless pipelines, exact zeros can be run-length encoded directly. In lossy image and video systems, quantisation can create long zero runs among transformed coefficients, after which run-length coding becomes useful.

The lossy decision belongs elsewhere. The RLE job remains the same: once identical values have clustered, count the run instead of restating every value.

Why Sorting Can Make RLE Better

Suppose a database column contains:

SG MY SG SG ID MY SG ID ID SG

Sort the rows by country and the column may become:

ID ID ID MY MY SG SG SG SG SG

Now run lengths appear.

If row order is semantically irrelevant or separately represented, sorting can create powerful compression in columnar storage.

Again, we see that compressibility depends on layout.

Columnar Databases Are Natural Run Factories

When values of the same field are stored together, repeated categories often cluster.

A column such as country, status, month, product category or boolean flag can contain long stretches of identical values, especially after sorting or partitioning.

RLE can then reduce storage and sometimes accelerate queries because operations can reason about whole runs at once.

Compression Can Accelerate Computation

This sounds backwards. Compression usually adds decoding work.

But suppose a database asks, “How many rows have status=ACTIVE?” and the RLE representation contains:

ACTIVE × 12,000

The system may count the run without materialising all 12,000 values.

A compressed representation can support computation directly when the operation matches the compression structure.

RLE Has Excellent Locality

Run records are usually simple and sequential. The decoder reads a value and a count, emits the run and moves on.

This makes RLE attractive in systems where extremely low complexity matters.

There is no giant dictionary to search and no deep probabilistic model to maintain.

Simplicity is an engineering feature.

RLE Is Fast Because It Knows Exactly What It Is Looking For

Run detection asks one narrow question:

Is the next value the same as the current one?

That narrowness is both strength and weakness.

It is fast because the pattern family is tiny. It misses richer structure because it refuses to search for anything else.

This connects with our Search article: restricting the search space makes compression practical but creates blindness.

RLE Does Not Understand ABABAB

Why not teach RLE to notice two-symbol motifs?

We can. But now we are moving toward dictionary or grammar compression.

Why not recognise rotated image patches? Now we are moving toward symmetry-aware modelling.

Why not predict the next value statistically? Now we are moving toward predictive coding.

Every compression method owns a particular pattern family. RLE owns consecutive sameness.

Worst-Case Expansion Is a Release-Gate Question

A production system must know not only average savings but worst-case behaviour.

If a format can double incompressible data, can buffers safely accommodate that expansion? Does the API report an upper bound? Can the system fall back to literal mode? Will the sender choose uncompressed storage when compression loses?

Compression is safe engineering only when failure modes are bounded.

The Compressor Should Be Allowed to Say “No”

One of the smartest behaviours in practical compression is refusing to compress a block that would become larger.

If the encoded representation plus metadata exceeds the literal representation, store the literal block.

This is not defeat.

It is correct optimisation.

Human Language Uses Run-Length Ideas Too

We say “I knocked three times” rather than “knock, knock, knock” when the count is what matters.

We say “repeat this exercise ten times” rather than print ten identical instructions.

We say “for the next six weeks” instead of naming every week individually.

Human language routinely compresses repeated events into counts and durations.

Education: Repetition Becomes a Rule

A learner writing:

5 + 5 + 5 + 5 + 5 + 5

can compress the repeated addition into:

6 × 5

Multiplication is not literally RLE, but the cognitive move is closely related: repeated identical operations become value plus count.

This is why run-length thinking is such a natural doorway into compression for children.

Primary School: Count the Run

Give pupils a row of coloured counters:

RRRRRBBBYYYYYYYYGG

Ask them to invent a shorter description that lets another child rebuild the exact row.

Most will independently discover count-plus-colour notation.

Secondary School: Find the Break-Even Run

Suppose a run record costs three bytes and a literal symbol costs one byte. Ask students how long a run must be before compression starts saving space.

Then change the count size and compare.

Now compression becomes an optimisation problem rather than a trick.

JC and Beyond: Renewal Processes and Run Distributions

At higher levels, runs can be modelled probabilistically. If symbol persistence follows a known process, run lengths themselves have a distribution that can be entropy-coded.

Instead of using a crude fixed-width count, a system can assign shorter representations to likely run lengths and longer representations to rare ones.

RLE then becomes the front end of a richer statistical coder.

A Run-Length Encoding Checklist

What counts as a run?
How often do long runs actually occur?
How are literal regions represented?
How is the count encoded?
What is the minimum profitable run length?
What is the maximum run length per record?
Can a transform or sorting step create longer runs?
What is the worst-case expansion?
Can the format fall back to literal storage?
Can useful operations run directly on the compressed runs?

The Deeper Point

Run-Length Encoding is easy to underestimate because the idea fits in one sentence.

But that simplicity reveals something fundamental.

Compression does not always need a grand theory. Sometimes the structure is right in front of us:

The same thing happened again, and again, and again—so stop writing it again. Count it.

That is RLE.

And when a larger compression pipeline rearranges information so repetition becomes consecutive, this tiny idea can become extraordinarily powerful.