Run-length encoding (compression)
Espremendo dados repetidos
- Compressão torna os dados menores. Run-length encoding (RLE) é uma forma simples disso.
- Funciona bem quando o mesmo valor se repete muitas vezes seguidas.
- É lossless (sem perda): a partir da versão espremida você pode reconstruir exatamente o original.
O que é um "run"
- Um run é uma sequência do mesmo caractere repetido: em
"aaabbc","aaa"é um run de 3. - RLE substitui cada run pelo caractere seguido de quantas vezes ele se repete.
- Então
"aaabbc"vira"a3b2c1"— muito menor quando runs são longos.
Contando um run
- Para medir um run, olhe para um caractere, depois conte quantos dos mesmos caracteres vêm depois dele.
- Pare quando o próximo caractere for diferente, ou você atingir o fim (
'\0'). - Essa contagem é o comprimento do run.
Construindo a string codificada
- Percorra a entrada. Para cada run, escreva o caractere, depois sua contagem, na saída.
- Mova sua posição de entrada para além do run inteiro antes de começar o próximo.
- Termine a string de saída com
'\0'para que seja uma string 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;
}
Erros comuns
- Run-length encoding armazena um valor então sua contagem; só ajuda quando há runs longos.
- É lossless — o original é restaurado exatamente.
Agora você tenta
- Encontre cada run, então escreva o caractere e sua contagem na saída.
- O caller lhe dá um buffer de saída grande o suficiente para guardar o resultado. Não escreva um
main.
Codificação por comprimento de corrida
Replace a run of repeats with count + symbol — lossless.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
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 não write a main.
Clique em Executar para ver a saída aqui.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Complete void rle_encode(const char *in, char *out) so it writes the run-length encoding of in em out: each run becomes the character then its count. "aaabbc" becomes "a3b2c1". End out with '\0'. Do não write a main.
Clique em Executar para ver a saída aqui.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Now undo it. Complete void rle_decode(const char *in, char *out): each character in in is followed by a single-digit count, so "a3b2c1" becomes "aaabbc". End out with '\0'. Do não write a main.
Clique em Executar para ver a saída aqui.