Run-length encoding replaces every maximal run of the same repeated symbol with a single
(count, symbol) pair. Scan the input once: while the next character matches the one
already being counted, extend the current run; the moment it doesn't, close the run out — record how
many characters it covered and what they were — and start a new run at the character that broke the
match. There's nothing to buffer across runs and nothing to decide two steps ahead: each run is found
and emitted in the same single step. Decoding just replays each pair, writing its symbol that many
times back out, in order.
This is the Compression category's second entry. LZW Compression, the first, builds an adaptive dictionary that can reference a repeated substring anywhere earlier in the message, even if the only earlier occurrence is nowhere near the current position. RLE can only ever look at the character immediately to its left — it has no memory of anything outside the run currently being counted. That's a real, measured limitation, not just an opinion: see Pitfalls below for exactly where each approach wins by a wide margin, on the same inputs, and where each one loses.
Type a message and press Load, then Step or Run.
Each step finds one maximal run — the highlighted cells below show the span it covers — and adds it to
the list of emitted (count, symbol) pairs. The default message mixes run lengths (3, 5, 2,
5) so the mechanism is visible at a glance; see Pitfalls for inputs where this same mechanism makes the
message bigger instead of smaller.
input (current run highlighted)
runs emitted, in order (count×symbol)
On the default message aaabbbbbccddddd (15 characters, alphabet
{a, b, c, d}, so each symbol needs ⌈log₂4⌉ = 2 bits): the scan starts at the
first a and keeps counting while the next character is also a — three in a
row, then a b breaks the match. Close out the run: (3, a). Restart counting
at b; five bs in a row before c breaks it:
(5, b). Two cs: (2, c). Five ds to the end of the
message: (5, d). Four runs — 3a, 5b, 2c, 5d — cover all fifteen characters.
The longest run found is 5, so every run's count needs ⌈log₂6⌉ = 3 bits to be
representable (a scheme that doesn't know the input in advance only commits to this width after seeing
all of it — see Pitfalls for what a format that commits before seeing the data has to do
instead). Four runs × (2-bit symbol + 3-bit count) = 20 bits, against a
30-bit fixed-width baseline (15 characters × 2 bits each) — a real 33% saving, and the
shortest version of why RLE works at all: pay a small per-run fee once, instead of paying the full
per-character symbol cost every single time a symbol repeats.
Round-trip tested with a 20,000-trial fuzz test (random strings, alphabet size 1–4, length 1–30 — the same harness convention LZW's own page uses) — zero mismatches. Unlike LZW's decoder, this one never has to special-case a code it hasn't seen the definition of yet: every run already carries its own count and symbol, with no shared, order-dependent dictionary state that the encoder and decoder could ever fall out of sync on.
function rleEncode(input) {
const runs = [];
let i = 0;
while (i < input.length) {
let j = i;
while (j < input.length && input[j] === input[i]) j++;
runs.push({ char: input[i], count: j - i });
i = j;
}
return runs;
}
function rleDecode(runs) {
let out = '';
for (const { char, count } of runs) out += char.repeat(count);
return out;
}
Measured, not estimated — bits packed at the narrowest fixed width each scheme
could actually use for the given input (same convention LZW's own
page uses for its code widths), against a fixed-width baseline of ⌈log₂(alphabet size)⌉
bits per character:
| input | runs | RLE bits | fixed-width bits | LZW bits |
|---|---|---|---|---|
ABABABABA | 9 | 18 | 9 | 11 |
abracadabra | 11 | 44 | 33 | 32 |
mississippi | 8 | 32 | 22 | 30 |
aabbccddeeffgghhiijj | 10 | 60 | 80 | 93 |
aaaaabbbbbccccc | 3 | 15 | 30 | 28 |
50×a | 1 | 7 | 50 | 26 |
No adjacent repeats means the encoding gets bigger, not smaller. RLE's worst case is
any input where no two identical characters ever sit next to each other — every run then has length 1,
and the per-run symbol-plus-count overhead is paid for nothing in return.
ABABABABA — the same classic example LZW's own
page uses for its own worst case — costs 18 bits here against a 9-bit
fixed-width baseline, exactly double. abracadabra — the
Huffman Coding page's own default example — has real
repeated letters (a five times, r and b twice each) but never two
of the same letter adjacently, so RLE still expands it 33% (44 vs. 33 bits) while LZW, which can see a
repeat anywhere earlier in the message rather than only immediately to the left, actually compresses
the exact same input (32 bits). mississippi is similar: its only adjacent repeats are the
doubled ss and pp, nowhere near enough to pay back the per-run overhead
elsewhere, so both algorithms expand it — but LZW's whole-history view still does measurably less
damage (30 vs. 32 bits).
RLE sees only adjacency; LZW sees the whole history — and each wins decisively in a
different regime. aabbccddeeffgghhiijj (ten adjacent pairs across a ten-letter
alphabet) is the mirror image of the row above: RLE's ten small, cheap runs cost 60 bits, beating the
80-bit fixed baseline comfortably, while LZW — spending code space rebuilding dictionary entries for
pairs it will mostly never see repeated — actually costs more than doing nothing at all (93
bits). The gap widens further on one long uninterrupted run: fifty repeats of the same character cost
RLE a single 7-bit pair, a 7x improvement on the 50-bit baseline, while LZW needs 26 bits to get there —
RLE wins by very close to 4x over LZW on exactly the input shape RLE is built for. Neither algorithm is
simply better than the other; they're tuned for different kinds of redundancy, and a real compressor
that has to handle unknown input (most general-purpose formats, e.g. PNG's filtering step before its own
LZ-family compressor) often runs something like RLE as a cheap first pass specifically to catch the
long-run case before a heavier, LZW-like stage looks for everything else.
A real format can't peek ahead the way this page's own numbers do. The bit counts above all pick the narrowest count field that fits after scanning the whole message — a real streaming format has to commit to a field width before it has seen any of the data. Byte-oriented RLE schemes (PackBits, the RLE variant inside BMP) commonly reserve a fixed 8 bits for the count field, enough for a run of up to 255. A run longer than that can't be represented in one pair at all — the encoder has to split it into multiple consecutive pairs of the same symbol (a run of 300 identical bytes becomes two pairs, say 255 and 45), each paying the full per-run symbol-plus-count cost over again. Not a bug — a direct, unavoidable consequence of committing to a width before seeing the data — but worth knowing before assuming this page's own after-the-fact narrowest-width convention describes how a real-world encoder actually budgets its bits.
Time: O(n) to encode — a single linear scan, one comparison per
character, regardless of how the runs break up. O(n) to decode, symmetric to encode: the
total number of characters written back out is exactly the original message length, however many runs
it took to describe it. Space: O(r) for the output, where r
is the number of runs found — bounded by n in the worst case, exactly the no-adjacent-
repeats case named in the first Pitfall above, where r = n and the encoding can't be any
smaller than one pair per original character. No dictionary to build, size, or cap the way
LZW needs (see its own Pitfalls for the cap-and-reset-rule problem
that creates) — RLE's only working state beyond the output list itself is the single run currently
being counted.
See Choosing a Compression Approach for how this entry compares against the site's other six — short version: reach for RLE only when the redundancy is adjacent, per the table above.