Run-length encoding (compression)

Squeezing repeated data

• Compression makes data smaller. Run-length encoding (RLE) is one simple way.
• It works well when the same value repeats many times in a row.
• It is lossless: from the squeezed form you can rebuild the exact original.

What a "run" is

• A run is a stretch of the same character repeated: in "aaabbc", "aaa" is a run of 3.
• RLE replaces each run with the character followed by how many times it repeats.
• So "aaabbc" becomes "a3b2c1" — much shorter when runs are long.

Counting a run

• To measure a run, look at a character, then count how many of the same character follow it.
• Stop when the next character is different, or you reach the end ('\0').
• That count is the run's length.

Building the encoded string

• Walk the input. For each run, write the character, then its count, into the output.
• Move your input position past the whole run before starting the next one.
• End the output string with '\0' so it is a proper C string.

#include <stdio.h>

int main(void) {
    const char *s = "aaab";
    int i = 0;
    char c = s[i];
    int count = 0;
    while (s[i] == c) {     // count the first run
        count++;
        i++;
    }
    printf("%c%d\n", c, count);   // a3
    return 0;
}

Common mistakes

• Run-length encoding stores a value then its count; it only helps when there are long runs.
• It is lossless — the original is restored exactly.

Now you try

• Find each run, then write the character and its count to the output.
• The caller gives you an output buffer big enough to hold the result. Do not write a main.