Run-Length Encoding
In this article we’ll go over how the run-length encoding algorithm works, what it’s used for, and how to implement its encode and decode functions in Python.
Run-length encoding (RLE) is a very simple form of data compression in which a stream of data is given as the input (i.e. “AAABBCCCC”) and the output is a sequence of counts of consecutive data values in a row (i.e. “3A2B4C”). This type of data compression is lossless, meaning that when decompressed, all of the original data will be recovered when decoded. Its simplicity in both the encoding (compression) and decoding (decompression) is one of the most attractive features of the algorithm.
Here you can see a simple example of a stream (“run”) of data in its original form and encoded form:
Input data:
AAAAAAFDDCCCCCCCAEEEEEEEEEEEEEEEEE
Output data:
6A1F2D7C1A17E
In this example we were able to compress the data from 34 characters down to 13.
As you may have noticed, the more consecutive values in a row, the more space we save in the resulting compression. On the other hand, if you have a sequence of data that frequently changes between values (i.e. “BEFEFADED”) then we won’t save much space at