Resumo

Neste artigo científico pretende-se descrever de forma detalhada o algoritmo de codificação e descodificação LZW.

Inicia-se com uma breve explicação sobre a origem do algoritmo e também se apresenta exemplos concretos para a sua aplicação através de um “script” em JavaScript.

1. Introdução

O Algoritmo LZW (Lempel–Ziv–Welch), que irá ser abordado neste artigo, resulta do melhoramento efetuado por Terry Welch dos algoritmos LZ77 e LZ78, os quais foram desenvolvidos por Jacob ZIV e Abraham Lempel, respetivamente. Inicialmente, foi desenhado a pensar no número de bits que se poderia reduzir aquando do envio de ficheiros armazenados nos discos, mas tem vindo a ser usado em muitos outros contextos.

Trata-se de um algoritmo de compressão de dados baseado num dicionário que produz códigos de comprimento fixo associados a sequências de símbolos de comprimento variável. Os códigos gerados durante o processo, tanto de codificação como de descodificação, correspondem a sequências de símbolos cada vez mais longas, que vão sendo adicionadas ao dicionário.

O LZW é um modo de compressão sem perdas (CSP), o que significa que o fluxo de dados descomprimidos é exatamente igual ao fluxo de dados originais, não se perdendo qualquer informação.

1.1 Objetivos do trabalho

O principal objetivo deste artigo é explicar passo a passo o funcionamento da codificação e descodificação do algoritmo LZW. Para esse efeito, foram utilizados dois exemplos:

• um exemplo estático com várias tabelas que explicam cada passo do algoritmo;
• um exemplo dinâmico implementado através de um “script” em JavaScript.

Pretende-se, igualmente, que sirva como uma ferramenta de apoio didático.

1.2 Justificação

O algoritmo LZW foi o escolhido por ser um dos codecs mais utilizados atualmente por ser simples e por ter um rácio de compressão muito bom em ficheiros binários e ficheiros de texto a partir de uma determinada dimensão.

1.3 Áreas de aplicação

O LZW é uma das principais técnicas usadas para a compressão de dados devido à sua simplicidade e versatilidade. Normalmente, é usado na codificação de ficheiros de imagens do tipo GIF e TIFF, ficheiros do tipo ZIP e RAR e também em diversos programas de software, uma vez que não há qualquer tipo de perda de informação após a codificação.

2. O algoritmo LZW

O 1º passo deste método de compressão consiste na criação de um “dicionário de arranque” usando códigos de 8 ou 12 bits (atualmente, apenas se utiliza códigos de 12 ou mais bits, porque dão, no mínimo, para 4096 (2¹²) entradas na tabela). Por norma, é usado o código ASCII ou o UTF8 para a criação deste dicionário, cujos caracteres ocupam as primeiras 256 linhas da tabela e as restantes irão sendo acrescentadas com o conjunto de símbolos encontrados no ficheiro durante o processo de codificação e descodificação.

Tanto na codificação como na descodificação, os dados do ficheiro terão que ser lidos símbolo-a-símbolo para se poder proceder à sua codificação e descodificação, comparando sempre cada símbolo do ficheiro com os existentes no dicionário.

2.1 Codificação

Como já foi referido anteriormente, o ficheiro com os dados de entrada terá que ser lido símbolo-a-símbolo e cada linha da tabela irá ser preenchida com cada um desses símbolos de acordo com o algoritmo a seguir descrito.

Pseudo-código do Algoritmo de Codificação

S = primeiro símbolo do fluxo de dados de entrada
DO
c = próximo símbolo do fluxo de dados de entrada (Si)
IF (S + c) existir no dicionário
S = S + c
ELSE
Saída = código de S
Adicionar (S + c) ao dicionário, criando um novo código
S = c
WHILE (c < > EOF)
Saída = código de S (último símbolo)

Este algoritmo irá dar origem a uma tabela que contém o dicionário de arranque e que terá o seguinte cabeçalho:

2.1.1 Exemplo de aplicação

