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.

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

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

12W1B12W3B24W1B14W

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

Output:

1A2B3C1D

 

References: https://en.wikipedia.org/wiki/Run-length_encoding

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 🙂