LZW
LZW (Lempel-Ziv-Welch) é um algoritmo de compressão de dados, derivado do algoritmo LZ78, baseado na localização e no registro das padronagens de uma estrutura. Foi desenvolvido e patenteado em 1984 por Terry Welch.[1] É geralmente utilizado em imagens em que não se pode perder a definição original. Nas imagens, o algoritmo lê os valores de pixels de uma imagem bitmap e elabora uma tabela de códigos onde se representam as padronagens repetidas dos pixels encontrados.
O codificador LZW reduz, pela compressão, os arquivos de imagens gráficas a 1/3 ou 1/4 de seu tamanho original.
Imagens com padronagem bem definidas — com grandes blocos de cor contínua ou repetidas de cores — podem reduzir para 1/10 o tamanho original do arquivo.
Formatos que utilizam o LZW
editarAlgoritmo
editar
O algoritmo LZW é uma variante do LZ78, que visa eliminar a necessidade de se emitir um caractere literal junto com o endereço de dicionário[2]. Para isso, o dicionário é inicializado com todos os símbolos do alfabeto (ao se usar codificação ASCII são 256 símbolos, de 0 a 255). A entrada é lida e acumulada em uma cadeia de caracteres que chamaremos de I. Sempre que a seqüência contida em I não estiver presente no dicionário emitimos o código correspondente a versão anterior de I (ou seja, I sem o último caractere) e adicionamos I ao dicionário. I volta a ser inicializado com o último caractere lido (o seu último caractere) e o processo continua até que não haja mais caracteres na entrada.
Pseudocódigo
editar1. No início o dicionário contém todas as raízes possíveis e I é vazio; 2. c <= próximo caractere da sequência de entrada; 3. A string I+c existe no dicionário? a. se sim, i. I <= I+c; b. se não, i. coloque a palavra código correspondente a I na sequência codificada; ii. adicione a string I+c ao dicionário; iii. I <= c; 4. Existem mais caracteres na sequência de entrada ? a. se sim, i. volte ao passo 2; b. se não, ii. coloque a palavra código correspondente a I na sequência codificada; iii. FIM.
Pseudocódigo descompactação String
editar1. No início o dicionário contém todas as raízes possíveis; 2. cW <= primeira palavra código na sequência codificada (sempre é uma raiz); 3. Coloque a string(cW) na sequência de saída; 4. pW <= cW; 5. cW <= próxima palavra código da sequência codificada; 6. A string(cW) existe no dicionário ? a. se sim, i. coloque a string(cW) na sequência de saída; ii. P <= string(pW); iii. C <= primeiro caracter da string(cW); iv. adicione a string P+C ao dicionário; b. se não, i. P <= string(pW); ii. C <= primeiro caracter da string(pW); iii. coloque a string P+C na sequência de saída e adicione-a ao dicionário; 7. Existem mais palavras código na sequência codificada ? a. se sim, i. volte ao passo 4; b. se não, i. FIM.
Exemplo
editarNo quadro abaixo mostramos os passes da compressão da cadeia A_ASA_DA_CASA usando o método de LZW. A coluna I representa a cadeia lida na entrada desde que a última saída foi emitida. A coluna no dic? indica se a seqüência em I está presente no dicionário. a coluna nova entrada mostra o que será inserido no dicionário (como o dicionário já contém os 256 símbolos do código ASCII é impraticável mostrar todo seu conteúdo, por isso listamos apenas as novas entradas). E por fim a coluna saída mostra o código que será emitido na saída do programa, junto com o que ele representa no dicionário (entre parênteses).
| I | no dic? | nova entrada | saída |
| A | S | ||
| A_ | N | 256:A_ | 65 (A) |
| _ | S | ||
| _A | N | 257:_A | 95 (_) |
| A | S | ||
| AS | N | 258:AS | 65 (A) |
| S | S | ||
| SA | N | 259:SA | 83 (S) |
| A | S | ||
| A_ | S | ||
| A_D | N | 260:A_D | 256 (A_) |
| D | S | ||
| DA | N | 261:DA | 68 (D) |
| A | S | ||
| A_ | S | ||
| A_C | N | 262:A_C | 256 (A_) |
| C | S | ||
| CA | N | 263:CA | 67 (C) |
| A | S | ||
| AS | S | ||
| ASA | N | 264:ASA | 258 (AS) |
| A | S | ||
| - | - | - | 65 (A) |
O tamanho final é de 10 códigos,sendo 7 representados por 8 bits cada um e 3 código representados por 9 bits. Nesse caso temos na saída 83 bits, comparados com os 104 originais. Como podemos ver, o método LZW é ainda mais lento para fazer efeito que o método LZ78 devido ao fato de o dicionário já estar inicialmente povoado com todos os símbolos do alfabeto. Entretanto ele é mais simples de ser implementado e gera resultados semelhantes ou até melhores com cadeias de caracteres mais longas.
Problemas
editarPor ser uma variante do LZ78 o LZW sofre dos mesmos problemas enfrentados por este, que podem ser vistos em LZ78#Problemas.
Exemplo de implementação
#!/usr/bin/python
# coding: utf-8
import sys
class lzw_encoder:
"""
Classe usada para codificar um arquivo usando
o algoritmo LZW. Está é uma implementação de
exemplo que não leva em conta a representação
binária do arquivo de saída nem o estouro do
tamanho do dicionário. Este código foi baseado nas
informações contidas em
"""
def __init__(self):
"""
Faz a carga inicial do dicionário com os 256
caracteres ASCII possíveis.
"""
self.next_code = 0
self.dictionary = dict()
for i in range(0,256):
self.add_to_dictionary(chr(i))
def add_to_dictionary(self, str):
"""
Cria um novo código para uma dada "string" e a
insere sob esse código no dicionário
"""
self.dictionary[str] = self.next_code
self.next_code = self.next_code + 1
def encode(self, str):
"""
Corpo do algoritmo. lê sequencialmente os
caracteres e cria as cadeias a serem inseridas
no dicionário, emitindo os respectivos códigos
no arquivo de saída (representado pela lista "ret"
"""
ret = [] # inicializa a lista (arquivo de saída)
buffer = '' # inicializa o acumulador de caracteres lidos
for i in range(0, len(str)):
c = str[i]
# enquanto a cadeia atual existir no dicionário,
# continuamos acresncentando caracteres a ela
# No caso da versao 3, troque a linha de baixo por:
# if len(buffer) == 0 or (buffer + c) in self.dictionary:
if len(buffer) == 0 or self.dictionary.has_key(buffer + c):
buffer = buffer + c
else:
# quando encontramos a maior cadeia presente
# emitimos o código dessa cadeia e criamos uma
# nova cadeia, acrescentando o último
# caractere lido.
code = self.dictionary[buffer]
self.add_to_dictionary(buffer + c)
buffer = c
ret = ret + [code]
if buffer:
ret = ret + [self.dictionary[buffer]]
return ret
class lzw_decoder:
"""
Classe usada para decodificar um arquivo
codificado com LZW. Segue as mesmas restrições
da classe lzw_encoder
"""
def __init__(self):
"""
Faz a carga inicial do dicionário com os 256
caracteres ASCII possíveis.
"""
self.next_code = 0
self.dictionary = dict()
for i in range(0,256):
self.add_to_dictionary(chr(i))
def add_to_dictionary(self, str):
"""
Cria um novo código para uma dada "string" e a
insere sob esse código no dicionário
"""
self.dictionary[self.next_code] = str
self.next_code = self.next_code + 1
def decode(self, symbols):
"""
Decodifica o arquivo. Emite sequêncialmente
as cadeias correspondentes aos códigos lidos.
Caso a concatenação dos códigos lidos não
corresponda a uma cadeia existente, acrescenta no
dicionário como uma nova cadeia.
"""
last_symbol = symbols[0]
ret = self.dictionary[last_symbol]
for symbol in symbols[1:]:
# No caso da versao 3, troque a linha de baixo por:
# if symbol in self.dictionary:
if self.dictionary.has_key(symbol):
current = self.dictionary[symbol]
previous = self.dictionary[last_symbol]
to_add = current[0]
self.add_to_dictionary(previous + to_add)
ret = ret + current
else:
previous = self.dictionary[last_symbol]
to_add = previous[0]
self.add_to_dictionary(previous + to_add)
ret = ret + previous + to_add
last_symbol = symbol
return ret
if __name__ == "__main__":
str = ''
str = 'A_ASA_DA_CASA'
encoder = lzw_encoder()
encoded = encoder.encode(str)
print ('encoded:', encoded)
decoder = lzw_decoder()
decoded = decoder.decode(encoded)
print ('decoded:', decoded)
Notas e referências
editar- ↑ SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer
- ↑ Elimina-se o caractere c do par (Dseq, c) descrito em LZ78#Algoritmo.
Bibliografia
editar- SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer
- WELCH, T. A. (June 1984). "A technique for high-performance data compression." Computer. Vol. 17, pp. 8–19.
Ligaçoes externas
editar- animação do algoritmo LZW passo a passo do site de um professor da Universidade Federal de Campina Grande.
- Compactador de arquivos online, que usa LZW ou Huffman, com os códigos. AED 3
