Run-Length Encoding

Run-length encoding compresses runs of a repeated value into a single value and a count.

The idea

When the same symbol repeats many times in a row, run-length encoding (RLE) stores it once with a count instead of writing it out. The string AAAAABBB becomes something like 5A3B.

When it helps

Kronos motion — number counters

RLE excels on data with long uniform runs: simple graphics with flat color regions, scanned black-and-white documents, and bitmap masks. Fax machines and the BMP and TGA image formats use forms of it.

When it hurts

On data without runs, RLE can expand the input, since each single symbol may need a count too. Practical schemes add an escape mechanism so isolated symbols are stored plainly and only runs are encoded.

As a stage in bigger codecs

RLE rarely stands alone in modern compressors. It commonly follows a transform that creates runs — for instance, JPEG applies RLE to long stretches of zero coefficients produced after quantization and zig-zag ordering.

Variants

Beyond the basic value-count form, variants encode only the lengths of alternating runs (useful for binary images) or combine RLE with entropy coding of the counts to squeeze out further redundancy.

python

def rle_encode(s):
    out = []
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:
            j += 1
        out.append((s[i], j - i))
        i = j
    return out
print(rle_encode('AAAAABBB'))  # [('A',5),('B',3)]