Introdução
O algoritmo Lempel Ziv (LZ) surgem na década de 1970 por Jacob Ziv e Abraham Lempel em trabalhos realizados em 1977 (LZ77) e 1978 (LZ78). Estes algoritmos são largamente usados, na compressão de dados sem perdas, em aplicações como o gzip, GIF e o standard de modem V.42, e encaixam na categoria de técnicas de codificação de entropia, mais concretamente nas técnicas de codificação baseada em dicionários, logo aplica-se a qualquer tipo de dados binário.
Áreas de aplicação
Tal como já foi anteriormente referido, estes codecs são utilizados em aplicações como o zip, gzip, gif, standard V.42, imagens gif, compress (Unix), e outros.
Algoritmo LZ78
De acordo com ( Salomon,2007) o método LZ78 não necessita de um buffer de pesquisa, um buffer look-ahead ou janela flutuante. Em vez disso existe um dicionário de strings previamente encontradas. Esse dicionário começa vazio ou quase vazio e o seu tamanho é limitado somente pela quantidade de memória disponível. O codificador envia sinais de dois campos. O primeiro campo é um apontador para o dicionário; o segundo é um código de um símbolo. Os tokens não contêm o comprimento de uma string, porque isso está implícito no dicionário. Cada token corresponde a uma string de entrada de símbolos e essa string é adicionada ao dicionário depois de o token ser escrito no ficheiro comprimido. Nada é eliminado do dicionário, o que é uma vantagem em relação ao LZ77.
O dicionário inicializa com a string nula na posição zero. Enquanto os símbolos são recebidos e codificados , as strings são adicionadas no dicionário nas posições 1,2 e assim sucessivamente. Quando o próximo símbolo x é lido a partir da entrada, o dicionário é procurado para uma entrada com o símbolo de uma string x. Se numa for encontrada, x é adicionado na próxima posição disponível no dicionário, e o token (0,x) é a saída. Este token indica a string “nula x” (uma concatenação da string nula e x). Se uma entrada com x é encontrada, o próximo símbolo y é lido e o dicionário é procurado para uma entrada contendo a string de dois símbolos xy. Se nenhum é encontrado , então a string xy é adicionada à próxima posição disponível no dicionário e o token (37,y) é a saída. Este token indica a string xy, desde que 37 é a posição no dicionário da string x. O processo continua até que a extremidade da entrada é atingida.
Geralmente, o símbolo actual é lido e torna-se uma string de um símbolo. O codificador então tenta encontra-lo no dicionário. Se o símbolo for encontrado no dicionário, o próximo símbolo é lido e é concatenado como o primeiro para formar uma string de dois símbolos que o codificador então tenta localizar no dicionário. Até que essas strings sejam encontradas no dicionário, mais símbolos são lidos e concatenados à string. A um certo ponto a string não é encontrada no dicionário, de modo que o codificador adiciona-a ao dicionário e gera um token com a última correspondência no dicionário como o seu primeiro campo e o último símbolo da string como o seu segundo campo.
Codificação
A codificação consiste em construir um dicionário com os símbolos que vão aparecendo repetidos no código e fazer referência à entrada no dicionário desses mesmos símbolos:
- O output da codificação consiste em criar um código composto por um índice da entrada do dicionário que corresponde à sequência de símbolos iguais mais longa existente no dicionário (i), e o primeiro símbolo diferente (c): (i, c)
- Aquando do output, são acrescentados ao dicionário o índice e o símbolo diferente.
- Quando o símbolo a ser codificado ainda não existe no dicionário, i assume o valor de 0 e é, para além do output, acrescentado ao dicionário também.
- O Dicionário começa sempre com a primeira entrada vazia
Algoritmo de codificação LZ78
INICIO
ENQUANTO não chegar ao fim do ficheiro
D = null (inicialmente o dicionário não contém nenhuma sequência).
word = null.
ENQUANTO houver símbolos para codificar
SE word + c é uma sequência presente no dicionário
word = word + c
c = próximo símbolo
SENÃO
Enviar código (índice (word), c)
Actualizar dicionário com word + c
word = null
FIM
Exemplo de codificação LZ78
Exemplo de codififação LZ78 a cadeia A A o A A D E E A A F F F F A A o A A
Voltando a utilizar os mesmos dados originais, abaixo é explicado como este algoritmo codifica os dados, sendo o output um código “duplo” (i, c) onde i é o índice do dicionário e c é o próximo símbolo:
1ª Iteração:
enquanto (há dados a serem codificados)
w <- nulo (w é o código a ser codificado)
k <- próximo símbolo do fluxo de dados
(K=A)
(w + k ) = nulo + A = A : não existe no dicionário, que só tem uma entrada com nulo
enquanto (w + k) existe no dicionário
w <- w + k
output( índiceDicionário(w), k)
como w = nulo, existe na posição 0 do dicionário:
OUTPUT= 0 , A
adicionar (w+k) ao dicionário
Dicionário:
|
Posição |
Conteúdo |
|
0 |
nulo |
|
1 |
A |
Output :
(0,A)
2ª Iteração:
enquanto (há dados a serem codificados)
w <- nulo
k <- próximo símbolo do fluxo de dados
(K=A)
1º iter.: (w + k )=nulo + A = A : Existe no dicionário, na posição 1
2º iter.: (w + k )=A + 0 = A : Não existe no dicionário
enquanto (w + k) existe no dicionário
w <- w + k
w=Nulo + A
k <- próximo símbolo do fluxo de dados
(K = 0)
output( índiceDicionário(w), k)
como w = A, que existe na posição 1 do dicionário:
OUTPUT= 1 , 0
adicionar (w+k) ao dicionário
Dicionario:
|
Posição |
Conteúdo |
|
0 |
nulo |
|
1 |
A |
|
2 |
A0 |
Output:
(0,A)
(1,0)
3ª Iteração:
enquanto (há dados a serem codificados)
w <- nulo
k <- próximo símbolo do fluxo de dados
(K=A)
1º iter.: (w + k )=nulo + A = A : Existe no dicionário, na posição 1
2º iter.: (w + k )=A + A = AA : Não existe no dicionário
enquanto (w + k) existe no dicionário
w <- w + k
w=Nulo + A
k<- próximo símbolo do fluxo de dados
(K = A)
output( índiceDicionário(w), k)
como w = A, que existe na posição 1 do dicionário:
OUTPUT= 1 ,A
adicionar (w+k) ao dicionário
Dicionário:
|
Posição |
Conteúdo |
|
0 |
Nulo |
|
1 |
A |
|
2 |
A0 |
|
3 |
AA |
Output:
(0,A)
(1,0)
(1,A)
As restantes iterações são exactamente iguais, e o resultado é:
Dicionário:
|
Posição |
Conteúdo |
|
0 |
nulo |
|
1 |
A |
|
2 |
A0 |
|
3 |
AA |
|
A |
D |
|
5 |
E |
|
6 |
EA |
|
7 |
AF |
|
8 |
F |
|
9 |
FF |
|
10 |
AA0 |
Output final:
(i, c)
(0, A)
(1, 0)
(1, A)
(0, D)
(0, E)
(5, A)
(1, F)
(0, F)
(8, F)
(3, 0)
(1, A)
Descodificação
- A descodificação consiste em descodificar para um buffer de output o código composto pelo “duplo” (i, c).
- Na altura de descodificação para o buffer de output, é criada uma entrada no dicionário que irá ser usada pelos “duplos” seguintes para referir as repetições de símbolos.
Algoritmo de descodificação LZ78
INICIO
ENQUANTO não chegar ao fim do ficheiro
D = null (inicialmente o dicionário não contém nenhuma sequência).
word = null.
ENQUANTO houver pares de word com c(codeword,char)
word = próximo codeword
c = próximo caracter
Enviar código (word no dicionário equivalente a word) + c
Actualizar (word no dicionário equivalente a word) + c no dicionario
FIM
Exemplo de descodificação LZ78
Exemplo da descodificação LZ78 para a cadeia A A 0 A A D E E A A F F F F A A 0 A A
A descodificação consiste começar com um dicionário cuja primeira entrada é igual a nulo, tal como na codificação, acrescentar entradas ao dicionário se i = 0 e respectivo output, ou, se i <> 0, ler a entrada no dicionário correspondente ao índice i, e acrescentar c.
1ª Iteração:
Enquanto não chega ao fim do ficheiro (EOF)
x<- próximo índice i
(X = 0)
c<- próximo símbolo c
(C = A)
output <- entrada no dicionário(x) + c
(OUTPUT = nulo + A)
adicionar (entrada no dicionário(x) + c) na próxima localização livre
Dicionário:
| Posição | Conteúdo |
| 0 | nulo |
| 1 | A |
Output = A
2ª Iteração:
Enquanto não chega ao fim do ficheiro (EOF)
x<- próximo índice i
(X = 1)
c<- próximo símbolo c
(C = 0)
output <- entrada no dicionário(x) + c
(OUTPUT = A + 0)
adicionar (entrada no dicionário(x) + c) na próxima localização livre
Dicionário:
|
Posição |
Conteúdo |
|
0 |
nulo |
|
1 |
A |
|
2 |
A0 |
Output = A + A0
3ª Iteração:
Enquanto não chega ao fim do ficheiro (EOF)
x<- próximo índice i
(X = 2)
c<- próximo símbolo c
(C = A)
output <- entrada no dicionário(x) + c
(OUTPUT = A + A)
adicionar (entrada no dicionário(x) + c) na próxima localização livre
Dicionário:
|
Posição |
Conteúdo |
|
0 |
Nulo |
|
1 |
A |
|
2 |
A0 |
|
3 |
AA |
Output = A + A0 + AA
4ª Iteração:
Enquanto não chega ao fim do ficheiro (EOF
x <- próximo índice i
(X = 0)
c <- próximo símbolo c
(C = D)
output entrada no dicionário(x) + c
(OUTPUT = nulo + D)
adicionar (entrada no dicionário(x) + c) na próxima localização livre
Dicionario:
|
Posição |
Conteúdo |
|
0 |
Nulo |
|
1 |
A |
|
2 |
A0 |
|
3 |
AA |
|
4 |
D |
Output= A + A0 + AA + D
Restantes iterações são exactamente iguais, e o resultado é:
A A 0 A A D E E A A F F F F A A 0 A A
Outro exemplo de aplicação
Como exemplo vamos aplicar o algoritmo na codificação e descodificação, passo a passo, à seguinte string: “a date at a date”
Codificação
Vamos guardar os valores de w, c, output e do dicionário para cada iteração.
Inicialmente o dicionário está vazio.
Descodificação
Descodificação de “0a0␣0d1t0e2a0t6␣3a7e”
Vamos guardar os valores de x, c, output e do dicionário para cada iteração.
Inicialmente o dicionário está vazio.
E assim recuperamos a string original: “a date at a date”
Implementação do algoritmo “LZ78”
A aplicação foi desenvolvida em Java. Reaproveitou-se o código já existente nessa mesma linguagem, acrescentando uma interface gráfica.
Inicialmente houve algumas dificuldades na compreensão desse código, tendo-o que adaptar ao que se idealizava
Em relação ao código, foram usadas as APIs “in” e “out” da princeton, para facilitar a utilização de ficheiros.
Comparação com outros métodos semelhantes
Para o exemplo utilizado para demonstrar os algoritmos de compressão e descompressão temos os
seguintes valores:
- Comprimento do ficheiro original: 19 Bytes
LZ77:
- Comprimento do ficheiro (Output) comprimido : 10 x 3 = 30 Bytes
LZ78:
- Comprimento do ficheiro (Output) comprimido : 11 x 2 = 22 Bytes
Como o ficheiro usado, para efeitos de demonstração do funcionamento dos algoritmos, é muito pequeno,
assistimos a uma expansão ao invés de uma compressão.
Utilizo outro ficheiro para efeitos de teste à capacidade/eficiência de compressão do qual abaixo coloco
um pequeno excerto, para que se possa ver que tipo de ficheiro se está a tratar:
(…)bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCccccc(…)
- Tamanho do ficheiro original: 9436 Bytes
LZ77:
- Comprimento do ficheiro de output: 6308 Bytes
- São necessários cerca de 0,67 Bytes por símbolo, sendo o rácio de compressão de 1,49 : 1
LZ78:
- Comprimento do ficheiro de output: 4276 Bytes
- São necessários cerca de 0,46 Bytes por símbolo, sendo o rácio de compressão de 2,17 : 1
Conclusão
Podemos concluir que este método não se poderá aplicar a quantidades de dados pequenas, sob pena de se utilizarem mais bytes para codificar do que os bytes que o ficheiro original contem.
Com a execução deste trabalho, consegui compreender como se consegue representar informação de forma diferente, embora que por vezes com recurso a mecanismos e métodos complexos.
Bibliografia
Salomon, D., “Data Compression The complete”, Reference 4ed Springer, 4th. Edition, 2007.
Trabalho desenvolvido no âmbito da disciplina de Multimédia II da Licenciatura em Engenharia Informática, lecionada pelo Prof. Doutor Nuno Magalhães Ribeiro da Faculdade de Ciência e Tecnologia da UFP.
Texto da autoria de Carina Santos (nº 24410), José Latourrette (nº 26333), Suse Ribeiro (nº 29565), Teresa Campante (nº 27798) e revisto por Nuno Magalhães Ribeiro.
Código javascript da autoria de Carina Santos (nº 24410), José Latourrette (nº 26333), Suse Ribeiro (nº 29565), Teresa Campante (nº 27798).
Site planeado, desenhado, desenvolvido e programado por Daniel Dias Lima Mendes, Diogo Emanuel Lamas e Silva, Nelson José Santos Almeida no âmbito do Projeto de final de Licenciatura realizado na Unidade Curricular de Laboratório de Projeto Integrado sob a orientação técnica do Prof. Doutor Nuno Magalhães Ribeiro.