Institute of Information Science - University of Miskolc

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:

<sxh c> #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;

} </sxh>