Codificación por longitud de corrida (compresión)
Comprimiendo datos repetidos
- La compresión hace que los datos sean más pequeños. El codificación por recuento de secuencias (RLE, por sus siglas en inglés) es una forma sencilla de lograrlo.
- Funciona bien cuando el mismo valor se repite muchas veces consecutivamente.
- Es sin pérdida: a partir de la forma comprimida puedes reconstruir exactamente el original.
Qué es una "secuencia"
- Una secuencia es un tramo del mismo carácter repetido: en
"aaabbc","aaa"es una secuencia de 3. - RLE reemplaza cada secuencia con el carácter seguido de cuántas veces se repite.
- Así,
"aaabbc"se convierte en"a3b2c1"— mucho más corto cuando las secuencias son largas.
Contando una secuencia
- Para medir una secuencia, observa un carácter y cuenta cuántos caracteres iguales lo siguen.
- Detente cuando el siguiente carácter sea diferente o reaches el final (
'\0'). - Ese conteo es la longitud de la secuencia.
Construyendo la cadena codificada
- Recorre la entrada. Por cada secuencia, escribe el carácter, luego su conteo, en la salida.
- Mueve tu posición de entrada más allá de toda la secuencia antes de comenzar la siguiente.
- Termina la cadena de salida con
'\0'para que sea una cadena C válida.
#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;
}
Errores comunes
- La codificación por recuento de secuencias almacena un valor seguido de su conteo; solo es útil cuando hay secuencias largas.
- Es sin pérdida: el original se restaura exactamente.
Ahora tú prueban
- Encuentra cada secuencia, luego escribe el carácter y su conteo en la salida.
- El llamador te proporciona un búfer de salida lo suficientemente grande para contener el resultado. No escribas una función
main.
Codificación de longitud de corrida
Reemplazar una secuencia de repeticiones con cantidad + símbolo — sin pérdida.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
Complete int run_length_at(const char *s, int i) para que devuelva cuántas veces se repite el carácter s[i] comenzando en el índice i. No escriba un main.
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
Complete void rle_encode(const char *in, char *out) para que escriba la codificación por longitud de corrida de in dentro de out: cada corrida se convierte en el carácter seguido de su cantidad. "aaabbc" se convierte en "a3b2c1". Termine out con '\0'. No escriba un main.
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
Ahora revierte eso. Completa void rle_decode(const char *in, char *out): cada carácter en in está seguido de un contador de un dígito, por lo que "a3b2c1" se convierte en "aaabbc". Termina out con '\0'. No escribas un main.
Haz clic en Ejecutar para ver la salida aquí.