Run-length encoding in Python

Run-length encoding (RLE) stores each run of the same character as a count and the character: AAABBC becomes 3A2B1C. It is one of the simplest ways to compress data, and it works well when the data has long runs, such as rows of pixels in a simple image.

The program

import re


def rle_encode(text):
    if not text:
        return ""
    parts = []
    current = text[0]
    count = 1
    for ch in text[1:]:
        if ch == current:
            count += 1
        else:
            parts.append(f"{count}{current}")
            current = ch
            count = 1
    parts.append(f"{count}{current}")  # the last run has no character after it
    return "".join(parts)


def rle_decode(code):
    return "".join(ch * int(count) for count, ch in re.findall(r"(\d+)(\D)", code))


for text in ["AAABBBCCDDDDEE", "WWWWWWWWWWWWBWWW", "abc", ""]:
    code = rle_encode(text)
    print(f"{text!r} -> {code!r} -> {rle_decode(code)!r}")

'AAABBBCCDDDDEE' -> '3A3B2C4D2E' -> 'AAABBBCCDDDDEE'
'WWWWWWWWWWWWBWWW' -> '12W1B3W' -> 'WWWWWWWWWWWWBWWW'
'abc' -> '1a1b1c' -> 'abc'
'' -> '' -> ''

How it works

• rle_encode() remembers the current character and how many times in a row it has seen it. When a different character arrives, it saves the count and the character, then starts counting the new one.
• After the loop, the last run is still waiting, so one more append saves it. Forgetting this line is the most common bug in RLE code.
• re.findall(r"(\d+)(\D)", code) finds every pair of "one or more digits" and "one character that is not a digit". \d+ lets a count have more than one digit, so 12W decodes to twelve W characters.
• ch * int(count) repeats the character: "W" * 3 is "WWW".
• "abc" gets longer (1a1b1c). RLE only saves space when there are runs.

This format cannot store digits in the text itself: "111" encodes to "31", and rle_decode("31") gives "", because the pattern finds no letter after the digits. The original text is lost. Real formats store the count in a separate byte to avoid this.

Another way: itertools.groupby

itertools.groupby() splits a string into runs of the same character for you:

from itertools import groupby


def rle_encode(text):
    return "".join(f"{len(list(run))}{ch}" for ch, run in groupby(text))


print(rle_encode("AAABBBCCDDDDEE"))

3A3B2C4D2E