INF01203 - Estruturas de Dados - Instituto de Informática (UFRGS) - Prof. Dennis Giovani Balreira



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ânciaExemploMétodo que a explora
Repetições consecutivasAAAAAAAA pode ser dito como “8 vezes A”RLE
Símbolos com frequências desiguaisem textos, o 'e' é muito mais comum que o 'z': faz sentido dar a ele um código mais curtoHuffman
Padrões (substrings) repetidosas mesmas palavras ou frases reaparecem várias vezes no arquivoLZW

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).

ExemploRazãoReduçãoBits por símbolo
1 MB → 300 KB300 / 1000 = 0,370%—
20 caracteres → 10 (RLE de AAABBBCCCCDDDDDDDDDE)10 / 20 = 0,550%—
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étodoO que exploraIdeia em uma frase
RLErepetições consecutivastroca AAAA por “4 vezes A”
Huffmana frequência dos símboloscódigos curtos para o que é comum, longos para o que é raro
LZWpadrões (substrings) repetidosmonta 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

  1. Percorra a entrada da esquerda para a direita.
  2. Conte quantos caracteres iguais aparecem em sequência (o run).
  3. Escreva o par contagem + caractere e recomece no próximo caractere diferente.

Entrada: AAABBBCCCCDDDDDDDDDE (20 caracteres). Cada letra tem uma cor, e os runs estão marcados embaixo:

entradaAAABBBCCCCDDDDDDDDDE
3 × A3 × B4 × C9 × D1 × E
saída RLE3A3B4C9D1E

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:

CasoEntradaSaída RLEResultado
Bom: muitas repetiçõesAAABBBCCCCDDDDDDDDDE
20 bytes
3A3B4C9D1E
10 bytes
−50%
Melhor caso: áreas uniformes (imagem P&B)22×W + 8×B
30 bytes
22W8B
5 bytes
−83%
Ruim: sem repetiçõesABCDEFGH
8 bytes
1A1B1C1D1E1F1G1H
16 bytes
+100% (EXPANSÃO!)

Melhor caso — imagem com áreas uniformes (22 pixels brancos e 8 pretos):

entradaWWWWWWWWWWWWWWWWWWWWWWBBBBBBBB
22 × W8 × B
saída RLE22W8B

Caso ruim — nenhum caractere se repete, então cada run tem comprimento 1 e o arquivo comprimido fica maior que o original:

entradaABCDEFGH
saída RLE1A1B1C1D1E1F1G1H

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.
  1. Criar um nó para cada caractere, com sua frequência.
  2. Enquanto existir mais de um nó:
    1. Escolher os dois nós de menor frequência.
    2. Criar um novo nó com a soma das frequências.
    3. Colocar o menor à esquerda e o maior à direita.
    4. Remover os dois nós originais da fila de prioridade.
    5. Inserir o novo nó na fila de prioridade.
  3. O nó restante será a raiz da árvore.
  4. Percorrer a árvore:
    • Esquerda = 0
    • Direita = 1
  5. 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:

caractereabrcd
frequência52211

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:

caracterecdbra
frequência11225

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.
0 1 c freq 1 d freq 1 2 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.
0 1 0 1 c freq 1 d freq 1 2 b freq 2 r freq 2 4 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.
0 0 1 1 0 1 c freq 1 d freq 1 2 b freq 2 r freq 2 4 6 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.
0 1 0 0 1 1 0 1 a freq 5 c freq 1 d freq 1 2 b freq 2 r freq 2 4 6 11 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):

0 1 0 0 1 1 0 1 a freq 5 c freq 1 d freq 1 2 b freq 2 r freq 2 4 6 11

Passo 5 — Códigos gerados (caminho da raiz até a folha):

CaractereFrequênciaCódigoBits por caractereBits no texto (freq × bits)
a5015 × 1 = 5
b211032 × 3 = 6
c110031 × 3 = 3
d110131 × 3 = 3
r211132 × 3 = 6
Total23 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”:

caractereabracadabra
código01101110100010101101110
bits13313131331
RepresentaçãoBitsObservação
ASCII original11 × 8 = 88 bits8 bits por caractere
Huffman23 bitsreduçã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):

CaractereOcorrênciasFrequência relativa pBits “merecidos” −log2 pContribuição p · (−log2 p)
a55/11 ≈ 0,45451,1370,4545 · 1,137 ≈ 0,517
b22/11 ≈ 0,18182,4590,1818 · 2,459 ≈ 0,447
r22/11 ≈ 0,18182,4590,1818 · 2,459 ≈ 0,447
c11/11 ≈ 0,09093,4590,0909 · 3,459 ≈ 0,314
d11/11 ≈ 0,09093,4590,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 lidosPercurso a partir da raizFolha: emite
0raiz →0 folha aa
110raiz →1 nó (6) →1 nó (4) →0 folha bb
111raiz →1 nó (6) →1 nó (4) →1 folha rr
0raiz →0 folha aa
100raiz →1 nó (6) →0 nó (2) →0 folha cc
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.

  1. Início: o dicionário contém todos os caracteres individuais (entradas 0 a 255 para ASCII). Faça w = primeiro caractere da entrada.
  2. Para cada próximo caractere c da entrada:
    1. Se w + c (o padrão com mais um caractere) já está no dicionário: o padrão cresce, w = w + c.
    2. 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.
  3. 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:

