Run-Length Encoding

Imagine transmitting a fax. Most of the page is white. A typical line might be 300 white pixels, then 20 black pixels, then 280 more white. Sending each pixel as a single bit costs 600 bits. But why not just say "300 white, 20 black, 280 white"? That takes fewer than 20 characters — a 10× saving for that line alone.

That idea is Run-Length Encoding (RLE): scan the input left to right, group consecutive identical symbols into runs, and replace each run with a (symbol, count) pair. The output can be far shorter whenever the data contains long flat stretches.

RLE was formalized in the early days of digital communication and is provably optimal for a specific class of source models — geometric distributions over run lengths — which is exactly what you get with bilevel (black-and-white) images. It is also the simplest possible lossless scheme: encoding and decoding are both a single linear scan, requiring no lookups, no trees and no arithmetic. The complexity of Huffman coding grows from here.

Click cells in the grid below to toggle them between white and black. RLE reads each row left to right and encodes every run of identical pixels as (color, count). Watch the encoded output update live as you draw.

<p class="hint">{{hint}}</p>
<canvas id="grid" width="320" height="320"></canvas>
<div class="controls">
  <button id="clear" type="button" class="ghost">{{btn_clear}}</button>
  <button id="fill" type="button" class="ghost">{{btn_fill}}</button>
  <button id="checker" type="button" class="ghost">{{btn_checker}}</button>
</div>
<div class="stats" id="stats"></div>
<div class="output-wrap">
  <div class="output-label">{{output_label}}</div>
  <div id="output" class="output"></div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
canvas { display: block; border: 1.5px solid #adb1b8; border-radius: 6px;
         cursor: crosshair; touch-action: none; }
.controls { display: flex; gap: .5rem; margin: .6rem 0 .4rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .38rem .8rem; border-radius: 7px;
         border: 1.5px solid #1d3557; cursor: pointer; }
button:not(.ghost) { background: #1d3557; color: #fff; }
button.ghost { background: #fff; color: #1d3557; }
.stats { font-size: .85rem; font-weight: 600; color: #555; margin-bottom: .5rem; min-height: 1.2em; }
.output-wrap { border: 1px solid #cdd9e3; border-radius: 6px; padding: .5rem .7rem;
               background: #f7f9fb; max-height: 160px; overflow-y: auto; }
.output-label { font-size: .78rem; font-weight: 700; color: #888; margin-bottom: .3rem;
                letter-spacing: .04em; text-transform: uppercase; }
.output { font: 13px/1.7 ui-monospace, monospace; color: #1d3557; word-break: break-all; }
.run-w { color: #888; }
.run-b { color: #1d3557; font-weight: 700; }

// Code not found

Notice how long unbroken stretches collapse to a single pair, while a checkerboard pattern actually grows — every pixel becomes its own run of length 1, and the encoding is twice as long as the original. That is the fundamental trade-off: RLE shines on data with large runs, and fails on data with high alternation.

RLE is one of the few compression algorithms whose theoretical properties are completely settled:

• Time complexity: $O(n)$. Both encoding and decoding make a single pass through the data. No preprocessing, no auxiliary data structures, no backtracking.
• Space complexity: $O(1)$ extra. Apart from the output buffer, only a current symbol and a counter are needed.
• Best case: high compression. A string of n identical symbols compresses to a single pair — $O(1)$ output — an arbitrarily large saving.
• Worst case: expansion. Alternating symbols (e.g., ABABAB…) produce one pair per symbol, roughly doubling the data. Standard implementations add a literal-copy escape to cap the overhead at around 2×.
• Information-theoretic optimality. For a source that produces runs whose lengths follow a geometric distribution with parameter p, RLE achieves entropy — the theoretical minimum — because the expected bits per run equal the entropy of that distribution. Real fax lines are very close to this model.
• Compared to Huffman and LZ. RLE ignores cross-run statistics; a sequence like AAABBBCCC could be compressed more by noting that A, B, C appear equally. Huffman coding and the LZ family exploit those patterns. RLE is a building block, not the final word.

The key insight is that RLE trades generality for simplicity. It is the right tool whenever the source statistics match its model, and an embarrassing one when they don't.

RLE's simplicity makes it a workhorse wherever the data has predictable structure:

• Fax transmission (ITU-T T.4 / T.6): the international Group 3 and Group 4 fax standards use modified Huffman and modified READ codes, both of which are RLE variants. A mostly-white A4 page at 200 dpi has ~3.4 million pixels; T.4 routinely squeezes it to under 50 KB.
• Bitmap images (BMP RLE4/RLE8, PCX, TGA): early PC formats stored paletted images with raw RLE. A 256-color splash screen with large flat areas could fit in tens of kilobytes where raw storage would need hundreds.
• PDF and PostScript streams: PDF uses a RunLengthDecode filter as one of its standard stream encodings for binary data with long repeated byte sequences.
• TIFF PackBits: the simplest TIFF compression mode is byte-level RLE, still in active use in print workflows.
• Preprocessing for stronger compressors: bzip2's preprocessing stage (Burrows–Wheeler + move-to-front) produces data with long runs that a subsequent RLE pass then removes before the final Huffman step.
• Video and display: early video game consoles used RLE for sprite and tile data storage; modern display protocols send run-compressed scanlines over limited-bandwidth links.

Anywhere data has spatial or temporal redundancy in the form of repeated values, RLE is the first tool to reach for — fast, provable, and needing no parameters to tune.

Run-Length Encoding is the smallest useful idea in data compression: scan once, count repeats, write a pair. Its $O(n)$ time, $O(1)$ space, and provable optimality on geometric sources make it the cleanest example of a compressor that exactly matches a statistical model.

It also teaches the central lesson of information theory: compression works by exploiting what you already know about the source. When the source is a fax page, long white runs are almost certain — and RLE can be counted on. When the source is encrypted data, every byte is equally surprising — and no compressor can help.

The next time you see a fax, a BMP file, or a console sprite, there is a good chance RLE is quietly folding the repetition away, one count at a time.