Lempel–Ziv–Welch ( LZW ) es un algoritmo universal de compresión de datos sin pérdidas creado por Abraham Lempel , Jacob Ziv y Terry Welch . Fue publicado por Welch en 1984 como una implementación mejorada del algoritmo LZ78 publicado por Lempel y Ziv en 1978. El algoritmo es simple de implementar y tiene el potencial de un rendimiento muy alto en implementaciones de hardware. [1] Es el algoritmo de la utilidad de compresión de archivos Unix ampliamente utilizada compress y se utiliza en el formato de imagen GIF .
El escenario descrito por el artículo de Welch de 1984 [1] codifica secuencias de datos de 8 bits como códigos de 12 bits de longitud fija. Los códigos del 0 al 255 representan secuencias de 1 carácter que constan del carácter de 8 bits correspondiente, y los códigos del 256 al 4095 se crean en un diccionario para las secuencias encontradas en los datos a medida que se codifican. En cada etapa de la compresión, los bytes de entrada se reúnen en una secuencia hasta que el siguiente carácter formaría una secuencia sin código aún en el diccionario. El código de la secuencia (sin ese carácter) se agrega a la salida y se agrega un nuevo código (para la secuencia con ese carácter) al diccionario.
La idea se adaptó rápidamente a otras situaciones. En una imagen basada en una tabla de colores, por ejemplo, el alfabeto de caracteres naturales es el conjunto de índices de tablas de colores y, en la década de 1980, muchas imágenes tenían tablas de colores pequeñas (del orden de 16 colores). Para un alfabeto tan reducido, los códigos completos de 12 bits producían una compresión deficiente a menos que la imagen fuera grande, por lo que se introdujo la idea de un código de ancho variable : los códigos suelen comenzar un poco más anchos que los símbolos que se codifican, y a medida que el tamaño de cada código se agota, el ancho del código aumenta en 1 bit, hasta un máximo prescrito (típicamente 12 bits). Cuando se alcanza el valor máximo del código, la codificación continúa utilizando la tabla existente, pero no se generan nuevos códigos para agregarlos a la tabla.
Otras mejoras incluyen reservar un código para indicar que la tabla de códigos debe borrarse y restaurarse a su estado inicial (un "código claro", normalmente el primer valor inmediatamente después de los valores de los caracteres alfabéticos individuales), y un código para indicar el final de datos (un "código de parada", típicamente uno mayor que el código claro). El código claro permite que la tabla se reinicie después de que se llene, lo que permite que la codificación se adapte a patrones cambiantes en los datos de entrada. Los codificadores inteligentes pueden monitorear la eficiencia de la compresión y borrar la tabla cuando la tabla existente ya no coincida bien con la entrada.
Dado que los códigos se agregan de una manera determinada por los datos, el decodificador imita la construcción de la tabla a medida que ve los códigos resultantes. Es fundamental que el codificador y el decodificador estén de acuerdo con la variedad de LZW utilizada: el tamaño del alfabeto, el tamaño máximo de la tabla (y el ancho del código), si se usa la codificación de ancho variable, el tamaño del código inicial y si se usa el claro. y códigos de parada (y qué valores tienen). La mayoría de los formatos que emplean LZW integran esta información en la especificación de formato o proporcionan campos explícitos para ellos en un encabezado de compresión para los datos.
Se inicializa un diccionario para que contenga las cadenas de un solo carácter correspondientes a todos los caracteres de entrada posibles (y nada más excepto los códigos de borrado y parada, si se están utilizando). El algoritmo funciona escaneando la cadena de entrada en busca de subcadenas sucesivamente más largas hasta que encuentra una que no está en el diccionario. Cuando se encuentra una cadena de este tipo, el índice de la cadena sin el último carácter (es decir, la subcadena más larga que está en el diccionario) se recupera del diccionario y se envía a la salida, y se agrega la nueva cadena (incluido el último carácter). al diccionario con el siguiente código disponible. El último carácter de entrada se usa como el siguiente punto de partida para buscar subcadenas.