Run Length Encoding (RLE) data compression algorithm

Run length encoding (RLE) is a very simple form of lossless data compression which runs on sequences having same value occurring many consecutive times and it encode the sequence to store only a single value and its count.

For example,

Consider a screen containing plain black text on a solid white background. There will be many long runs of white pixels in the blank space, and many short runs of black pixels within the text.


With a run length encoding (RLE) data compression algorithm applied to the above hypothetical scan line, it can be rendered as follows:


This can be interpreted as a sequence of twelve Ws, one B, twelve Ws, three Bs, etc.



The idea is to run a linear scan on the string and for each distinct character, we append the character and its consecutive occurrence in the output string.

Note that in worst case the size of output size will be just double of input size, so the algorithm can’t run in-place. eg. ABCD -> A1B1C1D1

C++ implementation –

Download   Run Code





Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