Criada em 1977 por Abraham Lempel e Jacob Ziv, a compressão LZW é encontrada na compressão de texto e de programas, como o LHA, o ARJ e o PKZIP. Os algoritmos de compressão LZ78 são usados na compressão de dados binários, como os bitmaps. Em 1984, Terry Welch modificou o compressor LZ78 para a sua implementação em controladores de discos de elevado desempenho. O resultado foi o algoritmo LZW que é encontrado e usado nos nossos dias. O LZW é um algoritmo de compressão capaz de trabalhar sobre qualquer tipo de dados. É, geralmente, rápido na compressão e descompressão dos dados sem precisar de usar operações de virgula flutuante (não precisa de coprocessador). Para além disso, como o LZW escreve os dados comprimidos como bytes e não words (2 bytes), o resultado da compressão é idêntico em sistemas big-endian e little-endian. O LZW é referido como um algoritmo substitucional, porque constrói um dicionário dos dados (normalmente chamado de tabela de tradução) originais. Os padrões dos dados são identificados e registados no dicionário. Se o padrão não está presente no dicionário, é codificado e registado no mesmo, ao mesmo tempo que é escrito no ficheiro destino. No caso oposto só é escrito no ficheiro destino e como a saida codificada é menor do que o padrão encontrado, a compressão dos dados é conseguida. A descodificação LZW é o inverso da codificação. O descompressor lê os dados comprimidos e adiciona os códigos existentes ao dicionário de dados. Posteriormente, cada código é traduzido nos dados que representa e escrito para o ficheiro destino. O LZW é um dos algoritmos de compressão mais utilizados nos nossos dias. Este método de compressão de dados sem perdas é encontrado em vários formatos de imagem, como o GIF, TIFF e PDF.
©
Departamento de Engenharia Informática |
    
|
