Como a compressão de ficheiros funciona de verdade: Huffman Coding, LZ77 e DEFLATE explicados

Todo o programador já trabalhou com ficheiros comprimidos. Extraes um pacote, serves uma resposta codificada em gzip, ou exportas um PNG — e a compressão acontece por baixo do capô. Mas a pergunta que a maioria dos tutoriais evita é: porquê funciona? Porque é que podes pegar num ficheiro de texto de 500 KB e reduzi-lo a 180 KB sem perder um único byte, mas não consegues comprimir mais um ficheiro ZIP?

A resposta está na teoria da informação e num punhado de algoritmos elegantes. Este artigo percorre a mecânica real: da entropia de Shannon às árvores de Huffman, passando pelo formato DEFLATE que sustenta ZIP, gzip e PNG.

Porque é que os ficheiros são comprimíveis

Os ficheiros são comprimíveis porque contêm redundância — padrões, repetições e sequências previsíveis que transportam menos informação do que o seu número bruto de bytes sugere.

Considera um exemplo simples. A cadeia AAAAAAAAAA (dez A) ocupa 10 bytes em ASCII. Mas o conteúdo informativo é trivial: poderias descrevê-la perfeitamente como "dez A". Um algoritmo de compressão faz exatamente isso — substitui dados verbosos e redundantes por uma descrição mais curta.

Os ficheiros reais estão cheios deste tipo de redundância:

• O texto em português reutiliza constantemente palavras comuns e combinações de letras. "que", "ção", "mente" aparecem muito mais frequentemente do que "xqz".
• O código fonte tem uma estrutura profundamente repetitiva: function, return, const, níveis de indentação, linhas em branco.
• As imagens bitmap contêm longas sequências horizontais de pixels idênticos ou quase idênticos — especialmente em áreas de cor plana.
• Os ficheiros de registo repetem timestamps, nomes de host e códigos de estado milhares de vezes.

Quanto mais redundantes forem os dados, mais comprimíveis são. Quanto menos redundantes — quanto mais aleatórios — mais difícil se torna comprimi-los.

Entropia: o limite absoluto da compressão

O artigo de Claude Shannon de 1948, A Mathematical Theory of Communication, introduziu uma forma precisa de medir o conteúdo de informação: a entropia, medida em bits.

A entropia de Shannon responde à pergunta: quantos bits precisas realmente, em média, para representar um símbolo desta fonte de dados?

A fórmula para uma fonte com símbolos s₁, s₂, ..., sₙ e probabilidades p₁, p₂, ..., pₙ é:

H = -Σ pᵢ × log₂(pᵢ)

Na prática, isto significa: suponhamos que tens um ficheiro com apenas dois caracteres — A (aparece 90% das vezes) e B (aparece 10% das vezes).

H = -(0.9 × log₂(0.9)) - (0.1 × log₂(0.1))
H = -(0.9 × -0.152) - (0.1 × -3.322)
H ≈ 0.137 + 0.332
H ≈ 0.469 bits por símbolo

Uma codificação ingénua usa 1 bit por símbolo (0 para A, 1 para B). Mas a entropia diz que o mínimo teórico é 0,469 bits por símbolo — menos de metade. Um bom algoritmo de compressão aproxima-se desse limite.

Considera agora um ficheiro verdadeiramente aleatório onde cada valor de byte (0–255) aparece com igual probabilidade (1/256 cada):

H = -(256 × (1/256) × log₂(1/256))
H = log₂(256) = 8 bits por byte

Oito bits por byte — entropia máxima. Não há redundância a explorar. É por isso que não consegues comprimir mais um ficheiro ZIP: já está perto da entropia máxima. Cada bit transporta informação; não restam padrões a eliminar.

Codificação por comprimento de sequência: a forma mais simples

Antes de chegar aos algoritmos mais pesados, a codificação por comprimento de sequência (RLE) ilustra a ideia central de forma clara.

O RLE substitui uma sequência de símbolos repetidos por um contador e o símbolo:

Original:  AAABBBBBCCDDDDDD
RLE:       3A 5B 2C 6D

Original: 16 caracteres. Codificado: 8 caracteres. Redução de 50%.

