Run-length encoding

Cost and properties

time	O(n), one pass
best case	huge — bitmaps, fax
worst case	expands the input
lossless	yes

Reference: Sedgewick & Wayne, §5.5.

Run-length encoding in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

def compress(s):
    # Replace each maximal run of identical symbols by (symbol, length).
    out, i = [], 0
    while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:  # measure the run
            j += 1
        out.append((s[i], j - i))
        i = j
    return out

def expand(pairs):
    return ''.join(sym * count for sym, count in pairs)

Why it works

Where it wins

A black-and-white bitmap is mostly long runs of one colour, so run-length encoding is dramatic there — it is the core of fax transmission (ITU G.3/G.4), of the classic .bmp RLE mode, and of the run-length step inside TIFF and PDF. On typical English text it barely helps, because runs of length 3+ are rare.

Every compressor fails on something

The no runs preset produces output twice the size of the input. This is unavoidable: there are fewer short bit strings than long ones, so no lossless scheme can shrink every input — a counting argument, not an engineering limitation. Real formats therefore include an escape or “stored” mode: if compression would expand the block, emit it raw with a flag.

The bit-level version

The course's version works on bits, where there are only two symbols so the symbol itself need not be stored — only the run lengths, alternating, starting with a run of 0s. Each length gets a fixed number of bits (say 8), and a run longer than 255 is emitted as 255, then a zero-length run of the other bit, then the remainder. That zero-length run is the kind of detail that only shows up when you implement it.

What comes next

RLE exploits one kind of redundancy: repetition of adjacent symbols. Huffman exploits a different one — uneven symbol frequencies. LZW exploits a third — repeated phrases, anywhere. Real formats stack them: DEFLATE (zip, gzip, PNG) runs an LZ77 phase and then Huffman-codes the result.

What to try in the animation

Try the no runs preset: the output is longer than the input. Every compression scheme has inputs it makes worse — that is a theorem, not a bug.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• long runs — aaaaaabbbbccccccccccddaaaaaaaa
• a bitmap row — 0000000011111111111100000000001111
• no runs (expands!) — abcdefghij
• one giant run — aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Open Run-length encoding in the player →

The rest of Data compression

• Huffman compression Merge the two least frequent symbols, repeatedly.
• LZW compression Emit the code for the longest known phrase, then learn that phrase plus one more character.