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 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Gesounds
Guest
Gesounds

Hi, first I want to thank you for your post.
i am trying to run the code in code::blocks. Code::blocks to recognize the order to_String.
I think it use a older compiler than c++ 11.
So I tried to change the int to string by an other way, the problem is that how the result is 1A12B123C1D instead of your right result. My code change is:
#include
#include
#include
using namespace std;

// Perform Run Length Encoding (RLE) data compression algorithm
// on string str
string encode(string str)
{
// stores output string
string encoding = “”;
int count;
//string zahl;
stringstream buffer;

for (int i = 0; str[i]; i++)
{
// count occurrences of character at index i

count = 1;

while (str[i] == str[i + 1])
count++, i++;

// append current character and its count to the result

buffer << count;
zahl = buffer.str();
encoding += zahl;
encoding += str[i];

}

return encoding;
}

int main()
{
string str = "ABBCCCD";

cout << encode(str);

return 0;
}

Can you please help me. Thank you

wpDiscuz