O RLE é usado na transmissão de fax (CCITT Grupo 3/4), ficheiros BMP e como subpasso dentro de formatos mais complexos. A sua fraqueza é óbvia: tem um desempenho fraco em dados sem longas sequências repetidas. A cadeia ABABABAB não tem sequências, pelo que o RLE torna-a maior ao antepor contadores de 1 em todo o lado.

Essa fraqueza é precisamente o que impulsiona abordagens mais sofisticadas.

Huffman Coding: códigos mais curtos para símbolos frequentes

No ASCII padrão, cada carácter recebe 8 bits independentemente da frequência com que aparece. O Huffman Coding quebra esse pressuposto. Os símbolos frequentes recebem códigos mais curtos; os símbolos raros recebem códigos mais longos. O comprimento médio do código diminui e o ficheiro encolhe.

Construir uma árvore de Huffman

Pega na cadeia AABBBCCCC (9 caracteres). Conta as frequências:

Passo 1. Coloca cada símbolo num nó folha ponderado pela sua frequência.

[A:2]  [B:3]  [C:4]

Passo 2. Funde repetidamente os dois nós de menor peso num nó pai cujo peso é a sua soma, até restar apenas uma árvore.

Funde [A:2] e [B:3] → pai [AB:5]:

      [AB:5]
      /     \
   [A:2]  [B:3]

[C:4]

Funde [C:4] e [AB:5] → raiz [ABC:9]:

         [ABC:9]
         /      \
      [C:4]  [AB:5]
              /    \
           [A:2]  [B:3]

Passo 3. Atribui códigos percorrendo a árvore: aresta esquerda = 0, aresta direita = 1.

Calcular a poupança de bits

Com os códigos de Huffman, codificar AABBBCCCC custa:

A × 2 ocorrências × 2 bits = 4 bits
B × 3 ocorrências × 2 bits = 6 bits
C × 4 ocorrências × 1 bit  = 4 bits
Total = 14 bits

Com ASCII fixo de 8 bits:

9 caracteres × 8 bits = 72 bits

14 bits vs. 72 bits — uma redução de 81% neste exemplo de brinquedo. Os ganhos reais são menores, mas o princípio mantém-se. O texto em português tipicamente comprime para 4–5 bits por carácter com Huffman sozinho, a partir de 8.

A ideia fundamental: os códigos de Huffman são livres de prefixo. Nenhum código é prefixo de outro, o que significa que um descodificador pode reconstruir inequivocamente o fluxo original sem separadores. A estrutura da árvore em si é armazenada no cabeçalho do ficheiro comprimido para que o descodificador a possa reconstruir.

LZ77 e LZ78: explorar sequências repetidas

O Huffman Coding trabalha com frequências individuais de símbolos. Mas ignora uma classe maior de redundância: as sequências repetidas. A palavra function no código fonte ocupa 8 bytes cada vez que aparece. Se pudesses substituir a segunda e as seguintes ocorrências por um apontador para a primeira, pouparias significativamente.

É exatamente o que Abraham Lempel e Jacob Ziv descreveram nos seus artigos de 1977 e 1978, dando-nos LZ77 e LZ78.

LZ77: compressão por janela deslizante

O LZ77 mantém uma janela deslizante — um buffer de dados vistos recentemente. À medida que o codificador processa novos dados, olha para trás através da janela para encontrar a correspondência mais longa com o que vem a seguir. Se encontrar uma, emite uma referência posterior (deslocamento, comprimento) em vez dos bytes literais.

Considera codificar a cadeia:

abcabc

Processando abc: sem histórico anterior, emite literais a, b, c.

Processando o segundo abc: o codificador olha para trás e encontra abc começando 3 posições atrás, com comprimento 3. Emite a referência posterior (deslocamento=3, comprimento=3) em vez de três bytes literais.

O descodificador, ao ver (3, 3), recua 3 posições no seu buffer de saída e copia 3 bytes — reconstruindo abc perfeitamente.

Numa implementação real, a pesquisa de correspondências é limitada pelo tamanho da janela (o gzip usa uma janela de 32 KB). Uma janela maior encontra mais correspondências mas custa mais memória e tempo de pesquisa.

A referência posterior (deslocamento, comprimento) tem tipicamente 2–3 bytes. Portanto, substituir uma sequência repetida de 10 bytes por uma referência de 2 bytes poupa 8 bytes. Quanto mais longa for a correspondência, melhor o rácio.

