All subjects · Computer Science · WCP04 Advanced Practical Programming and Problem-solving

Implementing run-length encoding

Edexcel IAL Computer Science · WCP04 Advanced Practical Programming and Problem-solving

Run-length encoding (RLE) is a simple lossless compression method. It replaces each run of identical values with the value and a count, so 'AAAAB' becomes 4A1B. It works well on data with long runs, such as simple images, and you must implement and use it.

Practise this in the app: instant marking and a fix for every mistake. Free, no email needed to start.

Practise this lesson

How RLE works

Scan the data from the start, counting how many times the current value repeats.
When the value changes, store the (value, count) pair and start counting the new value.
At the end, store the final run: forgetting it is the most common bug.
Decoding repeats each value count times. RLE is lossless: decoding gives back exactly the original.

Python implementation

def rle_encode(text):
    if text == "":
        return []
    runs = []
    current = text[0]
    count = 1
    for ch in text[1:]:
        if ch == current:
            count = count + 1
        else:
            runs.append((current, count))
            current = ch
            count = 1
    runs.append((current, count))        # do not forget the final run
    return runs

def rle_decode(runs):
    return "".join(ch * count for ch, count in runs)

def runs_to_text(runs):
    return "".join(f"{count}{ch}" for ch, count in runs)

# rle_encode, rle_decode and runs_to_text as above

row = "WWWWWWBBBWWWWBW"
runs = rle_encode(row)
print(runs)
print(runs_to_text(runs), len(row), "->", len(runs_to_text(runs)))
print(rle_decode(runs) == row)

Output:

[('W', 6), ('B', 3), ('W', 4), ('B', 1), ('W', 1)]
6W3B4W1B1W 15 -> 10
True

Decoding a text format

If the encoded data is a string such as '12A3B1C', counts can have more than one digit, so you cannot just take alternate characters. A regular expression splits it cleanly into (count, character) pairs:

import re
def decode_text(code):
    return "".join(ch * int(n) for n, ch in re.findall(r"(\d+)(\D)", code))
print(decode_text("12A3B1C"))

Output:

AAAAAAAAAAAABBBC

When RLE helps

Good for data with long runs: black and white images, simple graphics, scanned documents.
Poor for data with few repeats: 'ABCD' becomes '1A1B1C1D', twice as long.
Lists of (value, count) pairs work for any values, such as pixel colours or numbers, not just letters.

Worked example

Encode the image row [0, 0, 0, 1, 1, 0, 0, 0, 0] as (value, count) pairs.

```python # rle_encode from the lesson works on lists too print(rle_encode([0, 0, 0, 1, 1, 0, 0, 0, 0])) ```
Output: ``` [(0, 3), (1, 2), (0, 4)] ```

Answer: Nine pixels become three pairs. Because the function only indexes, slices and compares, it works on lists as well as strings.

Key idea: Count each run; on a change store (value, count) and restart; store the final run; decode by repeating; lossless; great for long runs, worse than the original when there are no runs; use a regex to parse multi-digit counts.

Check yourself

Using the lesson's functions, what does this print? ```python def rle_encode(text): if text == "": return [] runs = [] current = text[0] count = 1 for ch in text[1:]: if ch == current: count = count + 1 else: runs.append((current, count)) current = ch count = 1 runs.append((current, count)) # do not forget the final run return runs def rle_decode(runs): return "".join(ch * count for ch, count in runs) def runs_to_text(runs): return "".join(f"{count}{ch}" for ch, count in runs) print(runs_to_text(rle_encode("AAABCCCCD"))) ```
Show answer
3A1B4C1D. Runs: AAA, B, CCCC, D. Output: `3A1B4C1D`
Using the lesson's functions, what does this print? ```python def rle_encode(text): if text == "": return [] runs = [] current = text[0] count = 1 for ch in text[1:]: if ch == current: count = count + 1 else: runs.append((current, count)) current = ch count = 1 runs.append((current, count)) # do not forget the final run return runs def rle_decode(runs): return "".join(ch * count for ch, count in runs) def runs_to_text(runs): return "".join(f"{count}{ch}" for ch, count in runs) print(rle_decode([("x", 3), ("y", 1), ("x", 2)])) ```
Show answer
xxxyxx. Repeat each character by its count. Output: `xxxyxx`
Using the lesson's functions, what does this print? ```python def rle_encode(text): if text == "": return [] runs = [] current = text[0] count = 1 for ch in text[1:]: if ch == current: count = count + 1 else: runs.append((current, count)) current = ch count = 1 runs.append((current, count)) # do not forget the final run return runs def rle_decode(runs): return "".join(ch * count for ch, count in runs) def runs_to_text(runs): return "".join(f"{count}{ch}" for ch, count in runs) print(len(rle_encode("aabbbaaaab"))) ```
Show answer
4. Runs: aa, bbb, aaaa, b gives `4` pairs. The two runs of a are separate because b comes between them.
Using the lesson's functions, what does this print? ```python def rle_encode(text): if text == "": return [] runs = [] current = text[0] count = 1 for ch in text[1:]: if ch == current: count = count + 1 else: runs.append((current, count)) current = ch count = 1 runs.append((current, count)) # do not forget the final run return runs def rle_decode(runs): return "".join(ch * count for ch, count in runs) def runs_to_text(runs): return "".join(f"{count}{ch}" for ch, count in runs) s = "ABCDE" print(len(runs_to_text(rle_encode(s))) - len(s)) ```
Show answer
5. With no repeats every character becomes '1' plus the character: 10 characters instead of 5, so it is `5` characters longer.
decode_text is the function from the lesson. What does this print? ```python import re def decode_text(code): return "".join(ch * int(n) for n, ch in re.findall(r"(\d+)(\D)", code)) print(len(decode_text("10W2B")), decode_text("3x1y")) ```
Show answer
12 xxxy. '10W' is ten Ws, so the first decode has 12 characters; '3x1y' decodes to xxxy. Output: `12 xxxy`
A student's rle_encode returns [('A', 3), ('B', 2)] for 'AAABBC'. What is the most likely bug?
- The count starts at 0 instead of 1
- The loop starts at index 0 instead of 1
- The final run is never appended after the loop ends
- It compares characters with = instead of ==
Show answer
The final run is never appended after the loop ends. The last run (C, 1) is only stored when the value changes, which never happens after the last character, so it must be appended after the loop.
Why is RLE described as lossless?
- Decoding gives back exactly the original data
- It always makes data smaller
- It removes repeated data permanently
- It only works on images
Show answer
Decoding gives back exactly the original data. No information is discarded; the counts allow exact reconstruction.
For which data would RLE give the best compression?
- A photograph with constantly changing colours
- A black and white diagram with large areas of a single colour
- A random string of letters
- An encrypted file
Show answer
A black and white diagram with large areas of a single colour. Long runs of identical values compress well; varied data does not.

Practise with instant feedback

Sources

Last updated 8 November 2026. Spotted a mistake? Tell us.