> lz77 | sliding | window <
// LZ77 – compressão com janela deslizante e referências de dicionário
Codificação por dicionário
Referência padrões repetidos usando deslocamento e comprimento.
Janela deslizante
Mantém uma janela móvel para encontrar o maior padrão correspondente.
Algoritmo base
Fundamento de ZIP, GZIP, DEFLATE e PNG.
>> informações técnicas
Como o LZ77 funciona:
LZ77 mantém uma janela deslizante de dados vistos recentemente. Para cada posição, o algoritmo procura dentro da janela a maior substring que coincide. Se encontrar, emite uma referência (deslocamento, comprimento, próximo caractere). Caso contrário, emite um literal (0,0,caractere). Assim, padrões repetidos são substituídos por referências curtas, proporcionando compressão sem perdas.
Exemplo de LZ77:
Text: "ABCABCABC" Window=4, Lookahead=4 Position 0: 'A' - no match → (0,0,A) Position 1: 'B' - no match → (0,0,B) Position 2: 'C' - no match → (0,0,C) Position 3: 'ABC' - matches at offset 3 → (3,3,A) Position 7: 'BC' - matches at offset 3 → (3,2,) Output: (0,0,A)(0,0,B)(0,0,C)(3,3,A)(3,2,)
Por que usar LZ77?:
- ▸Compressão sem perdas
- ▸Dispensa conhecimento prévio do formato dos dados
- ▸Adapta-se aos padrões presentes nos dados
- ▸Implementação relativamente simples
- ▸Base de muitos algoritmos modernos de compressão
>> perguntas frequentes
O que é LZ77?
LZ77 é um algoritmo universal de compressão de dados sem perdas, publicado por Abraham Lempel e Jacob Ziv em 1977. Ele substitui repetições no fluxo de dados por referências a uma única cópia que apareceu anteriormente no fluxo não comprimido.
Como funciona a janela deslizante?
A janela deslizante é composta por um buffer de busca (dados já processados) e um buffer de lookahead (dados a serem comprimidos). O algoritmo procura no buffer de busca a maior correspondência com o início do buffer de lookahead e em seguida emite uma referência ou um literal.
LZ77 vs algoritmos modernos?
LZ77 é a base de muitos esquemas de compressão atuais. DEFLATE, usado em ZIP e GZIP, combina LZ77 com codificação de Huffman. LZSS reduz a redundância em LZ77, enquanto LZ78 e LZW constroem o dicionário de forma diferente, mantendo os mesmos princípios.
Quais tamanhos de janela são recomendados?
Para dados gerais, tamanhos de janela típicos variam de 32 KB a 64 KB. Janelas maiores encontram mais correspondências, mas consomem mais memória e tempo. DEFLATE usa 32 KB. O buffer de lookahead costuma ter de 256 a 512 bytes. O melhor tamanho depende dos padrões de repetição dos seus dados.
// Exemplo resolvido
| # | Offset | Length | Next | Output |
|---|---|---|---|---|
| 1 | 0 | 0 | a | a |
| 2 | 0 | 0 | b | b |
| 3 | 0 | 0 | r | r |
| 4 | 3 | 1 | c | a + c |
| 5 | 2 | 1 | d | a + d |
| 6 | 7 | 4 | — | abra |
// Exemplos de código
Input abracadabra (positions 0..10)
Token (offset, length, next)
offset = distance back into the window, length = bytes copied
Decode copy `length` bytes starting `offset` back, then append `next`
(the copy may overlap its own output, e.g. (1,5,x) repeats a byte)
Window the sliding search buffer; deflate/gzip use 32 KiB
>> Mais perguntas
P: O que significa a tripla (deslocamento, comprimento, caractere)?
R: O deslocamento indica quanto se recua na janela já vista, o comprimento quantos bytes são copiados, e o caractere é o próximo byte novo. O decodificador reconstrói a saída passo a passo.
P: Por que a cópia pode se sobrepor?
R: Se o deslocamento é menor que o comprimento, a cópia lê bytes que acabou de escrever. Assim surgem repetições: (1, 5, x) produz cinco vezes o caractere anterior.
P: Onde o LZ77 é usado?
R: O LZ77 está no DEFLATE (gzip, zlib, PNG, ZIP) e, em variantes, no LZ4, Snappy, Zstandard e Brotli. O tamanho da janela e a estratégia de busca definem taxa e velocidade.