Run-length Encoding (RLE)

Run-Length Encoding (RLE) – simple compression technique where consecutive repeating identical characters or bits are encoded with a single symbol and a repetition count. It was previously used for compressing black-and-white images but also in TGA, PCX formats, and FAX machines.

It’s easy to understand with an example.

Let’s encode the following characters using RLE encoding: 

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWW

Encoded: 

12W1B12W3B24W1B14W

The interpretation is: 12 W’s, 1 B, 12 W’s, 3 B’s, and so on.

Thus, the text encoded with run-length encoding describes the original 67 characters using 18. Of course, it is used with binary code rather than characters.

C program that implements this algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <string.h>
 
void runLengthEncoding(const char *input) {
    int length = strlen(input);
     
    for (int i = 0; i < length; i++) {
        // Count occurrences of the current character
        int count = 1;
        while (i < length - 1 && input[i] == input[i + 1]) {
            count++;
            i++;
        }
         
        // Print the count followed by the character
        printf("%d%c", count, input[i]);
    }
     
    printf("\n"); // New line after encoding
}
 
int main() {
    // Example string to encode
    char input[] = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWW";
     
    printf("Original String: %s\n", input);
    printf("Run-Length Encoded: ");
    runLengthEncoding(input);
     
    return 0;
}