Compresión LZW: qué es y cómo funciona
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).
¿Qué es la compresión LZW?
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í.
¿Cómo se hace la compresión y descompresión?
- 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.