LZW - Compressão e Descompressão

Lempel – Ziv - Welch

Pra quê

compactar???

Vamos viajar...Primeiros passos...

• Definir o lugar;• Juntar a grana;.....

• Arrumar as malas...

Vamos viajar...

Quantas malas você leva quando vai

viajar????

Nem sempre dá

para levar tudo

que você imagina!!

Por quê???

Espaço que você

imagina para as

suas malas...

Realidade...

Espaço custa caro!!!

Pra quê

compactar???

É preciso otimizar o

uso do espaço da

melhor forma

possível!!

Como ter tudo o que precisamos sem ocupar muito

espaço??

Compactando!!!

Algoritmos de Compressão

› Um minuto de um vídeo HD podeocupar mais de 1 GB.

Como colocar duas horas de filmeem um disco blu-ray de 25 GB

apenas?

Algoritmos Lempel-Ziv-Welch (LZW)

› O algoritmo Lempel-Ziv-Welch é um dosmuitos algoritmos utilizados para comprimirarquivos.

› É conhecido como um algoritmo semperdas, ou seja, durante a compressãodados não são perdidos.

› Foi criado por Abraham Lempel, Jacob Ziv eTerry Welch. Foi publicado por Welch em1984 como um refinamento do algoritmoLZ78 publicado por Lempel e Ziv, em 1978.

Algoritmo Lempel-Ziv-Welch

› Algoritmo LZW utiliza uma tabelade strings.

› Em poucas palavras, acompressão LZW substituisequências de caracteres porcódigos individuais.

› Os códigos 0-255 na tabela destrings representam bytesindividuais do arquivo de entrada eos códigos de 256 a 4.095 sãousados para representar assequências de bytes.

O que é compressão de

dados???

Compressão

› É baseada na construção de um dicionário de dados (grupo de um ou maiscaracteres) a partir do fluxo de entrada;

› Os padrões dos dados são identificados e registrados no dicionário;

› Quando é iniciado o algoritmo, verifica-se se o caractere já está inserido nodicionário;

Pseudocódigo da Compressão› As convenções adotadas são:

– raiz caracter individual– string uma sequência de um ou mais caracteres– palavra código valor associado a uma string– dicionário tabela que relaciona palavras código e strings

– P string que representa um prefixo– C caracter– cW palavra código– pW palavra código que representa um prefixo

– X <= Y string X assume o valor da string Y– X+Y concatenação das string X e Y– string(w) string correspondente à palavra código w

Pseudocódigo da Compressão1. No início o dicionário contém todas as raízes possíveis e P é vazio;2. C <= próximo caractere da sequência de entrada;3. A string P+C existe no dicionário ?

a. se sim,i. P <= P+C;

b. se não,i. coloque a palavra código correspondente a P na seqüência codificada;ii. adicione a string P+C ao dicionário;iii. P <= C;

4. Existem mais caracteres na seqüência de entrada ?a. se sim,

i. volte ao passo 2;b. se não,

ii. coloque a palavra código correspondente a P na seqüência codificada;iii. FIM.

Exemplo de Compressão

Exemplo de Compressão

Descompressão

› Na descompressão cada código é lido e comparadocom a tabela de códigos para fornecer a tradução.

› O primeiro passo é reconstruir a tabela de string damesma maneira como foi construída durante acodificação;

› Desta forma, o decodificador baseia-se em umatabela, que é idêntica a utilizada pelo codificador, eusa-a para decodificar os valores de entradasubsequentes.

Pseudocódigo da Descompressão

Exemplo de Descompressão

Exemplo de Descompressão

Índice Dicionário

1 A

2 B

3 W

1º Passo: A tabela é inicializada com todos os

valores possíveis de caracteres.

Para o nosso exemplo serão necessários apenas exibir os

caracteres que nos interessa.

Exemplo de Descompressão

Índice Dicionário

1 A

2 B

3 W

2º Passo:

pw = string.pw =cw = 3 string.cw = w

A string.cw consta na tabela;Imprime string.cw.pw = cw => pw = 3

Console:

W

Exemplo de Descompressão

Índice Dicionário

1 A

2 B

3 W

3º Passo:

pw = 3 string.pw = wcw = 1 string.cw = a

A string.cw consta na tabela;Imprime string.cw.p = w p+c = wac = aAdiciona p+c na tabela;pw = cw => pw = 3

Console:

W A

Exemplo de Descompressão

Índice Dicionário

1 A

2 B

3 W

4 wa

4º Passo:

