Run-Length Encoding, in depth: byte formats from pairs to PackBits, worst-case expansion, hostile input, RLE inside real formats and run-aware queries

When run-length encoding pays

RLE models data as a sequence of runs (value, length). If n values form r runs, the output is roughly r × (bytes per value + bytes per count). It wins when the average run length n/r is comfortably above the cost of storing a count, and loses when it is not. That is the whole theory, and it has a sharp consequence: RLE only exploits adjacency. The string "ABABAB..." is extremely predictable, yet every run has length 1 and RLE expands it. A general compressor would shrink it to almost nothing.

So the engineering question is rarely "which RLE format?" and usually "how do I create runs?". Sorting a table by a low-cardinality column turns a million status values into a handful of runs. The Burrows-Wheeler transform followed by move-to-front turns repeated contexts in text into runs of zeros. Bitmaps of mostly-blank documents already arrive that way. RLE is the cheap final stage after a transform has done the modelling.

Byte formats for the same runs

The same runs can be laid out in bytes several ways. Three common ones:

• Count-value pairs. Every run is emitted as (count, value), with the count in 1..255 and longer runs split. This format is trivial to write and decode, but a run of length 1 costs two bytes, so data without runs doubles in size.
• Escape or sentinel. Literal bytes are copied through, and a reserved escape byte introduces (escape, count, value). Runs of length 1 cost nothing extra, but the escape byte must itself be escaped whenever it appears in the data.
• PackBits (from the Macintosh, and one of the TIFF compression schemes). A signed header byte h is read first. For 0 ≤ h ≤ 127, the next h + 1 bytes are copied literally. For −127 ≤ h ≤ −1, the next byte is repeated 1 − h times. The value −128 is a no-op. Literal stretches pay one header byte per 128 bytes, which bounds the worst case at about 0.8% growth.

Segmentation masks use a fourth layout. Because there are only two values, the values are left implicit: the counts simply alternate between background and foreground, starting with background, so a mask that begins with foreground starts with a count of 0.

A tested PackBits encoder and decoder

A PackBits encoder and a defensive decoder. The encoder emits a repeat block for any run of three or more, since a run of two costs the same either way, and it ends literal blocks just before a run starts. The decoder rejects truncated input and enforces an output limit:

def packbits_encode(data: bytes) -> bytes:
    out, i, n = bytearray(), 0, len(data)
    while i < n:
        j = i
        while j < n and data[j] == data[i] and j - i < 128:
            j += 1
        if j - i >= 3:                         # repeat block, header 1-run as signed byte
            out += bytes(((257 - (j - i)) & 0xFF, data[i]))
            i = j
            continue
        start = i                              # literal block: stop before a run of 3
        while i < n and i - start < 128:
            if i + 2 < n and data[i] == data[i + 1] == data[i + 2]:
                break
            i += 1
        out.append(i - start - 1)              # header 0..127: copy header+1 bytes
        out += data[start:i]
    return bytes(out)

def packbits_decode(enc: bytes, limit: int) -> bytes:
    out, i = bytearray(), 0
    while i < len(enc):
        h = enc[i]; i += 1
        if h < 128:
            if i + h + 1 > len(enc):
                raise ValueError("literal runs past end of input")
            out += enc[i:i + h + 1]; i += h + 1
        elif h > 128:
            if i >= len(enc):
                raise ValueError("repeat header without value")
            out += enc[i:i + 1] * (257 - h); i += 1
        # h == 128: no-op
        if len(out) > limit:
            raise ValueError("output exceeds limit")
    return bytes(out)

Both functions round-tripped 3,000 random strings drawn from a skewed alphabet and the six inputs below. The count-value pair encoder (not shown) is ten lines long and was tested the same way.

Measured sizes

Sizes for 100,000-byte inputs (ratio is output divided by input):

Three lessons. First, on data without runs, pairs double the size while PackBits grows by 0.8%: the worst case is a property of the format, so choose the format with it in mind. Second, the repeated paragraph is highly redundant, yet neither encoder helped, because its redundancy is long-range repetition, which is LZ77's job and not RLE's. Third, on long runs, pairs beat PackBits two to one. A pair can describe up to 255 bytes and a PackBits repeat block only 128, so formats built for long runs use variable-length counts instead of a fixed byte.

Hostile input

A decoder is an amplifier. Two PackBits bytes produce 128, two pair bytes produce 255, and formats with varint counts let a few bytes claim gigabytes. Treat every encoded stream as untrusted:

