Run Length Encoding

Run length encoding is a lossless compression method. Instead of writing a value out again and again, it writes the value once and then records how many times it repeats. Because nothing is thrown away, decompressing gives back exactly the original data.

That makes it a good fit for data with long runs of the same value. A plain white background in a picture, a row of identical pixels in a logo, or a long stretch of silent samples in an audio file all contain lots of repetition, so run length encoding shrinks them a great deal.

How it works

A run is a group of the same value repeated one after another. Picture a row of pixels, each one stored as a colour letter. Without compression the row might be:

• GGGGGGGGRRRR — 12 characters stored

With run length encoding, each run is written as a count plus the value. The same row becomes:

• 8G4R — 4 characters stored

You have gone from 12 characters to 4, and no information has been lost, because 8G followed by 4R can only mean the original row.

When it helps and when it does not

The saving depends entirely on how much repetition the data contains. Data made of short, constantly changing runs can actually get bigger, because each single value now needs its count written next to it as well.

So run length encoding suits simple graphics with large flat blocks of colour, and it is a poor choice for a detailed photograph where neighbouring pixels are nearly all different.

A program can carry out the idea in a few lines.

pixels = "YYYYYYYWWW"
encoded = ""

count = 1
for position in range(1, len(pixels)):
    if pixels[position] == pixels[position - 1]:
        count = count + 1
    else:
        encoded = encoded + str(count) + pixels[position - 1]
        count = 1
encoded = encoded + str(count) + pixels[len(pixels) - 1]
print("Original: " + pixels)
print("Encoded:  " + encoded)

# rebuild to show nothing was lost
rebuilt = ""
for position in range(0, len(encoded), 2):
    rebuilt = rebuilt + encoded[position + 1] * int(encoded[position])
print("Rebuilt:  " + rebuilt)

Output:

Original: YYYYYYYWWW
Encoded:  7Y3W
Rebuilt:  YYYYYYYWWW

Notice that the encoded text starts with the number of repeats, so the original ten letters become four characters. The check at the end rebuilds the text to prove that the decompression is exact, which is what lossless means.