Compressão LZW

Fevereiro 2017

A compressão LZW

Abraham Lempel e Jakob Ziv são os inventores do compressor LZ77, inventado em 1977 (daí o seu nome). Este compressor era então utilizado para o arquivo (os formatos ZIP, ARJ e LHA utilizam-no).

Em 1978, criam o compressor LZ78 especializado na compressão de imagens (ou qualquer tipo de ficheiro de tipo binário).

Em 1984, Terry Welch da empresa Unisys alterou-o para o utilizar em controladores de discos rígidos, a inicial do seu apelido veio por conseguinte acrescentar-se à abreviatura LZ, para dar LZW.
LZW é igualmente um algoritmo muito rápido quer em compressão, quer em descompressão, baseado na multiplicidade das ocorrências de sequências de caracteres na cadeia a codificar. O seu princípio consiste em substituir motivos por um código de afectação (índice), construindo progressivamente um dicionário.

Além disso, trabalha em bits e não em octets, não depende por isso da maneira como o processador codifica as informações. É um dos algoritmos mais populares, é utilizado nomeadamente nos formatos TIFF e GIF. O método de compressão LZW patenteado pela empresa Unisys, é o algoritmo LZ77, livre de direitos, que é utilizado nas imagens PNG.

Construção do dicionário

O dicionário inicia com os 256 valores da tabela ASCII. O ficheiro a comprimir é recortado em cadeias de bytes (assim, para imagens monocromáticas - codificadas em 1 bit - esta compressão é pouco eficaz), cada um destas cadeias é comparada com o dicionário e acrescentada se por acaso não estiver presente.

A compressão

O algoritmo percorre a onda de informações codificando-a; se por acaso uma cadeia é mais pequena que a maior palavra do dicionário, então é transmitida.

A descompressão

Aquando da descompressão, o algoritmo reconstrói o dicionário no sentido oposto, este último não tem por conseguinte necessidade de ser armazenado.

Veja também


LZW Compression
LZW Compression
Compresión LZW
Compresión LZW
LZW-Komprimierung
LZW-Komprimierung
Compression MZW
Compression MZW
Compressione MZW
Compressione MZW
Este documento, intitulado 'Compressão LZW', está disponível sob a licença Creative Commons. Você pode copiar e/ou modificar o conteúdo desta página com base nas condições estipuladas pela licença. Não se esqueça de creditar o CCM (br.ccm.net) ao utilizar este artigo.