String Compression

The Idea

Run-length coding replaces a stretch of identical characters with the character and how many there were. Done in place it needs two cursors: read walks the runs, write lays the output down behind it. The write cursor can never catch up, because two characters are only ever replaced by two or fewer. Runs of one stay bare, and a count above nine is written one digit at a time.

Real-World Example

A screen recorder storing a row of identical pixels as "this grey, 240 times". The frame shrinks hard on flat backgrounds, nothing is lost, and the decoder just repeats what the count says.

The Code

def compress(chars):
    write = read = 0
    while read < len(chars):
        c, run = chars[read], 0
        while read < len(chars) and chars[read] == c:
            read += 1                 # measure the whole run first
            run += 1
        chars[write] = c
        write += 1
        if run > 1:                   # a run of one stays bare
            for d in str(run):
                chars[write] = d
                write += 1
    return write, chars[:write]

print(compress(list("aabbc")))   # (5, ['a', '2', 'b', '2', 'c'])