Compresión LZW

Septiembre 2017

Compresión LZW

Abraham Lempel y Jakob Ziv son los creadores del compresor LZ77, inventado en 1977 (de ahí su nombre). Este compresor se utilizó en ese momento para archivar (los formatos ZIP, ARJ y LHA lo utilizan).

En 1978 crearon el compresor LZ78 especializado en compresión de imágenes (o la compresión de cualquier tipo de archivo binario).

En 1984, Terry Welch de Unisys lo modificó para utilizarlo en controladores de disco duro; por lo tanto, se agregó la inicial de su apellido a la abreviatura LZ, lo que originó el término LZW.
LZW es un algoritmo muy rápido tanto para la compresión como para la descompresión, basado en la multiplicidad de aparición de secuencias de caracteres en la cadena que se debe codificar. Su principio consiste en sustituir patrones con un código de índice y construir progresivamente un diccionario.

Además, funciona en bits y no en bytes, por lo tanto, no depende de la manera en que el procesador codifica información. Es uno de los algoritmos más populares y se utiliza particularmente en formatos TIFF y GIF. Dado que el método de compresión LZW ha sido patentado por Unisys, el que se utiliza en imágenes PNG es el algoritmo LZ77, por el que no se pagan derechos de autor.

Construcción del diccionario

El diccionario comienza con los 256 valores de la tabla ASCII. El archivo a comprimir se divide en cadenas de bytes (por lo tanto, para las imágenes monocromáticas codificadas en 1 bit, esta compresión no es muy eficaz), cada una de estas cadenas se compara con el diccionario y se agrega si no se encuentra ahí.

Compresión

El algoritmo pasa por la cadena de información y la codifica. Si una cadena nunca es más corta que la palabra más larga del diccionario, ésta se transmite.

Descompresión

Durante la descompresión, el algoritmo reconstruye el diccionario en la dirección opuesta; por lo tanto, no necesita almacenarse.

Consulta también


LZW Compression
LZW Compression
LZW-Komprimierung
LZW-Komprimierung
Compression MZW
Compression MZW
Compressione MZW
Compressione MZW
Compressão LZW
Compressão LZW
Última actualización: 16 de octubre de 2008 a las 15:43 por Jeff.
El documento «Compresión LZW» se encuentra disponible bajo una licencia Creative Commons. Puedes copiarlo o modificarlo libremente. No olvides citar a CCM (es.ccm.net) como tu fuente de información.