Para explicar o funcionamento deste algoritmo, considere-se como exemplo uma sequência de caracteres composta por 15 símbolos de 8 bits cada um:

“LAILAALAALAALAA”

Na codificação, pretende-se obter um código comprimido que utilize um número muito menor de bits do que na sequência original. Na descodificação, pretende-se obter a sequência original decifrando o código comprimido.

1º Passo – Criação do dicionário de arranque:

A sequência de caracteres apresentada tem apenas 3 símbolos distintos (L, A, I).

O processo é iniciado com a criação do dicionário de arranque constituído por símbolos de 12 bits (o que dá para conter 4096 símbolos distintos). Neste exemplo, o dicionário irá somente incluir cada um dos símbolos distintos existentes na sequência original juntamente com um código numérico atribuído a cada símbolo:

Dicionário de arranque = {1-A, 2-I, 3-L}

2º Passo – Construção da tabela incluindo apenas o dicionário de arranque:

3º Passo – Leitura da sequência símbolo-a-símbolo e início do preenchimento:

S = “LAILAALAALAALAA”

1ª linha: S = 1º símbolo;

c = próximo símbolo da sequência (2º símbolo);

Saída = código de S;

Sequência = (S + c), porque o conjunto de símbolos “LA” (S + c) não existe na coluna Sequência;

Código = novo número (código criado para o novo símbolo adicionado);

S = “LAILAALAALAALAA”

2ª linha: S = c da linha anterior;

c = próximo símbolo da sequência (3º símbolo);

Saída = código de S;

Sequência = (S + c), porque o conjunto de símbolos “AI” (S + c) não existe na coluna Sequência;

Código = novo número;

S = “LAILAALAALAALAA”

3ª linha: S = c da linha anterior;

c = próximo símbolo da sequência (4º símbolo);

Saída = código de S;

Sequência = (S + c), porque o conjunto de símbolos “IL” (S + c) não existe na coluna Sequência;

Código = novo número;

S = “LAILAALAALAALAA”

4ª linha: S = c da linha anterior;

c = próximo símbolo da sequência (5º símbolo);

Saída = em branco;

Sequência = em branco, porque o conjunto de símbolos “LA” (S+c) já existe

S = “LAILAALAALAALAA”

5ª linha: S = (S + c), porque na linha anterior (S + c) já existia na sequência;

c = próximo símbolo da sequência (6º símbolo);

Saída = código de S;

Sequência = (S + c), porque o conjunto de símbolos “LAA” (S+c) não existe na coluna Sequência;

Código = novo número;

S = “LAILAALAALAALAA”

6ª linha: S = c da linha anterior;

c = próximo símbolo da sequência (7º símbolo);

Saída = código de S;

Sequência = (S + c), porque o conjunto de símbolos “AL” (S+c) não existe na coluna Sequência;

Código = novo número;

S = “LAILAALAALAALAA”

7ª linha: S = c da linha anterior;

c = próximo símbolo da sequência (8º símbolo);

Saída = em branco;

Sequência = em branco, porque o conjunto de símbolos “LA” (S+c) já existe na coluna Sequência, portanto não é preciso adicioná-lo ao dicionário;

Código = em branco;

S = “LAILAALAALAALAA”

8ª linha: S = (S + c), porque na linha anterior (S + c) já existia na sequência;

c = próximo símbolo da sequência (9º símbolo);

Saída = em branco;

Sequência = em branco, porque o conjunto de símbolos “LAA” (S+c) já existe na coluna Sequência, portanto não é preciso adicioná-lo ao dicionário;

Código = em branco;

S = “LAILAALAALAALAA”

9ª linha: S = (S + c), porque na linha anterior (S + c) já existia na sequência;

c = próximo símbolo da sequência (10º símbolo);

Saída = código de S;

Sequência = (S + c), porque o conjunto de símbolos “LAAL” (S+c) não existe na coluna Sequência;

Código = novo número;

S = “LAILAALAALAALAA”

10ª linha: S = c da linha anterior;

