Run Length Encoding in Python (Encode and Decode)

Run length encoding in Python replaces each run of repeated characters with a count and the character, so "AAABBB" becomes "3A3B". The shortest version uses itertools.groupby:

from itertools import groupby
"".join(f"{len(list(g))}{ch}" for ch, g in groupby("AAABBBCCDAA"))   # '3A3B2C1D2A'

Every encoder and decoder below was run on Python 3.12.5 with a round-trip check, so you can trust that the output decodes back to the input.

I’ll build an encoder with a plain loop, a shorter one with groupby, a decoder with regex, fix the bug that appears when the data contains digits, and measure when RLE actually saves space.

Run length encoding with a for loop

You walk the string, count how many times the current character repeats, and write the count and character when the run ends. The last run needs an extra append after the loop:

def rle_encode(text):
    if not text:
        return ""
    out = []
    current, count = text[0], 1
    for ch in text[1:]:
        if ch == current:
            count += 1
        else:
            out.append(f"{count}{current}")
            current, count = ch, 1
    out.append(f"{count}{current}")           # don't forget the last run
    return "".join(out)

for s in ["AAABBBCCDAA", "WWWWWWWWWWWWBWWWW", "ABC", ""]:
    print(f"{s!r:<22} -> {rle_encode(s)!r}")

Output:

'AAABBBCCDAA'          -> '3A3B2C1D2A'
'WWWWWWWWWWWWBWWWW'    -> '12W1B4W'
'ABC'                  -> '1A1B1C'
''                     -> ''

Forgetting the final append is the classic RLE bug: the last run silently disappears. For loops like this, see the Python for loop guide.

Run length encoding with itertools.groupby

groupby() groups consecutive equal items for you, which is exactly what RLE needs. Each group is an iterator, so take its length with len(list(...)) or sum(1 for _ in ...):

from itertools import groupby

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

def rle_pairs(text):
    return [(ch, sum(1 for _ in group)) for ch, group in groupby(text)]

print(rle_encode("AAABBBCCDAA"))
print(rle_pairs("AAABBBCCDAA"))

Output:

3A3B2C1D2A
[('A', 3), ('B', 3), ('C', 2), ('D', 1), ('A', 2)]

Note that groupby only groups neighbors; the two A’s at the end form their own run. That’s correct for RLE, and it’s why you shouldn’t sort the data first.

Decoding run length encoded strings

A regular expression splits the encoded string into (count, character) pairs. Repeat each character count times and join them back together:

import re
from itertools import groupby

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

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

for original in ["AAABBBCCDAA", "WWWWWWWWWWWWBWWWW", "xyz"]:
    packed = rle_encode(original)
    back = rle_decode(packed)
    print(f"{original:<18} -> {packed:<10} -> {back:<18} round trip ok: {back == original}")

print(rle_decode("12W1B4W"))

Output:

AAABBBCCDAA        -> 3A3B2C1D2A -> AAABBBCCDAA        round trip ok: True
WWWWWWWWWWWWBWWWW  -> 12W1B4W    -> WWWWWWWWWWWWBWWWW  round trip ok: True
xyz                -> 1x1y1z     -> xyz                round trip ok: True
WWWWWWWWWWWWBWWWW

(\d+) handles counts of 10 or more, like the 12 W’s. More on patterns in Python replace with regular expression.

Why does run length encoding break with digits?

If the data itself contains digits, the simple text format becomes ambiguous: "3112" could mean several different things. Keeping (character, count) pairs avoids the problem:

from itertools import groupby

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

print(rle_encode("1112"))                 # '3112' -- three 1s, one 2... or 3, 1, 1, 2?

def rle_encode_safe(text):
    return [(ch, len(list(g))) for ch, g in groupby(text)]       # keep pairs, no ambiguity

def rle_decode_safe(pairs):
    return "".join(ch * n for ch, n in pairs)

pairs = rle_encode_safe("1112")
print(pairs, "->", rle_decode_safe(pairs))

Output:

3112
[('1', 3), ('2', 1)] -> 1112

You could also add a separator between runs, or escape digits; I prefer the pairs. Real formats such as PackBits and BMP RLE use byte-level headers for the same reason.

When does RLE actually compress data?

In my tests, RLE only helped when the data had long runs. On typical text it makes things bigger, because every single character becomes two:

from itertools import groupby

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

samples = {
    "bitmap row": "0" * 40 + "1" * 8 + "0" * 40,
    "DNA-like": "AAAAAAAACCCCGGGGGGGGGGTTTT" * 4,
    "normal English": "Run length encoding works best on repetitive data.",
}
for name, s in samples.items():
    packed = rle_encode(s)
    print(f"{name:<15} {len(s):>3} chars -> {len(packed):>3} chars  ({len(packed) / len(s):.0%} of original)")

Output:

bitmap row       88 chars ->   8 chars  (9% of original)
DNA-like        104 chars ->  36 chars  (35% of original)
normal English   50 chars -> 100 chars  (200% of original)

That’s why RLE shows up in simple image formats, fax machines and bitmap fonts, while general-purpose compression uses smarter algorithms like zlib. Compare collections in list vs set in Python if you’re choosing structures for the pairs.

More algorithm practice in Python:

• Insertion sort in Python
• Breadth first search in Python
• Python for loop in one line
• Reverse a string in Python

Frequently asked questions