Aula 26 - Compressão de Dados: RLE, Huffman e LZW
Um arquivo de texto típico em inglês usa apenas 26 letras mais pontuação, mas o padrão ASCII reserva 8 bits por caractere — desperdiçando bits com símbolos que jamais aparecem naquele arquivo. Um arquivo de 1 MB leva 8 segundos para ser transmitido numa conexão de 1 Mbps; comprimido para 300 KB, leva apenas 2,4 segundos. Streaming de vídeo, armazenamento de imagens, protocolos de comunicação: compressão está em todo lugar.
Conceitos básicos de compressão
O que é comprimir?
Comprimir é representar a mesma informação usando menos bits. Isso só é possível porque os dados reais têm redundância: partes que podem ser descritas de forma mais econômica. Existem três tipos de redundância que exploraremos nesta aula:
| Redundância | Exemplo | Método que a explora |
|---|---|---|
| Repetições consecutivas | AAAAAAAA pode ser dito como “8 vezes A” | RLE |
| Símbolos com frequências desiguais | em textos, o 'e' é muito mais comum que o 'z': faz sentido dar a ele um código mais curto | Huffman |
| Padrões (substrings) repetidos | as mesmas palavras ou frases reaparecem várias vezes no arquivo | LZW |
Medindo a compressão
A razão de compressão é o tamanho comprimido dividido pelo tamanho original. Quanto menor, melhor. Também falamos em redução (quanto foi economizado, em %) ou em bits por símbolo (o ASCII usa 8 bits por caractere).
| Exemplo | Razão | Redução | Bits por símbolo |
|---|---|---|---|
| 1 MB → 300 KB | 300 / 1000 = 0,3 | 70% | — |
20 caracteres → 10 (RLE de AAABBBCCCCDDDDDDDDDE) | 10 / 20 = 0,5 | 50% | — |
8 caracteres → 16 (RLE de ABCDEFGH) | 16 / 8 = 2,0 | −100% (expansão) | — |
| 88 bits → 23 bits (Huffman de “abracadabra”) | 23 / 88 ≈ 0,26 | ≈ 74% | 23 / 11 ≈ 2,09 |
Uma razão maior que 1 significa que o “compressor” aumentou o arquivo. Isso é possível e acontece, como veremos com o RLE.
Todo arquivo pode ser comprimido?
Não. Existem 2n arquivos diferentes de n bits, mas menos de 2n arquivos menores que n bits. Pelo princípio da casa dos pombos, não há como representar todos eles com menos bits sem perda. Na prática, dados que já estão comprimidos (como um ZIP, um JPEG ou um MP3) ou dados aleatórios não têm redundância para ser explorada e não encolhem; podem até crescer um pouco. Comprimir bem depende de conhecer o tipo de dado.
|
Compressão sem perda (lossless) × com perda (lossy) Lossless: o arquivo original é recuperado exatamente. Exemplos: ZIP, PNG, GIF. Lossy: parte da informação é descartada, quando o ser humano não percebe a diferença. Exemplos: JPEG, MP3, vídeo H.264. Todos os métodos desta aula (RLE, Huffman, LZW) são lossless. |
Os três métodos desta aula
| Método | O que explora | Ideia em uma frase |
|---|---|---|
| RLE | repetições consecutivas | troca AAAA por “4 vezes A” |
| Huffman | a frequência dos símbolos | códigos curtos para o que é comum, longos para o que é raro |
| LZW | padrões (substrings) repetidos | monta um dicionário e troca cada padrão por um código |
1. RLE (Run-Length Encoding)
1.1 Ideia
Substitui cada sequência (run) de caracteres idênticos consecutivos por um par (contagem, caractere). É o método mais simples e mais antigo de compressão.
Analogia: ao ditar uma sequência pelo telefone, em vez de falar “A, A, A, B, B, B” você diz “três A, três B”. O RLE faz exatamente isso, só que escrevendo 3A3B.
|
1.2 Algoritmo passo a passo com exemplo
- Percorra a entrada da esquerda para a direita.
- Conte quantos caracteres iguais aparecem em sequência (o run).
- Escreva o par
contagem + caracteree recomece no próximo caractere diferente.
Entrada: AAABBBCCCCDDDDDDDDDE (20 caracteres). Cada letra tem uma cor, e os runs estão marcados embaixo:
| entrada | A | A | A | B | B | B | C | C | C | C | D | D | D | D | D | D | D | D | D | E |
| 3 × A | 3 × B | 4 × C | 9 × D | 1 × E | ||||||||||||||||
| saída RLE | 3A | 3B | 4C | 9D | 1E |
Resultado: 3A3B4C9D1E, com 10 caracteres no lugar de 20: uma redução de 50%.
1.3 Quando funciona e quando não funciona
O RLE depende de haver repetições. Compare três entradas:
| Caso | Entrada | Saída RLE | Resultado |
|---|---|---|---|
| Bom: muitas repetições | AAABBBCCCCDDDDDDDDDE20 bytes | 3A3B4C9D1E10 bytes | −50% |
| Melhor caso: áreas uniformes (imagem P&B) | 22×W + 8×B30 bytes | 22W8B5 bytes | −83% |
| Ruim: sem repetições | ABCDEFGH8 bytes | 1A1B1C1D1E1F1G1H16 bytes | +100% (EXPANSÃO!) |
Melhor caso — imagem com áreas uniformes (22 pixels brancos e 8 pretos):
| entrada | W | W | W | W | W | W | W | W | W | W | W | W | W | W | W | W | W | W | W | W | W | W | B | B | B | B | B | B | B | B |
| 22 × W | 8 × B | |||||||||||||||||||||||||||||
| saída RLE | 22W | 8B |
Caso ruim — nenhum caractere se repete, então cada run tem comprimento 1 e o arquivo comprimido fica maior que o original:
| entrada | A | B | C | D | E | F | G | H |
| saída RLE | 1A | 1B | 1C | 1D | 1E | 1F | 1G | 1H |
1.4 Estrutura em C
Cada corrida é um par (quantidade, caractere); a saída do RLE é um vetor desses pares.
/* "4W" vira {4, 'W'} */ typedef struct { int qtd; /* quantas vezes o caractere se repete */ char c; /* o caractere repetido */ } ParRLE;
1.5 Aplicações e limitações
Onde é usado: fax, BMP, PCX e TIFF (com opção RLE).
Limitações:
- Só é eficiente quando há muitas repetições consecutivas;
- Pode expandir os dados se quase todas as sequências tiverem comprimento 1;
- Não enxerga padrões que se repetem sem ficar juntos (“ABABAB” não comprime);
- Não é adequado para texto geral ou dados variados.
Custo: uma única passada pela entrada, ou seja, O(N), em que N é o número de caracteres da entrada.
2. Código de Huffman
2.1 Ideia
No ASCII, todo caractere usa 8 bits, independentemente da frequência. Mas a letra 'e' aparece muito mais do que a letra 'z' em textos. A ideia de Huffman: atribuir códigos mais curtos aos caracteres mais frequentes e códigos mais longos aos raros.
Analogia: o código Morse já faz isso. A letra mais comum do inglês, o E, é um único ponto (.); o T é um único traço (-); já letras raras como o Q (--.-) e o Z (--..) têm códigos longos.
|
Restrição fundamental: o código deve ser um código de prefixo, isto é, nenhum código pode ser prefixo de outro. Isso permite decodificar sem separadores entre os códigos. Exemplo: se a = 0 e b = 01, ao ler 01 não sabemos se é “b” ou “a” seguido de outro símbolo. Com a = 0 e b = 10, não há ambiguidade.
|
2.2 Construção da árvore de Huffman
O algoritmo é guloso (greedy) e usa uma fila de prioridade (min-heap), exatamente como visto na Aula 18:
| Nota — o que é um algoritmo guloso? É um algoritmo que, a cada passo, faz a escolha que parece a melhor naquele momento (aqui: juntar os dois nós de menor frequência) e nunca volta atrás. Nem sempre isso leva à melhor solução final, mas no Huffman leva. Algoritmos gulosos serão estudados com calma em outras disciplinas do curso. |
- Criar um nó para cada caractere, com sua frequência.
- Enquanto existir mais de um nó:
- Escolher os dois nós de menor frequência.
- Criar um novo nó com a soma das frequências.
- Colocar o menor à esquerda e o maior à direita.
- Remover os dois nós originais da fila de prioridade.
- Inserir o novo nó na fila de prioridade.
- O nó restante será a raiz da árvore.
- Percorrer a árvore:
- Esquerda = 0
- Direita = 1
- O caminho da raiz até cada folha será o código do caractere.
| Convenção didática: em cada junção, o nó de menor frequência vai à esquerda (0) e o de maior frequência à direita (1); em caso de empate, o mais antigo fica à esquerda. É só uma convenção para que todos cheguem às mesmas árvores e aos mesmos códigos: trocar os lados não muda o total de bits, só os códigos. |
|
Conexão com a Aula 18 — Min-Heap! A construção usa exatamente uma fila de prioridade mínima: o nó de menor frequência é sempre extraído primeiro. Se o texto tem k caracteres distintos, são cerca de k extrações, cada uma custando O(log k) (cresce bem devagar com k): a construção da árvore custa O(k log k). Depois, codificar o texto custa O(N), em que N é o número de caracteres do texto. |
2.3 Exemplo completo
Mensagem: “abracadabra” (11 caracteres). Cada caractere tem uma cor, que vamos acompanhar até o final.
Passo 1 — Contar as frequências: percorremos a mensagem e contamos cada caractere, na ordem em que aparecem:
| caractere | a | b | r | c | d |
| frequência | 5 | 2 | 2 | 1 | 1 |
Passo 2 — Ordenar: das menores para as maiores frequências (em caso de empate, vem antes quem apareceu primeiro). Essa lista é o conteúdo inicial do min-heap:
| caractere | c | d | b | r | a |
| frequência | 1 | 1 | 2 | 2 | 5 |
Passo 3 — Montar a árvore com o min-heap: repetimos as etapas do algoritmo até sobrar uma única árvore, sempre com a convenção didática: menor frequência à esquerda (0), maior à direita (1). Assim, em cada quadro as árvores aparecem em ordem crescente de frequência, da esquerda para a direita, como no heap. Só os nós que já foram juntados entram no desenho; o que ainda não foi usado fica apenas no heap (lista embaixo). O número dentro de cada nó interno é a soma das frequências das folhas ligadas a ele.
| Início: o min-heap começa com os caracteres já ordenados (Passo 2). Ainda não há árvore. |
| Heap agora (menor frequência primeiro): c:1 d:1 b:2 r:2 a:5 |
| Etapa 1: extrai as duas menores, c:1 (esquerda, bit 0) e d:1 (direita, bit 1); junta-as num nó novo (verde) de frequência 1 + 1 = 2 e o devolve ao heap. |
| Heap agora (menor frequência primeiro): b:2 r:2 (cd):2 a:5 |
| Etapa 2: extrai as duas menores, b:2 (esquerda, bit 0) e r:2 (direita, bit 1); junta-as num nó novo (verde) de frequência 2 + 2 = 4 e o devolve ao heap. |
| Heap agora (menor frequência primeiro): (cd):2 (br):4 a:5 |
| Etapa 3: extrai as duas menores, (cd):2 (esquerda, bit 0) e (br):4 (direita, bit 1); junta-as num nó novo (verde) de frequência 2 + 4 = 6 e o devolve ao heap. |
| Heap agora (menor frequência primeiro): a:5 (cdbr):6 |
| Etapa 4: extrai as duas menores, a:5 (esquerda, bit 0) e (cdbr):6 (direita, bit 1); junta-as num nó novo (verde) de frequência 5 + 6 = 11 e o devolve ao heap. Sobrou um nó: é a raiz. |
| Heap agora (menor frequência primeiro): (acdbr):11 |
Quando há empate de frequência, a escolha do nó pode mudar a forma da árvore e os códigos, mas o total de bits é sempre o mesmo. Aqui, em caso de empate, o nó mais antigo sai primeiro (e fica à esquerda).
Passo 4 — Árvore resultante (aresta esquerda = 0, direita = 1; as folhas têm a cor do caractere):
Passo 5 — Códigos gerados (caminho da raiz até a folha):
| Caractere | Frequência | Código | Bits por caractere | Bits no texto (freq × bits) |
|---|---|---|---|---|
| a | 5 | 0 | 1 | 5 × 1 = 5 |
| b | 2 | 110 | 3 | 2 × 3 = 6 |
| c | 1 | 100 | 3 | 1 × 3 = 3 |
| d | 1 | 101 | 3 | 1 × 3 = 3 |
| r | 2 | 111 | 3 | 2 × 3 = 6 |
| Total | 23 bits | |||
Repare: a, o caractere mais frequente (5 vezes), ficou com o código mais curto (1 bit); c e d, os mais raros, ficaram com 3 bits. Nenhum código é prefixo de outro.
Passo 6 — Codificando “abracadabra”:
| caractere | a | b | r | a | c | a | d | a | b | r | a |
| código | 0 | 110 | 111 | 0 | 100 | 0 | 101 | 0 | 110 | 111 | 0 |
| bits | 1 | 3 | 3 | 1 | 3 | 1 | 3 | 1 | 3 | 3 | 1 |
| Representação | Bits | Observação |
|---|---|---|
| ASCII original | 11 × 8 = 88 bits | 8 bits por caractere |
| Huffman | 23 bits | redução de ≈ 74% |
Comprimento médio: (5×1 + 2×3 + 2×3 + 1×3 + 1×3) / 11 = 23 / 11 ≈ 2,09 bits por caractere, contra os 8 do ASCII. (Esses 23 bits não incluem a tabela de códigos que acompanha o arquivo; veja a nota na seção 2.5.)
2.4 Até onde dá para comprimir? Entropia de Shannon
O Huffman usa só a frequência dos caracteres. Para esse tipo de compressão existe um limite teórico, calculado por Claude Shannon: a entropia (H), o menor número médio de bits por caractere que qualquer código baseado em frequências consegue.
A fórmula, em que c é cada caractere distinto do texto:
H = Σc ( p(c) · (−log2 p(c)) ) bits por caractere
- p(c) é a frequência relativa de c: ocorrências de c ÷ total de caracteres.
- −log2 p(c) é quantos bits o caractere c “merece”: quanto mais comum, menos bits. Por exemplo: p = 1/2 → 1 bit; p = 1/4 → 2 bits; p = 1/8 → 3 bits (log2 é o logaritmo na base 2).
- Σc soma, para cada caractere distinto c, o que está entre parênteses (o produto p(c) · (−log2 p(c))). O resultado é a média dos tamanhos “merecidos”, ponderada pela frequência de cada caractere.
Para o “abracadabra” (11 caracteres):
| Caractere | Ocorrências | Frequência relativa p | Bits “merecidos” −log2 p | Contribuição p · (−log2 p) |
|---|---|---|---|---|
| a | 5 | 5/11 ≈ 0,4545 | 1,137 | 0,4545 · 1,137 ≈ 0,517 |
| b | 2 | 2/11 ≈ 0,1818 | 2,459 | 0,1818 · 2,459 ≈ 0,447 |
| r | 2 | 2/11 ≈ 0,1818 | 2,459 | 0,1818 · 2,459 ≈ 0,447 |
| c | 1 | 1/11 ≈ 0,0909 | 3,459 | 0,0909 · 3,459 ≈ 0,314 |
| d | 1 | 1/11 ≈ 0,0909 | 3,459 | 0,0909 · 3,459 ≈ 0,314 |
| Entropia H = soma das contribuições | ≈ 2,04 bits por caractere | |||
Comparando: o ASCII gasta 8 bits por caractere, o limite teórico é 2,04 e o Huffman, que só pode usar um número inteiro de bits por código (1, 3, 3, 3 e 3, contra os 1,14 / 2,46 / 3,46 “ideais”), chegou a 2,09. Muito perto do limite.
Regra geral: quanto mais desiguais as frequências, menor a entropia e mais o Huffman comprime. Se os 5 caracteres aparecessem todos com a mesma frequência (1/5), a entropia seria a máxima para 5 caracteres: log2 5 ≈ 2,32 bits.
Mas esse limite vale só para códigos que olham as frequências. Em abababab... as frequências são 50% / 50% (1 bit por caractere), mas o LZW comprime muito mais, pois enxerga o padrão “ab” repetido, e não só as frequências.
|
2.5 Decodificação
Para decodificar, percorre-se a árvore bit a bit, a partir da raiz: 0 vai para o filho esquerdo, 1 para o direito. Ao chegar numa folha, emite-se o caractere e volta-se à raiz. Os primeiros símbolos de 0 110 111 0 100 ...:
| Bits lidos | Percurso a partir da raiz | Folha: emite |
|---|---|---|
| 0 | raiz →0 folha a | a |
| 110 | raiz →1 nó (6) →1 nó (4) →0 folha b | b |
| 111 | raiz →1 nó (6) →1 nó (4) →1 folha r | r |
| 0 | raiz →0 folha a | a |
| 100 | raiz →1 nó (6) →0 nó (2) →0 folha c | c |
| Não são necessários separadores entre os códigos. Como o código é de prefixo, chegar a uma folha significa que o código terminou: a própria estrutura da árvore determina os limites. |
|
Atenção — o decodificador precisa da árvore! Quem recebe só os bits não sabe quais códigos correspondem a quais caracteres. Por isso o arquivo comprimido leva, junto com a mensagem, uma tabela com os caracteres e seus códigos (ou as frequências, para o decodificador refazer a mesma árvore). Essa tabela ocupa bytes extras: no “abracadabra”, só os 5 caracteres distintos já ocupam 5 bytes = 40 bits, mais que os 23 bits da mensagem, e com os códigos junto o total pode até passar dos 88 bits originais. Em textos pequenos, a compressão pode não compensar. Em arquivos grandes o custo some (a tabela tem no máximo algumas centenas de bytes, quase nada perto de milhares ou milhões de caracteres). |
2.6 Estrutura em C
typedef struct NodoHuff { char c; /* caractere (só nas folhas) */ int freq; /* frequência no texto */ struct NodoHuff *esq, *dir; /* filhos: bit 0 / bit 1 */ } NodoHuff;
A construção usa um min-heap de NodoHuff* ordenado por freq (Aula 18).
2.7 Aplicações e limitações
Onde é usado: JPEG, MP3, Deflate (ZIP, PNG, gzip) e HTTP/2 (HPACK).
Limitações:
- Precisa enviar a tabela de códigos junto, o que pesa em arquivos pequenos;
- Olha só as frequências e ignora a ordem e os padrões repetidos (“abababab” não ajuda);
- Cada caractere usa um número inteiro de bits (no mínimo 1), então não chega exatamente ao limite da entropia;
- Se as frequências são quase iguais, o ganho é pequeno.
3. LZW (Lempel-Ziv-Welch)
3.1 Ideia
O Huffman é ótimo para caracteres individuais, mas ignora a repetição de padrões (substrings). Na string “abcabc”, ele codifica 'a', 'b', 'c', 'a', 'b', 'c' separadamente. O LZW constrói um dicionário de substrings que vai encontrando e substitui cada ocorrência por um código mais curto.
| Analogia: numa conversa, depois de dizer uma vez “Universidade Federal do Rio Grande do Sul”, você passa a dizer apenas “UFRGS”. O LZW cria esses “apelidos” sozinho, no meio do arquivo, e usa o apelido sempre que o padrão reaparece. |
3.2 Algoritmo de compressão
Em palavras: o LZW lê a entrada procurando o maior padrão que já conhece. Quando encontra um padrão novo, ele anota o padrão no dicionário, para poder usar um código curto da próxima vez. Duas variáveis ajudam: w é o padrão que estamos montando e c é o próximo caractere da entrada.
- Início: o dicionário contém todos os caracteres individuais (entradas 0 a 255 para ASCII). Faça w = primeiro caractere da entrada.
- Para cada próximo caractere c da entrada:
- Se w + c (o padrão com mais um caractere) já está no dicionário: o padrão cresce, w = w + c.
- Caso contrário: emita o código de w, adicione w + c ao dicionário (com o próximo código livre) e recomece o padrão: w = c.
- No fim da entrada, emita o código de w.
3.3 Exemplo completo de compressão
Entrada: “ABABABAB” (8 caracteres). Dicionário inicial (alfabeto simplificado): A : 0 B : 1
Acompanhe cada passo. Na coluna Entrada, as letras cinza já foram codificadas, as azuis formam o padrão w e a laranja é o próximo caractere c. Em amarelo, as entradas novas do dicionário; em verde, os códigos emitidos:
| Passo | Entrada | O que acontece | Saída até aqui | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 |
| AB não está no dicionário. Então: (1) emite o código de A, que é 0; (2) cadastra AB : 2; (3) w recomeça em B. | 0 | ||||||||
| 2 |
| BA não está no dicionário. Então: (1) emite o código de B, que é 1; (2) cadastra BA : 3; (3) w recomeça em A. | 01 | ||||||||
| 3 |
| AB já está no dicionário (código 2). Então o padrão cresce: w passa a ser AB. Nada é emitido. | 01 | ||||||||
| 4 |
| ABA não está no dicionário. Então: (1) emite o código de AB, que é 2; (2) cadastra ABA : 4; (3) w recomeça em A. | 012 | ||||||||
| 5 |
| AB já está no dicionário (código 2). Então o padrão cresce: w passa a ser AB. Nada é emitido. | 012 | ||||||||
| 6 |
| ABA já está no dicionário (código 4). Então o padrão cresce: w passa a ser ABA. Nada é emitido. | 012 | ||||||||
| 7 |
| ABAB não está no dicionário. Então: (1) emite o código de ABA, que é 4; (2) cadastra ABAB : 5; (3) w recomeça em B. | 0124 | ||||||||
| 8 |
| Acabou a entrada. Emite o código do w que sobrou, B: 1. | 01241 |
Saída comprimida:
| saída | 0 | 1 | 2 | 4 | 1 |
Dicionário ao final (azul: inicial; amarelo: criado durante a compressão):
| código | 0 | 1 | 2 | 3 | 4 | 5 |
| string | A | B | AB | BA | ABA | ABAB |
Resultado: 5 códigos no lugar de 8 caracteres. Repare que o código 4 (“ABA”) substitui três caracteres de uma vez: quanto mais longo o padrão repetido, maior o ganho.
3.4 Descompressão LZW
| Insight fundamental: o descompressor consegue reconstruir as entradas criadas durante a compressão (os padrões novos), um passo atrás do compressor. Por isso não é preciso transmitir essas entradas. |
|
ATENÇÃO: o descompressor PRECISA do dicionário inicial! Ele só reconstrói as entradas novas. As entradas iniciais (os caracteres individuais, A:0, B:1 no exemplo; entradas 0 a 255 no ASCII) têm de ser exatamente as mesmas nos dois lados: combinadas de antemão (como a tabela ASCII) ou enviadas junto com os dados. Sem o dicionário inicial, o código 0 não significa nada e a descompressão é impossível.
|
A cada código lido, o descompressor emite a string correspondente e adiciona ao dicionário a string anterior + o primeiro caractere da string atual (exatamente a entrada que o compressor criou naquele momento). Para a saída [0, 1, 2, 4, 1] e o dicionário inicial A:0, B:1 (sem ele não dá para começar!):
| Passo | Código lido | Emite | Nova entrada no dicionário (= anterior + 1.º caractere do que acabou de emitir) | Saída até aqui |
|---|---|---|---|---|
| 1 | 0 | A | — | A |
| 2 | 1 | B | A + B = AB : 2 | AB |
| 3 | 2 | AB | B + A = BA : 3 | ABAB |
| 4 | 4 ainda não existe! | ABA | AB + A = ABA : 4 | ABABABA |
| 5 | 1 | B | ABA + B = ABAB : 5 | ABABABAB |
Resultado: ABABABAB, a entrada original recuperada por completo.
| O caso especial (linha do código 4): ao ler o código 4, o descompressor ainda não criou a entrada 4: o compressor a criou e usou logo em seguida. Isso acontece quando o padrão começa e termina com o mesmo caractere. A string é sempre anterior + primeiro caractere do anterior (aqui, “AB” + “A” = “ABA”), e ela mesma passa a ser a nova entrada 4. |
3.5 Estrutura em C
Cada entrada do dicionário é um código já conhecido (o prefixo) mais um caractere novo:
typedef struct { int prefixo; /* código da string sem o último caractere */ char c; /* último caractere */ } EntradaLZW; EntradaLZW dic[4096]; /* a posição no vetor é o próprio código */
Exemplo (“ABABABAB”): a entrada 2 (“AB”) é {prefixo = 0, c = 'B'}, isto é, “o código 0 (A) seguido de B”.
3.6 Aplicações
| Formato | Uso do LZW |
|---|---|
| GIF | LZW sobre os dados de pixels; |
| TIFF | compressão LZW opcional; |
| LZW em streams; | |
| Unix compress | arquivos .Z clássicos. |
4. Comparação dos métodos
| Critério | RLE | Huffman | LZW |
|---|---|---|---|
| Tipo de redundância explorada | Repetições consecutivas | Frequência de símbolos | Padrões (substrings) repetidos |
| Requer dicionário / árvore? | Não | Sim (árvore) | Sim (construído durante a compressão) |
| Dicionário transmitido? | Não | Sim (ou acordo prévio) | Não (reconstruído pelo descompressor) |
| Custo da compressão (N = caracteres da entrada; k = caracteres distintos) | O(N) | O(k log k) para a árvore + O(N) para codificar | O(N) esperado |
| Eficiência em texto | Fraca | Boa | Muito boa |
| Eficiência em imagens P&B | Excelente | Moderada | Boa |
| Lossless? | Sim | Sim | Sim |
| Usado em | BMP, Fax | JPEG, ZIP | GIF, PDF |
| Nenhum método é universalmente melhor. Na prática, os formatos modernos combinam técnicas: o gzip usa LZ77 (semelhante ao LZW) seguido de Huffman; o PNG usa LZ77 + Huffman; o JPEG usa a DCT (uma transformada que separa o que o olho percebe do que ele quase não percebe; o que é pouco percebido é descartado, e é essa a etapa com perda) seguida de Huffman. A escolha depende do tipo de dado e do compromisso entre taxa de compressão, velocidade e complexidade. |
Resumo
|
Material complementar
- Vídeo (em inglês) com outro exemplo resolvido de Huffman: Compressing text using Huffman trees worked example.
Exercícios
-
Aplique a compressão RLE à string
"WWWWBWWWWWWWBBBWWWWW". Qual é a representação comprimida? Qual é a razão de compressão? - Por que o RLE pode expandir os dados para certas entradas? Dê um exemplo em que a saída é maior que a entrada.
-
Construa a árvore de Huffman para a mensagem
"banana". Calcule a frequência de cada caractere, desenhe a árvore e determine o código de cada um. -
Usando os códigos do exercício 3, codifique
"banana". Quantos bits a versão comprimida usa? Compare com ASCII (8 bits por caractere). - Explique por que o código de Huffman produz um código de prefixo. Por que a propriedade de prefixo é importante para a decodificação?
- O código de Huffman é construído a partir das frequências específicas de um texto. Se você usar esse mesmo código para comprimir outro texto, pode ser menos eficiente. Por quê? Como emissor e receptor coordenam qual código usar?
- Na compressão LZW, por que o descompressor não precisa receber o dicionário? Como ele o reconstrói?
-
Aplique LZW (dicionário inicial: A=0, B=1, C=2) para comprimir
"ABABCABABC". Mostre as entradas adicionadas ao dicionário e os códigos emitidos. - Um arquivo de texto de 1 MB é comprimido com Huffman e passa a 450 KB. Outro arquivo de 1 MB com conteúdo muito uniforme (por exemplo, todos os bytes iguais a 'A') é comprimido com RLE e passa a 10 bytes. Qual método atinge melhor taxa para sua entrada específica? O Huffman poderia comprimir o arquivo de 'A's tão bem?
Gabaritos
Sugestão de resposta — Exercício 1
Os runs da entrada (20 caracteres):
| entrada | W | W | W | W | B | W | W | W | W | W | W | W | B | B | B | W | W | W | W | W |
| 4 × W | 1 × B | 7 × W | 3 × B | 5 × W | ||||||||||||||||
| saída RLE | 4W | 1B | 7W | 3B | 5W |
Representação comprimida: 4W1B7W3B5W (10 caracteres).
Razão de compressão: 10 / 20 = 0,5, ou seja, redução de 50%.
Sugestão de resposta — Exercício 2
Quando os runs têm comprimento 1 (nenhum caractere se repete consecutivamente), o RLE precisa escrever o par (1, X) para cada caractere X, dobrando o tamanho.
Exemplo: "ABCDE" (5 bytes) → "1A1B1C1D1E" (10 bytes), uma expansão de 100%.
Sugestão de resposta — Exercício 3
Frequências:
| caractere | b | a | n |
| frequência | 1 | 3 | 2 |
Min-heap:
| Início: o min-heap começa com os caracteres já ordenados (Passo 2). Ainda não há árvore. |
| Heap agora (menor frequência primeiro): b:1 n:2 a:3 |
| Etapa 1: extrai as duas menores, b:1 (esquerda, bit 0) e n:2 (direita, bit 1); junta-as num nó novo (verde) de frequência 1 + 2 = 3 e o devolve ao heap. |
| Heap agora (menor frequência primeiro): a:3 (bn):3 |
| Etapa 2: extrai as duas menores, a:3 (esquerda, bit 0) e (bn):3 (direita, bit 1); junta-as num nó novo (verde) de frequência 3 + 3 = 6 e o devolve ao heap. Sobrou um nó: é a raiz. |
| Heap agora (menor frequência primeiro): (abn):6 |
Árvore (esquerda = 0, direita = 1):
Códigos:
| Caractere | Frequência | Código | Bits por caractere | Bits no texto (freq × bits) |
|---|---|---|---|---|
| a | 3 | 0 | 1 | 3 × 1 = 3 |
| b | 1 | 10 | 2 | 1 × 2 = 2 |
| n | 2 | 11 | 2 | 2 × 2 = 4 |
| Total | 9 bits | |||
Sugestão de resposta — Exercício 4
| caractere | b | a | n | a | n | a |
| código | 10 | 0 | 11 | 0 | 11 | 0 |
| bits | 2 | 1 | 2 | 1 | 2 | 1 |
Codificado: 10 0 11 0 11 0 = 9 bits.
ASCII: 6 × 8 = 48 bits.
Redução: 1 − 9/48 ≈ 81%.
Sugestão de resposta — Exercício 5
Na árvore de Huffman, os caracteres ficam apenas nas folhas. O caminho da raiz até uma folha A nunca é prefixo do caminho até outra folha B, pois chegar em A termina o caminho (A é folha e não tem filhos). Portanto, nenhum código é prefixo de outro.
Importância: sem a propriedade de prefixo, ao ler os bits seria ambíguo saber quando um código termina e o próximo começa. Com código de prefixo, a decodificação é unívoca, sem separadores entre os códigos.
Sugestão de resposta — Exercício 6
O código é ótimo apenas para a distribuição de frequências do texto original. Em outro texto as frequências são diferentes: caracteres que eram raros podem ser frequentes, recebendo códigos longos que agora são usados muitas vezes, o que aumenta o total de bits.
Coordenação: o emissor transmite a árvore de Huffman (ou a tabela de códigos) junto com o arquivo comprimido, no cabeçalho, e o receptor reconstrói a árvore antes de decodificar. Em aplicações fixas (como o JPEG), usam-se tabelas de Huffman padrão, acordadas previamente.
Sugestão de resposta — Exercício 7
O descompressor começa com o mesmo dicionário inicial que o compressor (os caracteres individuais). A cada código recebido, ele sabe qual string foi emitida e pode deduzir qual nova entrada o compressor adicionou naquele passo: a string anterior concatenada com o primeiro caractere da string atual. Assim, o dicionário é reconstruído passo a passo, sempre um passo atrás do compressor, o que basta para decodificar corretamente. (O único caso especial é quando o código lido ainda não existe no dicionário: a string é então a anterior + o primeiro caractere da anterior.)
Sugestão de resposta — Exercício 8
Dicionário inicial: A : 0 B : 1 C : 2
| Passo | Entrada | O que acontece | Saída até aqui | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 |
| AB não está no dicionário. Então: (1) emite o código de A, que é 0; (2) cadastra AB : 3; (3) w recomeça em B. | 0 | ||||||||||
| 2 |
| BA não está no dicionário. Então: (1) emite o código de B, que é 1; (2) cadastra BA : 4; (3) w recomeça em A. | 01 | ||||||||||
| 3 |
| AB já está no dicionário (código 3). Então o padrão cresce: w passa a ser AB. Nada é emitido. | 01 | ||||||||||
| 4 |
| ABC não está no dicionário. Então: (1) emite o código de AB, que é 3; (2) cadastra ABC : 5; (3) w recomeça em C. | 013 | ||||||||||
| 5 |
| CA não está no dicionário. Então: (1) emite o código de C, que é 2; (2) cadastra CA : 6; (3) w recomeça em A. | 0132 | ||||||||||
| 6 |
| AB já está no dicionário (código 3). Então o padrão cresce: w passa a ser AB. Nada é emitido. | 0132 | ||||||||||
| 7 |
| ABA não está no dicionário. Então: (1) emite o código de AB, que é 3; (2) cadastra ABA : 7; (3) w recomeça em A. | 01323 | ||||||||||
| 8 |
| AB já está no dicionário (código 3). Então o padrão cresce: w passa a ser AB. Nada é emitido. | 01323 | ||||||||||
| 9 |
| ABC já está no dicionário (código 5). Então o padrão cresce: w passa a ser ABC. Nada é emitido. | 01323 | ||||||||||
| 10 |
| Acabou a entrada. Emite o código do w que sobrou, ABC: 5. | 013235 |
Saída:
| saída | 0 | 1 | 3 | 2 | 3 | 5 |
Dicionário ao final:
| código | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| string | A | B | C | AB | BA | ABC | CA | ABA |
6 códigos ([0, 1, 3, 2, 3, 5]) no lugar de 10 caracteres.
Sugestão de resposta — Exercício 9
O RLE atinge uma razão absurda neste caso: 10 bytes / 1 048 576 bytes ≈ 0,001% do tamanho original.
O Huffman, com o arquivo “todo A”, produziria um código de 1 bit para 'A' (o único símbolo), resultando em 1 048 576 bits = 128 KB, muito pior que os 10 bytes do RLE.
O Huffman não consegue explorar a localidade (repetições consecutivas): ele só explora a frequência global. Para dados altamente repetitivos e uniformes, o RLE é imbatível. Para texto natural, com caracteres variados, o Huffman e o LZW são superiores.