• Know the expected output size (image dimensions, row count, page header) and stop at it. Never allocate from a count you have not checked against it.
• Reject truncated streams explicitly instead of reading past the buffer. In C this is the classic heap overread.
• Reject zero-length runs where the format forbids them, and reject counts that overflow your integer type when multiplied by the element width.
• Fuzz the decoder. Random bytes are a decent corpus for RLE because nearly every byte string is a syntactically valid stream.

RLE inside real formats

bzip2 uses RLE twice. An initial stage collapses runs of 4 to 255 identical bytes into four copies followed by a count byte (0 to 251). After the BWT and move-to-front, runs of the symbol zero are written in a bijective base-2 code using two symbols, RUNA and RUNB, before Huffman coding. Group 3 fax codes each scan line as alternating white and black run lengths, starting with a white run (which may be zero), and Huffman-codes the lengths, so long white margins cost a few bits.

Parquet stores definition and repetition levels and dictionary indices with an RLE/bit-packing hybrid. Each run starts with a ULEB128 varint header. If the low bit is 0, the header shifted right by 1 is a repeat count, followed by the value in ceil(bit_width / 8) little-endian bytes. If the low bit is 1, the header shifted right by 1 is a number of groups of eight values, bit-packed. Runs and literal stretches thus share one stream, the same idea as PackBits at bit granularity. For how the other encodings fit around it, see columnar database architecture.

COCO-style masks store binary masks as alternating counts in column-major (Fortran) order, starting with background. A 4 × 6 mask with a 2 × 3 rectangle at rows 1-2, columns 1-3 encodes as [5, 2, 2, 2, 2, 2, 9]. The area is the sum of the odd-position counts (6), computed without materialising the mask. Reading pixels in row-major order is the most common mask bug. Segmentation model serving covers where this encoding sits in an inference pipeline.

Querying runs without decompressing

Run-encoded data can be queried without expanding it, which is where columnar engines get much of their speed. Keep the run values and a prefix sum of run ends. A point lookup then becomes a binary search, and aggregates touch each run once:

import bisect
from itertools import groupby, accumulate

class RunColumn:
    def __init__(self, values):
        self.vals, lens = [], []
        for v, g in groupby(values):
            self.vals.append(v); lens.append(sum(1 for _ in g))
        self.ends = list(accumulate(lens))     # exclusive end of each run

    def __getitem__(self, i):                  # O(log r)
        return self.vals[bisect.bisect_right(self.ends, i)]

    def sum(self):                             # O(r), not O(n)
        total, start = 0, 0
        for v, e in zip(self.vals, self.ends):
            total += v * (e - start); start = e
        return total

A sorted column of 1,000,000 integers in 0..99 collapsed to 100 runs. Its sum, a count of rows equal to 42 (10,044), and any random access each touched at most 100 runs. The same structure underlies run containers in Roaring bitmaps, which intersect and union runs directly.

Operational guidance

• Measure average run length first. Compute n/r on a real sample. Below about 2 for byte data, RLE will not pay; look at delta encoding or a dictionary instead.
• Create runs on purpose. Sort or cluster by low-cardinality columns before writing, and order sort keys from lowest to highest cardinality.
• Pick the format by worst case. If inputs can be incompressible, use a format with literal blocks (PackBits, Parquet hybrid) rather than pairs.
• Layer it. RLE in front of an entropy coder (as in fax and bzip2) captures both the runs and the skewed distribution of their lengths.
• Keep runs queryable. If you will filter or aggregate, store run ends or lengths where the reader can use them, not inside an opaque compressed blob.

Failure modes

• Expansion: pairs over random or text-like data double the size.
• Decompression bombs: unchecked counts allocate huge buffers.
• Off-by-one headers: PackBits literal headers mean h + 1 bytes, and repeat headers mean 1 − h copies. Mixing these up shifts every following byte.
• Order mismatch: masks encoded column-major but decoded row-major give transposed garbage that still has the right area.
• Mishandling the no-op header: a PackBits decoder that treats 0x80 (−128) as a repeat header misreads every byte after it. The decoder above skips it, as the format requires.

Trade-offs

What to do next

1. Implement pairs and PackBits, and round-trip them against random strings from a small alphabet.
2. Reproduce the table on your own data, and compute n/r before choosing RLE.
3. Add an output limit and truncation checks to the decoder, then fuzz it for an hour.
4. Decode one real Parquet level stream or one COCO mask by hand to check your reading of the layout.
5. Sort one table by its lowest-cardinality column and measure the change in run count.
6. Implement run-aware sum and lookup, and compare them with expanding the column first.