Dados comprimidos por Ziv e Lempel apontando de volta para o texto já enviado

A compressão clássica girava em torno da codificação de Huffman, mas Huffman precisa de um modelo de probabilidades de símbolos construído antes de poder codificar. Até 1977, a maior parte do trabalho assumia que esse modelo tinha de vir de algum lugar.

Em 'A Universal Algorithm for Sequential Data Compression', Jacob Ziv e Abraham Lempel, do Technion, mostraram que o modelo podia ser dispensado. O codificador mantém uma janela de texto visto recentemente e compara o buffer de antecipação que chega com ela; uma correspondência é escrita como um deslocamento e um comprimento, de modo que a repetição custa quase nada.

O resultado é um esquema universal — ele comprime qualquer fonte sem estatísticas prévias, porque o dicionário é os próprios dados. O artigo de 1977 é o clássico que fez da compressão por dicionário a base do gzip, do PNG e da família ZIP.

Apontar de volta para o texto já visto em vez de pré-computar

Usar o texto já enviado como dicionário dispensa uma tabela de probabilidades pré-computada.

Um único token de deslocamento mais comprimento trata qualquer frase repetida, longa ou curta.

O esquema funciona em fontes desconhecidas, portanto é universal em vez de ajustado a um tipo de arquivo.

Não construa um modelo dos dados antecipadamente; deixe os dados fornecerem sua própria estrutura à medida que avança. Uma representação autorreferencial se adapta a qualquer entrada, seja ela qual for.

A abordagem LZ tornou-se a base da compressão sem perdas moderna: o LZ77 e seu descendente LZ78/LZW alimentam o gzip, o zip, o PNG e o fluxo DEFLATE usado em toda a web. Os artigos de Ziv e Lempel receberam o Prêmio de Inovação Tecnológica do Jubileu de Ouro de 1997 da IEEE Information Theory Society.