LZ78

LZ78 foi um dos algoritmos de compressão de dados desenvolvidos por Abraham Lempel e Jacob Ziv em 1978, juntamente com o outro algoritmo de compressão LZ77 publicado em 1977. Nos primeiros artigos publicados eles eram conhecidos por LZ1 e LZ2 (LZ77 e LZ78 respectivamente) e só depois ganharam o ano de sua publicação em suas siglas.

O algoritmo LZ78 se baseia na construção de um dicionário com os dados encontrados anteriormente no arquivo a ser comprimido. No início o dicionário se encontra vazio. A medida que o arquivo vai sendo lido, caractere por caractere, cada sequência de caracteres não encontrada no dicionário é introduzida no dicionário e ganha um código. As sequências que já se encontram no dicionário são substituídas pelo seu código no dicionário.

Existem diversas variantes desse algoritmo, entre elas o LZW que se tornou famoso pela facilidade de implementação. Entretanto, várias partes tanto do LZ78 quanto do LZW estavam sujeitas a restrições por patentes, e por isso não puderam se tornar populares durante algum tempo.

Algoritmo

O algoritmo LZ78 usa um dicionário (que chamaremos de D) para armazenar as sequências de caracteres encontradas no arquivo, e usa os códigos (posição das sequências no dicionário, ou mesmo um número atribuído sequencialmente às sequências de caracteres encontradas).

Ao ler um caractere do arquivo, procuramos em D para ver se ele já se encontra lá. Caso seja encontrado, lemos o próximo caractere, concatenamos no que já havíamos lido, e procuramos a nova sequência, agora de dois caracteres no dicionário. Enquanto as sequências já estiverem presentes no dicionário, o algoritmo continua lendo e concatenando. Finalmente, quando encontramos um caractere que concatenado à sequência não está presente no dicionário, emitimos na saída um par (D_seq, c) onde D_seq é o código da ultima sequência encontrada no dicionário e c é o caractere que "quebrou" a sequência. Depois de emitir o par na saída, introduzimos a nova sequência terminada em c no dicionário e começamos tudo novamente.

Para que o algoritmo funcione precisamos de inserir inicialmente no dicionário (geralmente sob o código 0) a cadeia vazia (uma entrada no dicionário representando uma cadeia de tamanho zero). Assim, ao ler um caractere c nunca antes lido pelo programa, é emitido na saída o par (0, c).

Um pseudo-código representando este algoritmo está a seguir:

cadeia := '' # inicializa com a cadeia de tamanho 0
D.insere(cadeia)
enquanto c := leia_novo_caractere()
   se D contém cadeia concatenada com c
      cadeia := cadeia concatenada com c
   senão
      imprime_na_saida([D.código(cadeia), c])
      D.insere(cadeia concatenada com c)
      cadeia = ''
   fim se
 fim enquanto
 imprime_na_saida([D.código(cadeia), ''])

A decodificação se dá de forma similar, começamos com o dicionário apenas com o código para a cadeia vazia, e vamos lendo os pares de (D_seq, c). Para cada par lido, emitimos na saída a sequência presente no dicionário sob o código D_seq, concatenada com o caractere c. Em seguida adicionamos esta nova sequência no dicionário. Note que o algoritmo de manutenção do dicionário (atribuição de códigos às sequências) deve ser o mesmo no programa que codifica e no que decodifica, para não termos inconsistências.

Exemplo

Para exemplificar o uso do algoritmo vamos aplicá-lo à entrada "A_ASA_DA_CASA". A tabela abaixo representa cada passo (determinado pela leitura de um novo caractere na entrada), com as respectivas saídas, quando ocorrerem, e o conteúdo do dicionário (expresso na forma [código:cadeia, código:cadeia, … código:cadeia]):

c	cadeia	saída	D
A	''	(0, 'A')	[0:'', 1:'A']
_	''	(0, '_')	[0:'', 1:'A', 2:'_']
A	''	-	-
S	'A'	(1, 'S')	[0:'', 1:'A', 2:'_', 3:'AS']
A	''	-	-
_	'A'	(1, '_')	[0:'', 1:'A', 2:'_', 3:'AS', 4:'A_']
D	''	(0, 'D')	[0:'', 1:'A', 2:'_', 3:'AS', 4:'A_', 5:'D']
A	''	-	-
_	'A'	-	-
C	'A_'	(4, 'C')	[0:'', 1:'A', 2:'_', 3:'AS', 4:'A_', 5:'D', 6:'A_C']
A	''	-	-
S	'A'	-	-
A	'AS'	(3, 'A')	[0:'', 1:'A', 2:'_', 3:'AS', 4:'A_', 5:'D', 6:'A_C', 7:'ASA']
EOF	''	(0, '')	-

A sequência de saída seria da forma: (0,'A')(0,'_')(1,'S')(1,'_')(0,'D')(4,'C')(3,'A'). Se usarmos três bits para representar os códigos das entradas do dicionário (valor máximo de 7) e um byte para os caracteres normais teríamos um total de 77 bits para representar a sequência (originalmente com 104 bits—13 caracteres com um byte por caractere).

Problemas

O clássico problema dos algoritmos baseados em dicionários é a memória necessária. Quanto mais lemos dados do arquivo, mais sequências armazenamos no dicionário, e com isso, necessitamos de mais memória. O outro problema que isso causa é de espaço de endereçamento: os códigos das entradas no dicionário crescem junto com ele (em geral ocupam $log_{2}(N)$ bits, onde N é o tamanho, ou número de entradas, do dicionário). Várias abordagens podem ser adotadas para lidar com esse problema, as mais simples são:

• Congelamento do dicionário (quando o dicionário atinge o tamanho limite, ele fica "congelado" e mais nenhuma entrada pode ser adicionada nele).
• Esvaziamento (o dicionário é esvaziado e a compressão começa toda de novo). Essa técnica pressupõe que é mais vantajoso usar a redundância local que a redundância global para a compressão. corresponde a separar o arquivo em "blocos" comprimidos separadamente.
• Uso de uma política de esvaziamento que seja comum tanto ao compressor quanto ao descompressor (apagar entradas mais antigas, por exemplo).

Outro problema, esse específico do LZ78, é o crescimento lento do dicionário. Devido a característica de inserir as cadeias no dicionário assim que um único caractere quebra a sequência faz com que o dicionário cresça de forma lenta e só se torne realmente útil depois de bastante informação lida. Esse problema torna o LZ78 e seus derivados pouco apropriado para comprimir quantidades muito pequenas de dados. A abordagem dada pelo LZ77 pode ser útil nos casos onde o crescimento lento do dicionário venha a reduzir a compressão.

Bibliografia

• ZIV, Jacob, LEMPEL, Abraham; Compression of Individual Sequences Via Variable-Rate Coding, IEEE Transactions on Information Theory, September 1978.