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 editar

TIFF, por opção;
GIF, por padrão.

Algoritmo 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 editar

1. 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 editar

1. 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 editar

No 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 editar

Por 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 (D_seq, 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

Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.

[1] SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer

[2] Elimina-se o caractere c do par (D_seq, c) descrito em LZ78#Algoritmo.

[1]

[2]