Demo do compressor LZ77

Observe a janela deslizante varrer da esquerda para a direita: a cada passo, ela encontra a referência retroativa mais longa dentro da janela de busca e emite um token (deslocamento, comprimento, literal).

Exemplo resolvido — Demo do compressor LZ77

Antecipação	[0..7] "abracada"
Tokens emitidos: 1 de 6	5.18×
Tokens de saída	(0,0,'a')

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Uma janela maior ajuda menos do que custa 🖖

Parece óbvio que uma janela de busca maior comprime melhor, já que mais histórico significa mais chances de encontrar uma correspondência. O problema é que cada ponteiro precisa poder endereçar qualquer ponto dessa janela, então alargá-la aumenta o campo de distância de todas as referências que você emite — incluindo as milhares que só precisavam voltar alguns bytes. Dobre a janela e você acrescenta um bit a todas elas, tenha isso comprado uma correspondência mais longa ou não. Esse compromisso é o motivo de o DEFLATE, o algoritmo dentro de ZIP, PNG e gzip, ter se fixado em 32 KB e ficado lá por décadas: longe o bastante para captar repetição real em texto comum, perto o bastante para os deslocamentos continuarem baratos.

Copiar em vez de repetir 🖖

Quando o algoritmo encontra texto que já leu, não volta a escrevê-lo por extenso. Regista apenas uma nota breve: «recua deslocamento caracteres e copia comprimento deles». Cada token tem aqui a forma (offset, length, literal): uma referência ao texto anterior, seguida de um caráter novo. Textos repletos de palavras ou padrões repetidos encolhem bastante; dados já aleatórios quase não se comprimem.

Quando um token vira uma longa sequência 🖖

Uma correspondência pode apontar apenas um caractere para trás e ainda assim copiar mais caracteres do que existem ali. Com offset 1, o decodificador copia cada byte no exato instante em que o escreve, de modo que um único token como (1, 5, ...) desdobra aaaaaa a partir de um só a. Assim a clássica codificação run-length (RLE) surge de graça no LZ77 — a «cópia» se sobrepõe a texto ainda em produção. Experimente o exemplo repetitivo para ver uma região de correspondência estender-se além da posição atual.

Problema resolvido na íntegra

Seis tokens de "abracadabra" com uma janela de pesquisa de 16 caracteres 5 passos
O painel indica 5,18× após um token. Determine quanto indica após todos os seis. A entrada é "abracadabra", a janela de pesquisa é de 16 carateres e o buffer de antecipação é de 8.
1. Um token é composto por três campos de largura fixa, pelo que o seu custo é determinado pelas duas definições e não pelos dados. O desvio tem de endereçar qualquer posição na janela, o comprimento qualquer valor até ao tamanho do buffer, e o literal é um byte em bruto.
  
  $⌈ lo g_{2} (W + 1)⌉ + ⌈ lo g_{2} (B + 1)⌉ + 8 = ⌈ lo g_{2} 17 ⌉ + ⌈ lo g_{2} 9 ⌉ + 8 = 5 + 4 + 8 = 17 bits$
2. O codificador varre da esquerda para a direita e escolhe a correspondência mais longa que a janela oferece. Nada se encontra atrás dos primeiros três carateres, pelo que 'a', 'b' e 'r' custam cada um um token inteiro para serem emitidos uma vez. Apenas o token final compensa o seu custo, copiando "abra" a partir da posição 0.
  
  $(0, 0, a) (0, 0, b) (0, 0, r) (3, 1, c) (5, 1, d) (7, 4, \emptyset)$
3. A razão no painel é um valor acumulado e divide a entrada inteira pela saída produzida até ao momento. Após um token, está a comparar onze carateres com dezassete bits, razão pela qual começa tão alta.
  
  $\frac{11 \times 8}{1 \times 17} = \frac{88}{17} = 5.18 \times$
4. Seis tokens a dezassete bits cada resultam em 102 bits, contra uma entrada de 88. A codificação é maior do que a coisa que codifica.
  
  $\frac{11 \times 8}{6 \times 17} = \frac{88}{102} = 0.86 \times$
5. O ponto de equilíbrio é uma divisão. Um token custa 17 bits e compra um determinado número de carateres que valem 8 bits cada, pelo que o esquema só ganha quando o token médio avança mais do que 17/8 carateres — e, destes seis, apenas o último o faz.
  
  $\frac{N}{T} > \frac{17}{8} = 2.125, \frac{N}{T} = \frac{11}{6} = 1.83$
Resposta

O painel indica 5,18× após o primeiro token e 0,86× após o sexto: a mesma cadeia de carateres, a mesma codificação, em lados opostos de 1,0. O valor que vale a pena reter é 2,125 carateres por token, que é apenas a largura do token dividida por oito, sendo este todo o teste para saber se o LZ77 ajuda uma dada entrada. Também atribui um preço a um ajuste que parece gratuito. Alargar a janela de pesquisa para 64 adiciona dois bits a cada campo de desvio e, nesta cadeia, não encontra qualquer correspondência mais longa — a análise produz os mesmos seis tokens —, pelo que a razão cai para 0,77×. Cada duplicação do alcance custa mais um bit em cada token, usado ou não.

$\frac{N}{T} > \frac{⌈ lo g _{2} ( W + 1 )⌉ + ⌈ lo g _{2} ( B + 1 )⌉ + 8}{8}$

Percurso de aprendizagem

Compressão manual

Conduz a Burrows-Wheeler a repetição medida em cadeias em vez de símbolos: uma referência retroativa que indica quanto recuar e quanto copiar.

Referências (1)

The algorithm, and the offset-1 trick block 3 turns on: J. Ziv and A. Lempel, "A universal algorithm for sequential data compression." IEEE Transactions on Information Theory 23(3), 337–343, 1977.

Pela equipa 42Math · Atualizado 2026-08-17

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Computação →

Problemas de exemplo

abracadabra → 6 tokens - «abracadabra»: 6 tokens para 11 caracteres. O último recua 7 posições e copia 4 caracteres, ou seja, «abra» inteiro numa só referência.
aabaabaabaab → 3 tokens - «aabaabaabaab»: 4 tokens para 12 caracteres. Um deles recua apenas 3 posições e copia 7 caracteres, fazendo a correspondência avançar para além do caráter que está a ser escrito. Codificação por comprimento de sequências, de graça.
the quick brown fox → 16 tokens - «the quick brown fox»: 16 tokens para 19 caracteres. A correspondência mais longa é uma única letra. Num trecho tão curto, quase não há texto anterior que possa ser reutilizado.
ATGATCGATCG → 5 tokens - «ATGATCGATCGATCG»: 6 tokens para 15 bases. A quinta referência recua 4 posições e copia 7 caracteres, sobrepondo-se a si própria, porque ATCG se repete com um período menor do que a correspondência que está a preencher.