c = próximo símbolo da sequência (11º símbolo);

Saída = em branco;

Sequência = em branco, porque o conjunto de símbolos “LA” (S+c) já existe na coluna Sequência, portanto não é preciso adicioná-lo ao dicionário;

Código = em branco;

S = “LAILAALAALAALAA”

11ª linha: S = (S + c), porque na linha anterior (S + c) já existia na sequência;

c = próximo símbolo da sequência (12º símbolo);

Saída = em branco;

Sequência = em branco, porque o conjunto de símbolos “LAA” (S+c) já existe na coluna Sequência, portanto não é preciso adicioná-lo ao dicionário;

Código = em branco;

S = “LAILAALAALAALAA”

12ª linha: S = (S + c), porque na linha anterior (S + c) já existia na sequência;

c = próximo símbolo da sequência (13º símbolo);

Saída = em branco;

Sequência = em branco, porque o conjunto de símbolos “LAAL” (S+c) já existe na coluna Sequência, portanto não é preciso adicioná-lo ao dicionário;

Código = em branco;

S = “LAILAALAALAALAA”

13ª linha: S = (S + c), porque na linha anterior (S + c) já existia na sequência;

c = próximo símbolo da sequência (14º símbolo);

Saída = código de S;

Sequência = (S + c), porque o conjunto de símbolos “LAALA” (S+c) não existe na coluna Sequência;

Código = novo número;

S = “LAILAALAALAALAA”

14ª linha: S = c da linha anterior;

c = próximo símbolo da sequência (15º símbolo);

Saída = código de S;

Sequência = (S + c), porque o conjunto de símbolos “AA” (S+c) não existe na coluna Sequência;

Código = novo número;

S = “LAILAALAALAALAA” (Final do ficheiro – EOF)

15ª linha: S = c da linha anterior;

c = EOF (End of File);

Saída = código de S;

Sequência = em branco;

Código = em branco;

Pode-se verificar, quando se atinge o final da sequência, que o dicionário foi sendo atualizado dinamicamente com sequências progressivamente mais longas, e que o codificador gerou o seguinte fluxo de dados comprimidos contendo 9 códigos:

Código comprimido = 312417911 (todos os números da coluna “Saída”)

Comparando a sequência de dados de entrada com o código comprimido conclui-se que o número de símbolos passou dos 15 caracteres iniciais para 9 códigos. Se considerarmos que cada um dos caracteres de entrada se representa recorrendo a 1 byte (8 bits) e que cada código LZW ocupa 12 bits, o rácio de compressão resultante pode ser determinado do seguinte modo:

É importante referir que a aplicação do algoritmo LZW apenas começa a obter alguma compressão após algumas centenas de iterações, isto é, após o processamento de algumas centenas de caracteres contidos no ficheiro de entrada.

2.2 Descodificação

A técnica de descodificação do Algoritmo LZW funciona de um modo análogo à técnica de descodificação. É iniciada com a leitura símbolo-a-símbolo do código comprimido obtido na codificação do fluxo de dados de entrada e vai adicionando ao dicionário de arranque sequências cada vez mais longas conforme se ilustra na exemplificação. De referir que a descodificação apenas necessita de conhecer o dicionário de arranque.

Pseudo-código do Algoritmo de Descodificação original

S = NULL
DO
c = próximo símbolo do código comprimido
cadeia = símbolo da Sequência do dicionário correspondente ao código c
Escrever cadeia no ficheiro de saída
IF (S <> NULL)
Sequência = S + cadeia[0] e respetivo Código = novo código
S = cadeia
WHILE (c < > EOF)

Este algoritmo tem um problema que reside no facto do ritmo de descodificação poder ultrapassar o ritmo com que os símbolos foram codificados. Isto é, o descodificador faz a leitura de um código que ainda não existe no seu dicionário. Este problema apenas ocorre quando existe uma sequência consecutiva de caracteres que se repete, no mínimo, quatro vezes.