PassoEntradaO que aconteceSaída até aqui
1
ABABABAB
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
ABABABAB
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
ABABABAB
AB já está no dicionário (código 2). Então o padrão cresce: w passa a ser AB. Nada é emitido.01
4
ABABABAB
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
ABABABAB
AB já está no dicionário (código 2). Então o padrão cresce: w passa a ser AB. Nada é emitido.012
6
ABABABAB
ABA já está no dicionário (código 4). Então o padrão cresce: w passa a ser ABA. Nada é emitido.012
7
ABABABAB
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
ABABABAB
Acabou a entrada. Emite o código do w que sobrou, B: 1.01241

Saída comprimida:

saída01241

Dicionário ao final (azul: inicial; amarelo: criado durante a compressão):

código012345
stringABABBAABAABAB

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!):

PassoCódigo lidoEmiteNova entrada no dicionário (= anterior + 1.º caractere do que acabou de emitir)Saída até aqui
10A—A
21BA + B = AB : 2AB
32ABB + A = BA : 3ABAB
44
ainda não existe!
ABAAB + A = ABA : 4ABABABA
51BABA + B = ABAB : 5ABABABAB

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

FormatoUso do LZW
GIFLZW sobre os dados de pixels;
TIFFcompressão LZW opcional;
PDFLZW em streams;
Unix compressarquivos .Z clássicos.

4. Comparação dos métodos

CritérioRLEHuffmanLZW
Tipo de redundância exploradaRepetições consecutivasFrequência de símbolosPadrões (substrings) repetidos
Requer dicionário / árvore?NãoSim (árvore)Sim (construído durante a compressão)
Dicionário transmitido?NãoSim (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 codificarO(N) esperado
Eficiência em textoFracaBoaMuito boa
Eficiência em imagens P&BExcelenteModeradaBoa
Lossless?SimSimSim
Usado emBMP, FaxJPEG, ZIPGIF, 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

  • RLE: substitui sequências repetidas por (contagem, símbolo); simples e rápido (uma passada), ótimo para dados muito repetitivos, mas pode expandir dados com pouca repetição.
  • Huffman: constrói uma árvore binária ótima usando um min-heap de frequências; garante código de prefixo (decodificação sem separadores); eficiente para texto; requer transmitir a árvore.
  • LZW: constrói um dicionário de substrings durante a compressão; o descompressor reconstrói as entradas novas sem recebê-las (mas precisa do dicionário inicial); eficaz para texto e dados com padrões repetidos.
  • Compressão lossless recupera o original exatamente; compressão lossy descarta informação imperceptível ao ser humano (imagens, áudio).
  • Os formatos reais combinam múltiplas técnicas para maximizar a eficiência.

Material complementar


Exercícios

  1. Aplique a compressão RLE à string "WWWWBWWWWWWWBBBWWWWW". Qual é a representação comprimida? Qual é a razão de compressão?

  2. Por que o RLE pode expandir os dados para certas entradas? Dê um exemplo em que a saída é maior que a entrada.

  3. 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.

  4. Usando os códigos do exercício 3, codifique "banana". Quantos bits a versão comprimida usa? Compare com ASCII (8 bits por caractere).

  5. 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?

  6. 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?

  7. Na compressão LZW, por que o descompressor não precisa receber o dicionário? Como ele o reconstrói?

  8. 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.

  9. 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):

entradaWWWWBWWWWWWWBBBWWWWW
4 × W1 × B7 × W3 × B5 × W
saída RLE4W1B7W3B5W

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:

caractereban
frequência132

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.
0 1 b freq 1 n freq 2 3 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.
0 1 0 1 a freq 3 b freq 1 n freq 2 3 6 Heap agora (menor frequência primeiro): (abn):6

Árvore (esquerda = 0, direita = 1):

0 1 0 1 a freq 3 b freq 1 n freq 2 3 6

Códigos:

CaractereFrequênciaCódigoBits por caractereBits no texto (freq × bits)
a3013 × 1 = 3
b11021 × 2 = 2
n21122 × 2 = 4
Total9 bits

Sugestão de resposta — Exercício 4
caracterebanana
código100110110
bits212121

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

PassoEntradaO que aconteceSaída até aqui
1
ABABCABABC
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
ABABCABABC
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
ABABCABABC
AB já está no dicionário (código 3). Então o padrão cresce: w passa a ser AB. Nada é emitido.01
4
ABABCABABC
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
ABABCABABC
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
ABABCABABC
AB já está no dicionário (código 3). Então o padrão cresce: w passa a ser AB. Nada é emitido.0132
7
ABABCABABC
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
ABABCABABC
AB já está no dicionário (código 3). Então o padrão cresce: w passa a ser AB. Nada é emitido.01323
9
ABABCABABC
ABC já está no dicionário (código 5). Então o padrão cresce: w passa a ser ABC. Nada é emitido.01323
10
ABABCABABC
Acabou a entrada. Emite o código do w que sobrou, ABC: 5.013235

Saída:

saída013235

Dicionário ao final:

código01234567
stringABCABBAABCCAABA

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.