LZ78 e LZW

O LZ78 constrói um dicionário explícito de padrões encontrados em vez de usar uma janela deslizante. O LZW (Lempel-Ziv-Welch), um derivado, tornou-se famoso como o algoritmo por detrás da compressão GIF e do utilitário compress do Unix. O LZW codifica padrões como índices de dicionário únicos, fazendo crescer o dicionário dinamicamente durante a codificação e descodificação.

DEFLATE: LZ77 mais Huffman Coding

O DEFLATE, definido na RFC 1951, combina LZ77 e Huffman Coding em sequência:

1. Passagem LZ77: Substitui sequências repetidas por referências posteriores (deslocamento, comprimento). A saída é um fluxo de literais e referências posteriores.
2. Passagem Huffman: Aplica Huffman Coding a esse fluxo. Os literais frequentes recebem códigos curtos; os valores de referência posterior raros recebem códigos mais longos.

As duas técnicas atacam diferentes tipos de redundância. O LZ77 elimina a repetição de longo alcance. O Huffman Coding elimina então a redundância baseada em frequência no que resta. Juntos, atingem rácios de compressão que nenhum dos algoritmos sozinho conseguiria.

Os dados DEFLATE estão organizados em blocos. Cada bloco pode usar um de três modos:

• Sem compressão — para dados onde a compressão expandiria a saída (dados já aleatórios)
• Códigos Huffman fixos — uma tabela de códigos pré-acordada, poupando o overhead de armazenar uma árvore personalizada
• Códigos Huffman dinâmicos — uma árvore personalizada otimizada para este bloco específico, armazenada no cabeçalho do bloco

O modo dinâmico é usado para a maioria dos dados comprimíveis. O codificador analisa o bloco, constrói uma árvore Huffman ótima, armazena-a no início do bloco e depois codifica os dados usando essa árvore.

Onde o DEFLATE vive nos formatos de ficheiro reais

ZIP

Os ficheiros ZIP armazenam cada entrada de forma independente com o seu próprio fluxo comprimido com DEFLATE. Esta compressão por entrada significa que podes extrair um único ficheiro de um ZIP sem descomprimir todo o arquivo. O formato ZIP também suporta um modo "armazenado" (sem compressão) para ficheiros que já estão comprimidos.

gzip

O gzip envolve um único fluxo DEFLATE com um cabeçalho (número mágico, SO, hora de modificação) e uma soma de verificação CRC32. É o formato de compressão padrão para HTTP Content-Encoding: gzip e para arquivos .tar.gz. A extensão .gz é sempre um único fluxo DEFLATE.

PNG

O PNG usa DEFLATE (via zlib) para comprimir os seus dados de pixels. Antes da compressão, o PNG aplica um passo de filtragem: transforma cada linha de pixels em diferenças relativamente a uma previsão (codificação delta). Isto aumenta dramaticamente as sequências e repetições que o LZ77 pode explorar, melhorando significativamente a compressão. Para capturas de ecrã e diagramas típicos, o PNG comprime para 20–50% do tamanho dos dados de pixels brutos. As ferramentas de compressão de imagem que exportam PNG dependem desta cadeia de processamento.

zlib

O zlib é um formato envolvente em torno do DEFLATE — adiciona um cabeçalho de dois bytes e uma soma de verificação Adler-32. Os fluxos PDF usam zlib/DEFLATE ao comprimir conteúdo incorporado (a compressão de PDF reduz o tamanho do ficheiro recomprimindo ou removendo esses fluxos). HTTP, WebSockets e muitos protocolos de rede também usam zlib.

JPEG: uma abordagem diferente

Vale a pena fazer uma pausa aqui porque o JPEG usa uma estratégia de compressão completamente diferente — uma que perde dados deliberadamente.

O JPEG aplica uma Transformada Discreta do Cosseno (DCT) a blocos de 8×8 pixels. A DCT converte os valores dos pixels em componentes de frequência (semelhante a uma transformada de Fourier). Os componentes de alta frequência — detalhes finos — são então quantizados de forma agressiva (arredondados para valores mais grosseiros ou descartados completamente). Os coeficientes restantes são codificados com Huffman Coding, mas o passo de quantização com perdas é o que torna o JPEG muito menor do que o PNG para fotografias.

