# 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. É 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

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

## Algoritmo

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. 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 descompactação String
## Exemplo

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

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