Compressão de Dados, Áudio, Imagem e Vídeo

Comprimir é reescrever uma sequência de bits x num fluxo y = E(x), em geral mais curto. O decodificador D devolve x bit a bit no contrato sem perdas, ou uma aproximação x̂ no contrato com perdas.

Huffman, RLE, LZW e a quantização da DCT neste tópico — e a codificação de imagens no processamento de imagens — partem desses dois contratos.

As páginas se agrupam em quatro blocos. O primeiro justifica cortar bytes no disco e no canal, separa os dois contratos, e mostra que nenhum E sem perdas encolhe toda sequência de n bits.

O segundo explora redundância sem alterar x: Huffman minimiza o comprimento esperado L com códigos livres de prefixo; RLE troca a corrida pelo par (contagem, símbolo).

O terceiro aprende frases: o LZW emite o código de w, insere w+c na tabela reconstruída nos dois lados e alarga cada código para ⌈log₂ n⌉ bits.

O quarto descarta o que o olho ou o ouvido mal resolve. JPEG quantiza coeficientes da DCT por Q(u,v); MP3 marca o inaudível e o mascarado.

Compressão Sem Perda monta a árvore de Huffman e o RLE. Compressão LZW cadastra frases numa trie e não envia a tabela.

O contrato D(E(x)) = x versus x̂, e a contagem de gavetas que impede o compressor universal, estão em Compressão de Dados. DCT, F(u,v)/Q(u,v) e psicoacústica estão em Compressão com Perda.

Huffman depois da quantização JPEG está em Compressão Sem Perda. O arredondamento que zera agudos e impede recuperar x está em Compressão com Perda.

Corrida em área uniforme está em Compressão Sem Perda. Zerar AC de um bloco 8×8 está em Compressão com Perda.