Para solucionar este problema foram efetuadas alterações ao algoritmo de descodificação, adicionando um teste que verifica se o código que é lido do fluxo de dados comprimidos já existe no dicionário. Caso não exista, é necessário adicioná-lo.

Pseudo-código do Algoritmo de Descodificação modificado

S = NULL
DO
c = próximo símbolo do código comprimido
cadeia = símbolo da Sequência do dicionário correspondente ao código c
IF (cadeia = = NULL)
cadeia = S + S[0]
Escrever cadeia no ficheiro de saída
IF (S <> NULL)
Sequência = S + cadeia[0] e respetivo Código = novo código
S = cadeia
WHILE (c <> EOF)

2.2.1 Exemplo de Aplicação

Considerando o exemplo da sequência de caracteres usado na exemplificação da codificação:

“LAILAALAALAALAA”

Código comprimido = 312417911

1º Passo – Construção da tabela incluindo o dicionário de arranque usado na codificação:

2º Passo – Leitura do código comprimido símbolo-a-símbolo e início do preenchimento:

c = “312417911”

1ª linha: c = primeiro símbolo do código;

S = NULL;

Cadeia = Sequência correspondente ao código de c;

Sequência = em branco;

Código = em branco;

c = “312417911”

2ª linha: c = próximo símbolo do código;

S = Cadeia da linha anterior;

Cadeia = Linha da coluna Sequência correspondente ao código de c;

Sequência = S + Cadeia[0], porque S é diferente de Null;

Código = novo número;

c = “312417911”

3ª linha: c = próximo símbolo do código;

S = Cadeia da linha anterior;

Cadeia = Linha da coluna Sequência correspondente ao código de c;

Sequência = S + Cadeia[0], porque S é diferente de Null;

Código = novo número;

c = “312417911”

4ª linha: c = próximo símbolo do código;

S = Cadeia da linha anterior;

Cadeia = Linha da coluna Sequência correspondente ao código de c;

Sequência = S + Cadeia[0], porque S é diferente de Null;

Código = novo número;

c = “312417911”

5ª linha: c = próximo símbolo do código;

S = Cadeia da linha anterior;

Cadeia = Linha da coluna Sequência correspondente ao código de c;

Sequência = S + Cadeia[0], porque S é diferente de Null;

Código = novo número;

c = “312417911”

6ª linha: c = próximo símbolo do código;

S = Cadeia da linha anterior;

Cadeia = Linha da coluna Sequência correspondente ao código de c;

Sequência = S + Cadeia[0], porque S é diferente de Null;

Código = novo número;

c = “312417911”

7ª linha: c = próximo símbolo do código;

S = Cadeia da linha anterior;

Cadeia = ERRO! Não existe nenhum código na coluna Sequência correspondente ao código de c;

O código 9 ainda não foi criado no dicionário, logo não pode ser descodificado! O algoritmo modificado resolve este problema preenchendo a coluna Cadeia com S + S[0].

c = “312417911”

7ª linha: c = próximo símbolo do código;

S = Cadeia da linha anterior;

Cadeia = S + S[0], porque c não existe na coluna código do dicionário

Sequência = S + Cadeia[0], porque S é diferente de Null;

Código = novo número;

c = “312417911”

8ª linha: c = próximo símbolo do código;

S = Cadeia da linha anterior;

Cadeia = S + S[0], porque c não existe na coluna código do dicionário

Sequência = S + Cadeia[0], porque S é diferente de Null;

Código = novo número;

c = “312417911”

9ª linha: c = próximo símbolo do código;

S = Cadeia da linha anterior;

Cadeia = S + S[0], porque c não existe na coluna código do dicionário

Sequência = S + Cadeia[0], porque S é diferente de Null;

Código = novo número;

c = “312417911”

10ª linha:  c = EOF (End of File);

S = Cadeia da linha anterior;

Cadeia = em branco;

Sequência = em branco;

Código = em branco;

3. Implementação do algoritmo LZW em JavaScript