pw = 1 string.pw = acw = 2 string.cw = b

A string.cw consta na tabela;Imprime string.cw.p = a p+c = abc = bpw = cw => pw = 2

Console:

W A B

Exemplo de Descompressão

Índice Dicionário

1 A

2 B

3 W

4 wa

5 ab

5º Passo:

pw = 2 string.pw = bcw = 2 string.cw = b

A string.cw consta na tabela;Imprime string.cw.p = b p+c = bbc = bpw = cw => pw = 2

Console:

W A B B

Exemplo de Descompressão

Índice Dicionário

1 A

2 B

3 W

4 wa

5 ab

6 bb

6º Passo:

pw = 2 string.pw = bcw = 1 string.cw = a

A string.cw consta na tabela;Imprime string.cw.p = b p+c = bac = apw = cw => pw = 1

Console:

W A B B A

Exemplo de Descompressão

Índice Dicionário

1 A

2 B

3 W

4 wa

5 ab

6 bb

7 ba

7º Passo:

pw = 1 string.pw = acw = 4 string.cw = wa

A string.cw consta na tabela;Imprime string.cw.p = a p+c = awc = wpw = cw => pw = 4

Console:

W A B B A W A

Exemplo de Descompressão

Índice Dicionário

1 A

2 B

3 W

4 wa

5 ab

6 bb

7 ba

8 aw

8º Passo:

pw = 4 string.pw = wacw = 6 string.cw = bb

A string.cw consta na tabela;Imprime string.cw.p = wa p+c = wabc = bpw = cw => pw = 6

Console:

W A B B A W A B B

Exemplo de Descompressão

Índice Dicionário

1 A

2 B

3 W

4 wa

5 ab

6 bb

7 ba

8 aw

9 wab

10 bba

9º Passo:

pw = 6 string.pw = bbcw = 1 string.cw = a

A string.cw consta na tabela;Imprime string.cw.p = bb p+c = bbac = apw = cw => pw = 1

Console:

O algoritmo terminou!

W A B B A W A B B A

Vantagens

› É muito eficaz na compressão desequências que apresentam algum tipo derepetição nos dados de entrada;

› È simples de entender;

› Rápida execução;

› Não necessita de nenhuma informação apriori sobre os dados de entrada;

› Pode comprimir dados em apenas umpasso;

› Faz a compressão e descompressão dosarquivos.

Desvantagens

› Não comprime bem sequências pequenas;

› Não comprime bem sequências com caracteres muitodiversos;

› Arquivos longos degradam a taxa de compressãoconforme o arquivo é lido.

› A razão para isso é simples. Uma vez que atabela de strings é de tamanho finito, depoisque certo número de inserções foram feitas,strings não mais podem ser adicionadas.

Considerações Finais

› Este método de compressão sem perdas é de baixa complexidade,pelo fato de o LZW usar como seu principal foco a criação dedicionários com comprimento fixo. Com isso, o desempenhoproporcionado pela compressão e descompressão é rápida.

› Comparando-o com algoritmos semelhantes, anteriores ao mesmo(LZ77 e LZ78), é um dos algoritmos mais eficaz na redução dotamanho do fluxo de dados comprimidos, obtendo uma maiorrapidez de execução.

Referências Bibliográficas

[1] WIKIPÉDIA. Disponível em:< http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch > Acesso em 25 de maio de 2015.

[2] The Scientist and Engineer’s Guide to Digital Sign Processing. Data 27: Data Compression – LZW Compression. Disponível em: < http://www.dspguide.com/ch27/5.htm > Acesso em: 28 de maio de 2015.

[3] YOUTUBE. Lempel-Ziv-Welch Compression Algoritm – Tutorial. Disponível em: <https://www.youtube.com/watch?v=j2HSd3HCpDs> Acesso em 27 de maio de 2015.

[4] Terry Welch, "A Technique for High-Performance Data Compression", Computer, June 19

[5] Mark Nelson. Programming mostly. Disponível em: < http://marknelson.us/1989/10/01/lzw-data-compression/ > Acesso em: 27 de maio de 2015.

[6] MITOPENCOURSEWARE.Massachusetts Institute of Technology. Unit Two: Compression, Lecture One. Disponível em: >http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-050j-information-and-entropy-spring-2008/videos-homework-and-readings/unit-2-lecture-1/ > Acesso em 28 de maio de 2015.

[7] Implementações do LZW. Disponível em: <http://rosettacode.org/wiki/LZW_compression> Acesso em 27 de maio de 2015.