Lempel–Ziv–Welch ( LZW ) es un algoritmo de compresión de datos sin pérdida universal 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 de Unix compress y se utiliza en el formato de imagen GIF .
El escenario descrito en 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 de 0 a 255 representan secuencias de 1 carácter que consisten en el carácter de 8 bits correspondiente, y los códigos de 256 a 4095 se crean en un diccionario para las secuencias que se encuentran 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 para la secuencia (sin ese carácter) se agrega a la salida, y un nuevo código (para la secuencia con ese carácter) se agrega 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 natural es el conjunto de índices de la tabla 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 empezar con un bit más de ancho que los símbolos que se están codificando y, a medida que se utiliza cada tamaño de código, el ancho del código aumenta en 1 bit, hasta un máximo prescrito (normalmente 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 añadirlos a la tabla.
Otras mejoras incluyen la reserva de un código para indicar que la tabla de códigos debe ser borrada y restaurada a su estado inicial (un "código de borrado", típicamente el primer valor inmediatamente después de los valores de los caracteres alfabéticos individuales), y un código para indicar el final de los datos (un "código de detención", típicamente uno mayor que el código de borrado). El código de borrado permite que la tabla se reinicialice después de que se llena, lo que permite que la codificación se adapte a los 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 sobre 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 utiliza codificación de ancho variable, el tamaño inicial del código y si se deben utilizar los códigos de borrado y detención (y qué valores tienen). La mayoría de los formatos que emplean LZW incorporan esta información en la especificación del formato o proporcionan campos explícitos para ellos en un encabezado de compresión para los datos.
Aquí se muestra una vista de alto nivel del algoritmo de codificación:
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 de parada, si se están utilizando). El algoritmo funciona escaneando la cadena de entrada en busca de subcadenas cada vez más largas hasta que encuentra una que no está en el diccionario. Cuando se encuentra una cadena de este tipo, se recupera del diccionario el índice de la cadena sin el último carácter (es decir, la subcadena más larga que está en el diccionario) y se envía a la salida, y la nueva cadena (incluido el último carácter) se agrega al diccionario con el siguiente código disponible. El último carácter de entrada se utiliza entonces como el siguiente punto de inicio para escanear en busca de subcadenas.
De esta manera, se registran en el diccionario cadenas cada vez más largas y están disponibles para su posterior codificación como valores de salida únicos. El algoritmo funciona mejor con datos con patrones repetidos, por lo que las partes iniciales de un mensaje sufren poca compresión. Sin embargo, a medida que el mensaje crece, la relación de compresión tiende asintóticamente al máximo (es decir, el factor o relación de compresión mejora en una curva creciente y no linealmente, acercándose a un máximo teórico dentro de un período de tiempo limitado en lugar de en un tiempo infinito). [2]
Aquí se muestra una vista de alto nivel del algoritmo de decodificación:
El algoritmo de decodificación funciona leyendo un valor de la entrada codificada y generando la cadena correspondiente del diccionario. Sin embargo, no se necesita el diccionario completo, solo el diccionario inicial que contiene cadenas de un solo carácter (y que generalmente está codificado en el programa, en lugar de enviarse con los datos codificados). En cambio, el diccionario completo se reconstruye durante el proceso de decodificación de la siguiente manera: después de decodificar un valor y generar una cadena, el decodificador lo concatena con el primer carácter de la siguiente cadena decodificada (o el primer carácter de la cadena actual, si la siguiente no se puede decodificar; ya que si el siguiente valor es desconocido, entonces debe ser el valor agregado al diccionario en esta iteración, y por lo tanto su primer carácter es el mismo que el primer carácter de la cadena actual), y actualiza el diccionario con la nueva cadena. Luego, el decodificador procede a la siguiente entrada (que ya se leyó en la iteración anterior) y la procesa como antes, y así sucesivamente hasta que ha agotado el flujo de entrada.
Si se utilizan códigos de ancho variable, el codificador y el decodificador deben tener cuidado de cambiar el ancho en los mismos puntos de los datos codificados para que no estén en desacuerdo sobre los límites entre los códigos individuales en el flujo. En la versión estándar, el codificador aumenta el ancho de p a p + 1 cuando se encuentra una secuencia ω + s que no está en la tabla (de modo que se debe agregar un código para ella) pero el siguiente código disponible en la tabla es 2 p (el primer código que requiere p + 1 bits). El codificador emite el código para ω con un ancho p (ya que ese código no requiere p + 1 bits) y luego aumenta el ancho del código para que el siguiente código emitido tenga un ancho de p + 1 bits.
El decodificador siempre está un código detrás del codificador al construir la tabla, por lo que cuando ve el código para ω, genera una entrada para el código 2 p − 1. Dado que este es el punto donde el codificador aumenta el ancho del código, el decodificador debe aumentar el ancho aquí también, en el punto donde genera el código más grande que cabe en p bits.
Desafortunadamente, algunas implementaciones tempranas del algoritmo de codificación aumentan el ancho del código y luego emiten ω en el nuevo ancho en lugar del ancho anterior, de modo que para el decodificador parece que el ancho cambia un código demasiado pronto. Esto se llama "cambio temprano"; causó tanta confusión que Adobe ahora permite ambas versiones en archivos PDF, pero incluye una bandera explícita en el encabezado de cada flujo comprimido con LZW para indicar si se está utilizando el cambio temprano. De los formatos de archivos gráficos que admiten la compresión LZW, TIFF utiliza el cambio temprano, mientras que GIF y la mayoría de los demás no lo hacen.
Cuando la tabla se borra en respuesta a un código de borrado, tanto el codificador como el decodificador cambian el ancho del código después del código de borrado al ancho del código inicial, comenzando con el código inmediatamente posterior al código de borrado.
Dado que los códigos emitidos normalmente no caen en los límites de bytes, el codificador y el decodificador deben estar de acuerdo sobre cómo se empaquetan los códigos en bytes. Los dos métodos comunes son LSB-first (" bit menos significativo primero") y MSB-first (" bit más significativo primero"). En el empaquetamiento LSB-first, el primer código se alinea de modo que el bit menos significativo del código caiga en el bit menos significativo del primer byte de flujo, y si el código tiene más de 8 bits, los bits de orden superior que quedan se alinean con los bits menos significativos del siguiente byte; los códigos posteriores se empaquetan con LSB yendo al bit menos significativo aún no utilizado en el byte de flujo actual, y se procede a los bytes posteriores según sea necesario. El empaquetamiento MSB-first alinea el primer código de modo que su bit más significativo caiga en el MSB del primer byte de flujo, con el desbordamiento alineado con el MSB del siguiente byte; los códigos posteriores se escriben con MSB yendo al bit más significativo aún no utilizado en el byte de flujo actual.
Los archivos GIF utilizan el orden de empaquetado LSB primero. Los archivos TIFF y PDF utilizan el orden de empaquetado MSB primero.
El siguiente ejemplo ilustra el algoritmo LZW en acción, mostrando el estado de la salida y del diccionario en cada etapa, tanto en la codificación como en la decodificación de los datos. Este ejemplo se ha construido para proporcionar una compresión razonable en un mensaje muy corto. En los datos de texto reales, la repetición es generalmente menos pronunciada, por lo que normalmente se necesitan secuencias de entrada más largas antes de que la compresión aumente su eficiencia.
El texto simple a codificar (de un alfabeto que utiliza solo letras mayúsculas) es:
NO SERÉORNOTTOBEORTOBEORNOT#
Hay 26 símbolos en el alfabeto de texto simple (las letras mayúsculas de la A a la Z ). # se utiliza para representar un código de parada: un código fuera del alfabeto de texto simple que activa un manejo especial. Asignamos arbitrariamente los valores del 1 al 26 para las letras y 0 para el código de parada '#'. (La mayoría de las versiones de LZW colocarían el código de parada después del alfabeto de datos, pero nada en el algoritmo básico lo requiere. El codificador y el decodificador solo tienen que acordar qué valor tiene).
Un ordenador los convierte en cadenas de bits . Se necesitan códigos de cinco bits para dar combinaciones suficientes para abarcar este conjunto de 27 valores. El diccionario se inicializa con estos 27 valores. A medida que el diccionario crece, los códigos deben aumentar de ancho para dar cabida a las entradas adicionales. Un código de 5 bits da 2 5 = 32 posibles combinaciones de bits, por lo que cuando se crea la palabra número 33 del diccionario, el algoritmo debe cambiar en ese punto de cadenas de 5 bits a cadenas de 6 bits (para todos los valores de código, incluidos los que anteriormente se emitían con solo cinco bits). Tenga en cuenta que, dado que se utiliza el código de todos ceros 00000 y se etiqueta como "0", la entrada número 33 del diccionario se etiqueta como 32. (La salida generada anteriormente no se ve afectada por el cambio de ancho del código, pero una vez que se genera un valor de 6 bits en el diccionario, es posible que sea el siguiente código emitido, por lo que el ancho para la salida posterior cambia a 6 bits para adaptarse a eso).
El diccionario inicial consta pues de las siguientes entradas:
Almacenar en búfer los caracteres de entrada en una secuencia ω hasta que ω + el siguiente carácter no esté en el diccionario. Emitir el código para ω y agregar ω + el siguiente carácter al diccionario. Comenzar a almacenar en búfer nuevamente con el siguiente carácter. (La cadena que se codificará es "TOBEORNOTTOBEORTOBEORNOT#").
El uso de LZW ha permitido ahorrar 29 bits de 125, lo que ha reducido el mensaje en más de un 23 %. Si el mensaje fuera más largo, las palabras del diccionario empezarían a representar secciones de texto cada vez más largas, enviando las palabras repetidas de forma muy compacta.
Para decodificar un archivo comprimido LZW, es necesario saber de antemano el diccionario inicial utilizado, pero se pueden reconstruir entradas adicionales ya que siempre son simplemente concatenaciones de entradas anteriores.
En cada etapa, el decodificador recibe un código X; busca X en la tabla y genera la secuencia χ que codifica, y conjetura que χ + ? es la entrada que el codificador acaba de agregar, porque el codificador emitió X para χ precisamente porque χ + ? no estaba en la tabla, y el codificador continúa y la agrega. Pero, ¿cuál es la letra que falta? Es la primera letra en la secuencia codificada por el siguiente código Z que recibe el decodificador. Entonces, el decodificador busca Z, la decodifica en la secuencia ω y toma la primera letra z y la agrega al final de χ como la siguiente entrada del diccionario.
Esto funciona siempre que los códigos recibidos estén en el diccionario del decodificador, de modo que puedan decodificarse en secuencias. ¿Qué sucede si el decodificador recibe un código Z que aún no está en su diccionario? Como el decodificador siempre está un código detrás del codificador, Z puede estar en el diccionario del codificador solo si el codificador lo acaba de generar, al emitir el código X anterior para χ. Por lo tanto, Z codifica algún ω que es χ + ?, y el decodificador puede determinar el carácter desconocido de la siguiente manera:
Esta situación ocurre siempre que el codificador encuentra una entrada con el formato cScSc , donde c es un solo carácter, S es una cadena y cS ya está en el diccionario, pero cSc no. El codificador emite el código para cS , colocando un nuevo código para cSc en el diccionario. A continuación, ve cSc en la entrada (comenzando en la segunda c de cScSc ) y emite el nuevo código que acaba de insertar. El argumento anterior muestra que siempre que el decodificador recibe un código que no está en su diccionario, la situación debe verse así.
Aunque la entrada de la forma cScSc puede parecer poco probable, este patrón es bastante común cuando el flujo de entrada se caracteriza por una repetición significativa. En particular, las cadenas largas de un solo carácter (que son comunes en los tipos de imágenes que LZW suele codificar) generan repetidamente patrones de este tipo.
El esquema simple descrito anteriormente se centra en el algoritmo LZW en sí. Muchas aplicaciones aplican una codificación adicional a la secuencia de símbolos de salida. Algunas empaquetan el flujo codificado como caracteres imprimibles utilizando alguna forma de codificación de binario a texto ; esto aumenta la longitud codificada y disminuye la tasa de compresión. Por el contrario, a menudo se puede lograr una mayor compresión con un codificador de entropía adaptativa . Un codificador de este tipo estima la distribución de probabilidad para el valor del siguiente símbolo, en función de las frecuencias observadas de los valores hasta el momento. Una codificación de entropía estándar, como la codificación de Huffman o la codificación aritmética , utiliza códigos más cortos para valores con probabilidades más altas.
La compresión LZW se convirtió en el primer método de compresión de datos universal ampliamente utilizado en computadoras. Un archivo de texto grande en inglés puede comprimirse mediante LZW hasta aproximadamente la mitad de su tamaño original.
LZW se utilizó en el programa de dominio público compress , que se convirtió en una utilidad más o menos estándar en los sistemas Unix alrededor de 1986. Desde entonces ha desaparecido de muchas distribuciones, tanto porque infringía la patente de LZW como porque gzip producía mejores índices de compresión utilizando el algoritmo DEFLATE basado en LZ77 , pero a partir de 2008 al menos FreeBSD incluye tanto compress como uncompress como parte de la distribución. Varias otras utilidades de compresión populares también usaban LZW o métodos estrechamente relacionados.
El formato LZW se volvió muy utilizado cuando se convirtió en parte del formato de imagen GIF en 1987. También se puede utilizar (opcionalmente) en archivos TIFF y PDF . (Aunque LZW está disponible en el software Adobe Acrobat , Acrobat utiliza DEFLATE de manera predeterminada para la mayoría de los datos de texto e imágenes basados en tablas de colores en archivos PDF).
Se han emitido varias patentes en los Estados Unidos y otros países para LZW y algoritmos similares. LZ78 estaba cubierto por la patente estadounidense 4.464.650 de Lempel, Ziv, Cohn y Eastman, asignada a Sperry Corporation , posteriormente Unisys Corporation, presentada el 10 de agosto de 1981. Se emitieron dos patentes estadounidenses para el algoritmo LZW: la patente estadounidense 4.814.746 de Victor S. Miller y Mark N. Wegman y asignada a IBM , presentada originalmente el 1 de junio de 1983, y la patente estadounidense 4.558.302 de Welch, asignada a Sperry Corporation, posteriormente Unisys Corporation, presentada el 20 de junio de 1983.
Además de las patentes mencionadas anteriormente, la patente de Welch de 1983 también incluye citas de varias otras patentes que la influyeron, incluidas dos patentes japonesas de 1980 (JP9343880A y JP17790880A) de Jun Kanatsu de NEC , la patente estadounidense 4.021.782 (1974) de John S. Hoerning, la patente estadounidense 4.366.551 (1977) de Klaus E. Holtz y una patente alemana de 1981 (DE19813118676) de Karl Eckhart Heinz. [3]
En 1993-94, y nuevamente en 1999, Unisys Corporation recibió una condena generalizada cuando intentó imponer tarifas de licencia para LZW en imágenes GIF. La controversia Unisys-CompuServe de 1993-1994 ( CompuServe es el creador del formato GIF) provocó una discusión en Usenet sobre comp.graphics titulada Thoughts on a GIF-replacement file format (Reflexiones sobre un formato de archivo de reemplazo de GIF ) , que a su vez fomentó un intercambio de correos electrónicos que finalmente culminó en la creación del formato de archivo Portable Network Graphics (PNG) sin patentes en 1995.
La patente estadounidense de Unisys sobre el algoritmo LZW expiró el 20 de junio de 2003, [4] veinte años después de su presentación. Las patentes presentadas en el Reino Unido, Francia, Alemania, Italia, Japón y Canadá expiraron en 2004, [4] también veinte años después de su presentación.