Encodage par compression de suites
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.
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.
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.
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;
}
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.
À 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.
Encodage par suites
Remplacez une suite de répétitions par compteur + symbole — sans perte.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Maintenant annuler cela. Compléter void rle_decode(const char *in, char *out) : chaque caractère dans in est suivi d'un compteur à un chiffre, donc "a3b2c1" devient "aaabbc". Terminer out par '\0'. Ne pas écrire de main.
Cliquez sur Exécuter pour voir le résultat ici.