← Computação

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

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

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

      ⌈log⁡2(W+1)⌉+⌈log⁡2(B+1)⌉+8=⌈log⁡217⌉+⌈log⁡29⌉+8=5+4+8=17 bits\lceil\log_2(W{+}1)\rceil+\lceil\log_2(B{+}1)\rceil+8=\lceil\log_2 17\rceil+\lceil\log_2 9\rceil+8=5+4+8=17\ \mathrm{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,∅)(0,0,\mathtt{a})\ (0,0,\mathtt{b})\ (0,0,\mathtt{r})\ (3,1,\mathtt{c})\ (5,1,\mathtt{d})\ (7,4,\varnothing)

    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.

      11×81×17=8817=5.18×\frac{11\times8}{1\times17}=\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.

      11×86×17=88102=0.86×\frac{11\times8}{6\times17}=\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.

      NT>178=2.125,NT=116=1.83\frac{N}{T}>\frac{17}{8}=2.125,\qquad \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.

    NT>⌈log⁡2(W+1)⌉+⌈log⁡2(B+1)⌉+88\frac{N}{T}>\frac{\lceil\log_2(W{+}1)\rceil+\lceil\log_2(B{+}1)\rceil+8}{8}

Percurso de aprendizagem

Compressão manual

Referências (1)

· Verificado com fontes publicadas. Correções bem-vindas.