skip to content

Run-length encoding replaces repeats with count-symbol pairs, so on what input does it make the output larger?

level: juniorimportance: must knowfreq 66%

answer

  1. depends on how often symbols repeat
  2. count plus symbol costs two bytes
  3. a run of one costs double
  4. break-even at average run length two
  5. alternating input doubles the output

basics

~20 s

Run-length encoding expands any input whose symbols rarely repeat: a single symbol still costs a count plus the symbol, so alternating bytes double in size. It pays only when the average run is longer than one pair.

solid answer

~40 s

Run-length encoding rewrites a stream as `(count, symbol)` pairs. With a one-byte count and a one-byte symbol a pair costs 2 bytes, so a run of length one costs twice what the raw symbol cost. A monochrome scan line of 640 identical pixels collapses beautifully: with the count capped at 255 you emit three pairs, `(255,w)(255,w)(130,w)`, six bytes instead of 640. Feed the same encoder `ABABABAB` and every run has length one, so you get eight pairs — 16 bytes for 8. The break-even is an average run length equal to the pair width in symbols, which is two here. That is why real formats guard the encoder: a literal-span marker, or a per-block flag that stores the block raw when encoding grew it.

code

pseudocode · 10 lines
pseudocode
i = 0
while i < length(input):
    run = 1
    while i + run < length(input)
          and input[i + run] == input[i]
          and run < 255:
        run = run + 1
    emit(run)
    emit(input[i])          # two bytes, even when run == 1
    i = i + run

go deeper

for a junior

Recall the shape of the output — a count and a symbol per run — and the one-line consequence: data that does not repeat gets bigger, roughly doubling when every run has length one.

for a middle

Explain the break-even. A pair costs two bytes and covers one run, so the encoder wins only above an average run length of two, and the count's fixed width forces long runs to split.

for a senior

Show the operational guard: measure the encoded block against the raw block, keep the smaller, and record the choice. Know which payloads genuinely carry runs and which, such as already-compressed bytes, never will.

for a principal

Frame it as a stage, not a compressor. The judgment is whether a cheap repetition-only pass earns its place ahead of a general coder for a given payload class, given the expansion risk on everything else.

## What the encoder actually emits Run-length encoding is the simplest lossless scheme there is. Walk the input, count how many times the current symbol repeats **consecutively**, emit that count followed by the symbol, and continue from the first symbol that differs. Decoding is the mirror image: read a count, read a symbol, write the symbol that many times. It carries **no model** of which symbols are likely. It exploits exactly one kind of redundancy — adjacent repetition — and is blind to every other kind. Two consequences follow immediately: - A **run of length one still costs a whole pair**. With a one-byte count and a one-byte symbol that is 2 bytes spent to represent 1 byte of input. - The **count field has a fixed width**, so any run longer than that field's maximum must be split across several pairs. ## The break-even arithmetic Let `p` be the pair width in bytes (count plus symbol) and `r` the average run length in symbols. The encoder emits roughly `n/r` pairs for `n` input symbols, so the output is about `(n/r) * p` bytes against `n` raw. The encoder wins when `r > p`, breaks even at `r = p`, and loses below it. With a one-byte count and a one-byte symbol, `p = 2`: an average run of two is the knife edge. | Input | Raw bytes | Run-length output | Outcome | |---|---|---|---| | 640 identical pixels | 640 | 6 — `(255,w)(255,w)(130,w)` | about 1% of raw | | `AAAB` | 4 | 4 — `(3,A)(1,B)` | no change | | `ABABABAB` | 8 | 16 — eight pairs | doubled | | uniformly random bytes | n | about 2n | doubled | The random-byte row is the honest worst case and it is not a corner case: with 256 equally likely symbols the chance that the next byte repeats the current one is 1/256, so the expected run length is barely above one and essentially every pair covers a single symbol. ## Where the worst case actually bites The inputs an engineer meets most often sit near that worst case. Ordinary prose, compiled instruction streams and structured text all have average run lengths close to one. **Already-compressed bytes are the sharpest trap**: a good coder has removed exactly the long runs the encoder is hunting, so re-encoding it is pure expansion. Run-length encoding is therefore applied where runs are known in advance to exist: - bilevel raster scan buffers, where a scan line crosses long stretches of one colour; - sparse bitmaps and occupancy maps dominated by one value; - padding regions and long spans of zero bytes inside a fixed-layout record; - the output of an earlier stage that has been arranged to produce runs. ## The guards real formats carry 1. **A store-raw escape per block.** The encoder compresses a block, compares the result against the input, and if the result is larger it emits a flag meaning "this block is literal". That caps the damage at the flag itself rather than at 100% growth. 2. **Literal spans.** A marked span saying "the next k symbols are not encoded" lets isolated symbols cost about one byte each plus an amortised marker, instead of two bytes each. 3. **Splitting on the count's width.** A run of 640 with a one-byte count becomes 255, 255 and 130 — the encoder must handle the split, and the decoder must tolerate two adjacent pairs carrying the same symbol. 4. **Implied alternation.** When only two symbols exist and runs alternate by construction, the symbol is not stored at all: you store the first colour once and then nothing but lengths, halving the per-pair cost. ## What it leaves on the table Even where run-length encoding wins outright, it does not touch the distribution of what it produces. Run lengths are themselves far from uniform — short runs are much more common than long ones — and the count bytes it emits are ordinary symbols with an ordinary skew. That residual redundancy belongs to an entropy coder placed behind it, which is why run-length encoding appears in practice as one stage of a pipeline rather than as a whole compressor. Ecosystems differ in where they expose it — some formats offer it as a standalone mode, others only as one token type inside a larger scheme — but the arithmetic above is the same in every one of them.

  • How do real formats stop a run-length stage from inflating a block?
    They compare the encoded block against the raw block and keep whichever is smaller, recording the choice in a per-block flag. Some also carry a literal-span token so isolated symbols cost about one byte each instead of a full pair. Both cap the worst case at a few bits of overhead rather than doubling.
  • Why can a bilevel scan line store lengths only, with no symbols at all?
    With two symbols, adjacent runs must alternate by construction — a run of white can only be followed by a run of black. So the symbol carries no information beyond the first one: you store the starting colour once and then a sequence of lengths, which roughly halves the per-run cost.
  • Why does re-running the encoder over its own output usually make things worse?
    The first pass removed the adjacent repetition, so the second pass sees counts and symbols interleaved with almost no runs. Average run length is back near one, and every symbol costs a fresh pair. Repeated application of a transform is not cumulative gain; it is a reliable way to expand.

saying these in an interview costs you the question

  • Claims run-length encoding always shrinks data, never expands it.
  • Thinks the worst case is merely no gain rather than growth.
  • Applies it to already-compressed bytes and expects a win.
  • Forgets the count field has a maximum, so long runs split.
  • Believes it models symbol frequencies the way an entropy coder does.