Run-length encoding (compression) · Codificação por repetição (compressão)
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.
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.
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.
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.
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.
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.
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.
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;
}
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.
Erros comuns
- Run-length encoding armazena um valor então sua contagem; só ajuda quando há runs longos.
- É lossless — o original é restaurado exatamente.
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.
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.
Run-length encoding · Codificação por comprimento de corrida
Replace a run of repeats with count + symbol — lossless. · Substitua uma sequência de repetições por contagem + símbolo — sem perda.
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 · não write a main. · Complete int run_length_at(const char *s, int i) para que retorne quantas vezes o caractere s[i] se repete começando no índice i. Não escreva um main.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Complete void rle_encode(const char *in, char *out) so it writes the run-length encoding of in into · em out: each run becomes the character then its count. "aaabbc" becomes "a3b2c1". End out with '\0'. Do not · não write a main. · Complete void rle_encode(const char *in, char *out) para que escreva a codificação por repetição de in em out: cada run torna-se o caractere seguido de sua contagem. "aaabbc" torna-se "a3b2c1". Termine out com '\0'. Não escreva um main.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.