A contrapartida: o JPEG não consegue reconstruir perfeitamente os pixels originais. O PNG consegue. Esta é a distinção com perdas vs. sem perdas explorada em profundidade no nosso artigo sobre conversão de ficheiros com e sem perdas.

Para uma fotografia, o JPEG com qualidade 80 pode usar 10% dos bytes que um PNG sem perdas precisaria. Para uma captura de ecrã com cores planas e bordas nítidas, o PNG normalmente ganha porque os artefactos DCT são visíveis e o DEFLATE comprime regiões planas de forma excelente.

Porque é que não consegues comprimir mais um ficheiro ZIP

Esta é uma fonte comum de confusão. Se a compressão funciona encontrando padrões, porque é que comprimir um ficheiro já comprimido produz quase nada?

Porque o DEFLATE está a fazer o seu trabalho corretamente. Um fluxo DEFLATE bem comprimido parece estatisticamente aleatório — por design. As referências posteriores e os códigos Huffman eliminam os padrões previsíveis. O que resta está perto do limite de entropia dos dados.

Passa um segundo compressor sobre ele e não encontrará sequências (o LZ77 não encontra correspondências longas) nem viés de frequência (o Huffman vê uma distribuição de símbolos quase uniforme). A entropia já é 7,9+ bits por byte. Não há mais nada a explorar.

É também por isso que nunca deves comprimir media já comprimida. Empacotar um JPEG dentro de um ZIP custa-te o overhead do ZIP sem qualquer benefício de tamanho. O mesmo se aplica a MP3, MP4, HEIC — todos são formatos comprimidos que já estão perto do seu tecto de entropia.

Comparação de algoritmos

Juntando tudo

A cadeia desde dados brutos até bytes comprimidos para um ficheiro comprimido com gzip tem este aspeto:

1. Entrada: Fluxo de bytes brutos (ex.: um ficheiro de texto)
2. LZ77: Procura referências posteriores com uma janela deslizante de 32 KB, produzindo um fluxo de literais e pares (deslocamento, comprimento)
3. Huffman Coding: Constrói duas árvores — uma para literais/comprimentos, outra para deslocamentos — e codifica a saída do LZ77
4. Blocos DEFLATE: Empacota as árvores Huffman e os dados codificados num ou mais blocos
5. Envolvente gzip: Antepõe o cabeçalho gzip, adiciona o CRC32 e o tamanho do ficheiro original
6. Saída: Ficheiro .gz, tipicamente 30–70% menor para entrada comprimível

A descompressão funciona estritamente ao contrário: analisa o cabeçalho gzip, lê e reconstrói as árvores Huffman a partir dos cabeçalhos dos blocos, descodifica o fluxo Huffman de volta em tokens LZ77, aplica referências posteriores para reconstruir o fluxo de bytes original. A descompressão é sempre mais rápida do que a compressão porque o trabalho pesado (procurar correspondências ótimas, construir árvores ótimas) é feito apenas uma vez.

Principais conclusões

• Os ficheiros são comprimíveis porque contêm redundância — padrões repetidos e frequências de símbolos enviesadas.
• A entropia de Shannon define o piso absoluto: os dados verdadeiramente aleatórios não podem ser comprimidos porque cada bit já transporta informação.
• O RLE lida com a repetição de forma grosseira. O Huffman Coding lida com o viés de frequência de forma elegante. O LZ77 lida com a repetição de sequências de longo alcance.
• O DEFLATE encadeia LZ77 e Huffman em sequência, razão pela qual supera qualquer um dos algoritmos sozinho. É o motor dentro do ZIP, gzip, PNG e fluxos PDF comprimidos com zlib.
• O JPEG adota uma abordagem fundamentalmente diferente: quantização DCT com perdas seguida de Huffman sem perdas, trocando precisão de pixels por redução dramática de tamanho.
• Comprimir um ficheiro comprimido não alcança nada porque uma boa compressão produz uma saída de entropia quase máxima.

Compreender estes algoritmos é útil quando estás a escolher um formato, a diagnosticar ficheiros inesperadamente grandes, ou a depurar uma cadeia de compressão. Da próxima vez que usares a compressão de PDF, extraíres um ficheiro ZIP ou exportares um PNG para compressão de imagem, saberás exatamente o que o software está a fazer aos teus bits.