Interactive Math & Science Lessons

Run-Length Encoding (RLE)

Type any text and watch it split into runs — consecutive repeats of the same character collapse into a single (symbol, count) pair. Long runs shrink the data; short runs make it grow.

Loading interactive simulation...

Lesson

The theory — Run-Length Encoding (RLE)

Run-length encoding replaces each maximal run of identical symbols with one (symbol, count) pair. What reaches the readout is not the text but two numbers: N characters and R runs. Every other figure on the page is those two divided by one another.

What each symbol means

N
the number of characters going in. It is the length of what you typed, nothing more.
R
the number of runs — maximal blocks of one repeated symbol. R goes up by one wherever two neighbours differ, so it counts boundaries, not characters.
L̄
N/R, the average run length. This is the only quantity that decides the outcome.
ratio
N/2R, which is L̄/2. Above 1 the output is smaller than the input.

Where the formula comes from

  1. Count runs rather than characters. In 0010111100001111 the neighbours differ in five places, so there are six runs and the row reads R=6.
  2. The encoded size is 2R and nothing else. Which symbols the runs were made of never enters the arithmetic — six runs cost twelve units whether they are pixels, letters or digits.
  3. Divide: ratio = N/2R = L̄/2. So the break-even sits at L̄ = 2, and it is exactly reachable — type AABB and the bars read 4 bytes in, 4 bytes out.
  4. The two directions are not symmetric. Upward there is no limit: a single run of a million characters encodes to one pair. Downward the floor is 0.50× and cannot be beaten, because the worst an input can do is give every character its own run.

How to read what you see

All four presets are exactly sixteen characters long, which makes them worth reading as a set. Image scanline has three runs and encodes to 6 bytes. Classic runs has four and gives 8. Bitmap mask has six and gives 12. Worst case has sixteen and gives 32. Same length in, and out comes anything from 6 bytes to 32 — a factor of five, settled entirely by R. Then type hello world: eleven characters, ten runs, 20 bytes out. Ordinary prose sits near the bottom of that range, which is the whole reason RLE is a component of compressors rather than one on its own.

Assumes
That a pair costs exactly 2 units, that a symbol and a count are the same width, and that a count can be any size. Real encoders give the count a fixed width — one byte, so 255 — and must split a longer run into several pairs, which raises the break-even slightly above 2. The equal-width assumption fails hardest on the data RLE is best at: in a 1-bit fax scan the symbol is one bit and the count is not.
Breaks when
The 0.50× floor is not a defect waiting to be engineered away. A lossless encoder has to be reversible, so distinct inputs must map to distinct outputs; and there are fewer short strings than long ones to map onto. Any scheme that makes even one input shorter therefore makes some other input longer. That is a counting fact, not a property of run-length encoding. PackBits, in the third insight above, pushes its worst case down to one control byte per 128 — under 1% — and that is as far as anyone can go, because the floor can be lowered without limit but never reached. What RLE does is wear the cost on the outside, in a readout you can watch move.

why the break-even point is exactly 2 🖖

Every run — no matter how long — costs the same 2 units to store: one for the symbol, one for the count. A run of length L is only worth encoding when that costs less than writing L raw characters — that is, when L is greater than 2. Averaged over the whole input, that condition becomes L̄ = N/R greater than 2, where N is the total length and R is the number of runs — the exact line the formula above checks. This is also why RLE is a poor general-purpose compressor: English text, source code, and random data rarely have runs longer than 2, so RLE is reserved for data engineered to have long runs on purpose — 1-bit fax scans, sparse bitmaps, and palette images with flat color fields. Real formats push the idea further: PNG runs a Paeth/Sub/Up delta filter over each scanline before compressing, turning smooth gradients into long runs of near-zero differences first — RLE (via DEFLATE) does the rest. Try the worst-case sample above: sixteen distinct characters have sixteen runs of length 1, so encoding needs 32 units to store 16 — the input doubles in size.

the compression you'd invent yourself 🖖

Run-length encoding is the one compression idea you could reinvent on your own: instead of spelling out WWWWWWW letter by letter, you just say "7 W's" — the same shortcut people use reading "triple seven" in a phone number. It scans the data in a single left-to-right pass and remembers nothing beyond the run it is currently counting, which makes it fast and easy to stream. And it is lossless: from the (symbol, count) pairs you can rebuild the original exactly, unlike JPEG or MP3, which throw detail away for good.

the RLE cousin that can't blow up 🖖

Naive RLE can double incompressible data, but Apple's PackBits variant — born in 1980s MacPaint and still a standard compression mode in TIFF — is engineered so it almost never expands. Each block starts with one signed control byte: a non-negative value means "the next bytes are literal," a negative one means "repeat the following byte." Unique data is copied verbatim in chunks of up to 128 bytes, so the worst case adds just one control byte per 128 — under 1% overhead instead of the 100% naive RLE can hit.

Problem solved in full

  1. Run-length encoding AAAAAABBBCCDDDDD into four pairs 5 steps

    Run-length encoding turns AAAAAABBBCCDDDDD into four pairs. Work out the compression, and then the exact condition under which this scheme makes a file bigger.

    1. The encoding is the obvious one: replace each run by the character and its length. Sixteen characters collapse to four pairs.

    2. Two numbers describe any input to this scheme — its length and its number of runs — and their ratio is the mean run length. Here it is 4.

    3. Now count honestly. Each pair costs two tokens, a character and a count, so the output is 2R against an input of N. Nothing else about the data matters.

    4. So the scheme wins exactly when 2R < N, which rearranges to a mean run length above 2. Here 8 against 16 — a clean halving — and the verdict line on the panel says the same thing in one symbol.

    5. Below that threshold it loses, and at a mean run length of 1 it loses maximally: every character becomes a pair, doubling the file.

    Answer

    The tool prints N = 16 and R = 4, a mean run of 4 and a 2× saving. The condition is the thing to keep: RLE compresses if and only if runs average more than two, and it is one of the few compression schemes whose break-even point is a single number you can check by eye. Type ABCD into the box and watch it expand to twice the size. That is not a flaw — it is why RLE survives only where runs are guaranteed by construction: fax scan lines, sparse bitmaps, and the flat regions of a JPEG after quantisation, never general text.

Learning path

Compression by hand

Leads to Huffman the idea in its plainest form: replace a run of identical symbols with the symbol and a count.

References (3)

· Updated

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Computing lessons →

Example problems

  • Classic runs - "AAAAAABBBCCDDDDD" → (A,6)(B,3)(C,2)(D,5) — 16 chars into 8 pairs
  • Worst case - "ABCDEFGHIJKLMNOP" — all unique chars, every pair is longer than original
  • Bitmap mask - "0010111100001111" — pixel row showing why PNG prefilters before RLE
  • Image scanline - "WWWWWWWBBBBBWWWW" — simple B&W image row, strong run structure