Durante o desenvolvimento do nosso projeto, deparámo-nos com algumas dificuldades. A principal destas dificuldades foi tentar criar um script que simulasse uma animação sem ter que pressionar um botão para passar cada fase do algoritmo.

Com base em diversas pesquisas efetuadas, optámos por modelar o nosso script num paradigma de “nesting” e de “delays”, ou seja, a solução encontrada consiste na execução de uma função na finalização de uma outra e no atraso na execução de funções ou instruções de código.

De acordo com os nossos conhecimentos em JavaScript, este modelo era o mais acessível para implementarmos. O “Nesting” foi necessário porque o Javascript é uma linguagem de programação com uma execução “single-threaded” e assíncrona. O “Delay” foi necessário para permitir a visualização do script no ecrã o tempo suficiente de forma a permitir uma leitura adequada do algoritmo e o seu consequente entendimento.

Para a instalação do programa criado em JavaScript são necessárias as seguintes bibliotecas:

• jQuery 2.2+
• Bootstrap 3
• MathJax 2.6+

Exemplo de organização das bibliotecas:

• /LZW/jquery/
• /LZW/css/
• /LZW/mathjax/
• /LZW/js/
• /LZW/LZW_encode.html
• /LZW/LZW_decode.html

Algoritmo de Descodificação LZW em javascript

Algoritmo de Codificação LZW em javascript

4. Comparação com outros métodos semelhantes

Comparando os algoritmos LZW e Huffman pode-se concluir que ambos têm resultados muito semelhantes quando são usados na compressão de ficheiros de texto. Já quando são usados na compressão de ficheiros binários, o algoritmo LZW apresenta um rácio de compressão melhor, porque consegue representar vários dígitos binários consecutivos com um único código, enquanto que no algoritmo de Huffman cada dígito binário é representado por uma sequência de 2 bits, resultando, desta forma, num código comprimido maior em termos de número de bits.

Também na compressão de ficheiros de imagem do tipo BMP, o LZW é mais bem-sucedido que o Huffman, uma vez que substitui conjuntos de pontos por um único código.

No caso dos ficheiros do tipo GIF ou do tipo TIFF, apesar do LZW ser bastante usado, não é muito eficiente em termos de rácio de compressão devido às sequências consecutivas de pixéis serem bastante variadas, ou seja, estas repetem-se poucas vezes.

Tabela de Comparação entre LZW e Huffman

Tabela de Comparação entre LZW, Huffman, LZH e HLZ

5. Conclusão

Após a conclusão deste trabalho, constatámos que o LZW é um codec eficiente, de baixa complexidade e muito rápido quer na compressão quer na descompressão. A sua utilização justifica-se mais em ficheiros binários e de texto, porque para ficheiros de imagem existem outros algoritmos mais eficientes em termos de rácio de compressão, como por exemplo, o RLE.

Com a implementação deste algoritmo na forma de um programa em JavaScript torna-se bastante mais acessível a sua compreensão, pois consegue-se visualizar passo a passo a codificação/descodificação de qualquer sequência de símbolos introduzida no respetivo campo.

Futuramente, o programa criado em JavaScript poderá ser otimizado permitindo a codificação e descodificação de ficheiros de imagem e alterando o output da codificação para código binário, em que cada símbolo é representado por 12 bits.

Bibliografia

• Ribeiro, Nuno M., Torres, José, “Tecnologias de Compressão Multimédia”, FCA – Editora de Informática, 2009.
• Mengyi Pu, Ida, “Fundamental Data Compression”, Elsevier, 2006
• Penfield, Paul, “Course on Compression”, MIT, 2003
• Salomon, D., “Data Compression”, Springer, 4^th. Edition, 2002
• http://www.iaeorg/publication/WCECS2007/WCECS2007_pp326-336.pdf

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 Cláudia Faria (27742), Patrícia Silva (28028) e Rafael Pacheco (29795) e revisto por Nuno Magalhães Ribeiro.

Código javascript da autoria de Cláudia Faria (27742), Patrícia Silva (28028) e Rafael Pacheco (29795).

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.