Data compression · Compressão de dados
Why compress data
- Data takes up space to store and time to send.
- Compression makes a file smaller so it is cheaper to save and faster to share.
- There are two kinds: lossless and lossy.
Por que comprimir dados
- Dados ocupam espaço para armazenar e tempo para enviar.
- A compressão torna um arquivo menor para que seja mais barato salvar e mais rápido compartilhar.
- Existem dois tipos: sem perda e com perda.
Lossless compression
- Lossless makes a file smaller but keeps every bit of the data.
- When you open the file, you get back the exact original.
- It works by finding patterns and writing them in a shorter way.
Compressão sem perda
- Sem perda torna um arquivo menor mas mantém todo o dado.
- Quando você abre o arquivo, recupera o exato original.
- Funciona encontrando padrões e escrevendo-os de forma mais curta.
Original: AAAAAAAA-BBB
Shorter: 8A-3B (8 A's, then 3 B's)
Open it: AAAAAAAA-BBB (exactly the same again)
Lossy compression
- Lossy makes a file much smaller by throwing away some data.
- It drops details that people can barely see or hear.
- You cannot get the exact original back — but it is "close enough".
Compressão com perda
- Com perda torna um arquivo muito menor descartando alguns dados.
- Ela elimina detalhes que as pessoas mal conseguem ver ou ouvir.
- Você não pode recuperar o exato original — mas é "close enough" (praticamente igual).
Photo (large) --lossy--> Photo (small)
A few colors and fine details are gone,
but your eye hardly notices.
The trade-off: size vs quality
- Lossless keeps full quality, but the file stays larger.
- Lossy gives a much smaller file, but quality goes down a little.
- You choose based on what matters more: perfect data or small size.
O compromisso: tamanho vs qualidade
- Sem perda mantém a qualidade total, mas o arquivo permanece maior.
- Com perda oferece um arquivo muito menor, mas a qualidade cai um pouco.
- Você escolhe baseado no que importa mais: dados perfeitos ou tamanho pequeno.
When to use each
- Use lossless when every detail must be exact.
- Use lossy when a small drop in quality is fine and small size matters.
Quando usar cada um
- Use sem perda quando cada detalhe deve ser exato.
- Use com perda quando uma pequena queda na qualidade é aceitável e tamanho pequeno importa.
Lossless: text, code, a .zip file, a spreadsheet
Lossy: photos (JPEG), music (MP3), video
Key idea
- Compression trades size against quality (or against work to undo it).
- Lossless = smaller and perfect; lossy = much smaller but not exact.
- Good engineers pick the right kind for the job.
Ideia-chave
- A compressão troca tamanho contra qualidade (ou contra o trabalho para desfazê-la).
- Sem perda = menor e perfeito; com perda = muito menor mas não exato.
- Bons engenheiros escolhem o tipo certo para o trabalho.
Run-length encoding
- Run-length encoding (RLE) is a simple lossless method.
- A run is a stretch of the same character repeated. RLE stores a count instead of the repeats.
- We will store each run as a pair
[character, count]inside a list.
Codificação por comprimento de corrida
- Codificação por comprimento de corrida (RLE) é um método simples sem perda.
- Uma corrida é uma sequência do mesmo caractere repetido. RLE armazena um contador em vez das repetições.
- Armazenaremos cada corrida como um par
[character, count]dentro de uma lista.
"AAAB" -> [["A", 3], ["B", 1]] (3 A's, then 1 B)
[["A", 3], ["B", 1]] -> "AAAB" (decode it back — exact again)
Common mistakes
- Lossless compression can be reversed exactly; lossy throws away detail.
- More compression can mean lower quality.
Erros comuns
- A compressão sem perda pode ser revertida exatamente; a com perda descarta detalhes.
- Mais compressão pode significar qualidade inferior.
Now you try
- Build RLE yourself: an encoder, a decoder, and a length helper.
- Each task checks your function on several inputs. Press Check answer.
Agora você tenta
- Construa RLE por si mesmo: um codificador, um decodificador e um auxiliar de comprimento.
- Cada tarefa verifica sua função em várias entradas. Pressione Verificar resposta.
Lossless compression · Compressão sem perda
Run-length encoding replaces a run of repeats with count + symbol. · Codificação por repetição substitui uma sequência de repetições por contagem + símbolo.
Write encode(text) for run-length encoding. Return a list of [character, count] pairs, one per run of repeats. Example: encode("AAAB") → [['A', 3], ['B', 1]]. For the empty string return []. · Escreva encode(text) para codificação por repetição. Retorne uma lista de pares [character, count], um por sequência de repetições. Exemplo: encode("AAAB") → [['A', 3], ['B', 1]]. Para a string vazia retorne [].
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Write decode(pairs) that reverses the encoder: given a list of [character, count] pairs, rebuild the original string. Example: decode([['A', 3], ['B', 1]]) → 'AAAB'. For [] return · retorno ''. · Escreva decode(pairs) que inverte o codificador: dada uma lista de pares [character, count], reconstrua a string original. Exemplo: decode([['A', 3], ['B', 1]]) → 'AAAB'. Para [] retorne ''.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Without decoding, write original_length(pairs) that returns how many characters the original text had — just add up the counts. Example: original_length([['A', 3], ['B', 1]]) → 4. · Sem decodificar, escreva original_length(pairs) que retorne quantos caracteres o texto original tinha — basta somar as contagens. Exemplo: original_length([['A', 3], ['B', 1]]) → 4.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.