Run-length encoding (compression) · Encodage par compression de suites
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.
Compresser les données répétées
- La compression rend les données plus petites. Le codage par longueur de run (RLE) est une méthode simple.
- Elle fonctionne bien lorsque la même valeur se répète plusieurs fois de suite.
- C'est sans perte : depuis la forme compressée, vous pouvez reconstruire l'original exact.
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.
Qu'est-ce qu'un "run" ?
- Un run est une séquence du même caractère répété : dans
"aaabbc","aaa"est un run de 3. - RLE remplace chaque run par le caractère suivi de combien de fois il se répète.
- Donc
"aaabbc"devient"a3b2c1"— beaucoup plus court quand les runs sont longs.
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.
Compter un run
- Pour mesurer un run, regardez un caractère, puis comptez combien de caractères identiques le suivent.
- Arrêtez-vous lorsque le prochain caractère est différent, ou que vous atteignez la fin (
'\0'). - Ce compte constitue la longueur du run.
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.
Construire la chaîne encodée
- Parcourez l'entrée. Pour chaque run, écrivez le caractère, puis son compte, dans la sortie.
- Avancez votre position d'entrée au-delà de tout le run avant de commencer le suivant.
- Terminez la chaîne de sortie avec
'\0'pour qu'elle soit une chaîne C valide.
#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.
Erreurs courantes
- Le codage par longueur de run stocke une valeur puis son compteur ; cela n'aide que lorsqu'il y a de longs runs.
- C'est sans perte — l'original est restauré exactement.
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.
À vous maintenant
- Trouvez chaque run, puis écrivez le caractère et son compteur dans la sortie.
- L'appelant vous donne un tampon de sortie assez grand pour contenir le résultat. Ne écrivez pas de
main.
Run-length encoding · Encodage par suites
Replace a run of repeats with count + symbol — lossless. · Remplacez une suite de répétitions par compteur + symbole — sans perte.
Complete int run_length_at(const char *s, int i) so it returns how many times the character s[i] repeats starting at index i. Do not · non write a main. · Complétez int run_length_at(const char *s, int i) pour qu'il retourne combien de fois le caractère s[i] se répète à partir de l'index i. Ne pas écrire de main.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Complete void rle_encode(const char *in, char *out) so it writes the run-length encoding of in into · dans out: each run becomes the character then its count. "aaabbc" becomes "a3b2c1". End out with '\0'. Do not · non write a main. · Complétez void rle_encode(const char *in, char *out) pour qu'il écrive l'encodage par compression de in dans out : chaque suite devient le caractère suivi de son compteur. "aaabbc" devient "a3b2c1". Terminez out par '\0'. Ne pas écrire de main.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.