RLE (Run-Length Encoding)

Run Length Encoding (or RLE, or range encoding) is a data compression (lossless) technique based on successive repetitions of elements.

Run Length means run length , and indeed, with RLE, what matters is the length, the size of the repetitions (in a text, a message, etc.)

The text to be encoded is scanned to find sequences of identical characters, then note the character and the number of repetitions in the sequence.

This procedure only produces compression if the message consists of many repetitions.

Writing variant

It is possible to encode by reversing the characters and the counts.

In case of Binary data

If the message is composed of binary data (0 and 1), then it is possible to use RLE without indicating the character, the numbers are sufficient. The first number indicating the 0 (or the 1), then alternatively.

Case of Numerical data

If the message is made up of numbers, then use a separator otherwise it will no longer be possible to distinguish the characters from their number of repetitions.

The RLE decompression consists in browsing the message formed of pairs (character, number of repetition) and writing the equivalent text by writing the character the corresponding number of times.

Binary data case

A message compressed with RLE is composed of pairs (Character-Number) or triples (Character-Separator-Number).

Bitmap BMP and PCX image formats use RLE to reduce file size.

RLE is particularly effective for data with long, repeating sequences (or identical pattern). Binary images, images with solid color areas (such as simple logos), or text files with repeating characters often benefit from effective compression with RLE.

Conversely, RLE is not effective for data with no repetitions or few repetitions. In these cases, the size of the compressed data may even increase compared to the original size.

RLE can be combined with other compression algorithms to improve performance (more compact files).

The source code of the RLE function for encoding:
function RLE_Encode(input_string) {
encoded_string = ""
count = 1
for (i = 1; i < length(input_string); i++) {
if (input_string[i] == input_string[i - 1]) {
count = count + 1
}
else {
encoded_string += input_string[i - 1] + count
count = 1
}
}
encoded_string += input_string[i - 1] + count
return encoded_string
}

The decoding function is programmed as follows:
function RLE_Decode(encoded_string) {
decoded_string = ""
for (i = 0; i < length(encoded_string); i+=2) {
char = encoded_string[i]
count = encoded_string[i+1]
decoded_string += string_repeat(char, count)
}
return decoded_string
}