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.
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 –
using namespace std;
// Perform Run Length Encoding (RLE) data compression algorithm
// on string str
string encode(string str)
// stores output string
string encoding = "";
for (int i = 0; str[i]; i++)
// count occurrences of character at index i
count = 1;
while (str[i] == str[i + 1])
// append current character and its count to the result
encoding += to_string(count) + str[i];
// main function
string str = "ABBCCCD";
cout << encode(str);
Thanks for reading.