Cairn
algorithms · compression · O(n) encode, O(n) decode — n = input length

↩ back to Compression

Run-Length Encoding

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.

Try it

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)

Press Load.

Why it works

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.

Reference implementation

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;
}

Pitfalls

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:

inputrunsRLE bitsfixed-width bitsLZW bits
ABABABABA918911
abracadabra11443332
mississippi8322230
aabbccddeeffgghhiijj10608093
aaaaabbbbbccccc3153028
50×a175026

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.

Complexity

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.