Run-Length Encoding (RLE)

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.

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.

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.