Lempel–Ziv–Welch

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. Es el algoritmo de la utilidad de compresión de archivos Unix compress y se utiliza en el formato de imagen GIF.

Algoritmo

El escenario descrito por el artículo de Welch de 1984 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 todavía 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 están usando. codificado, y a medida que se agota cada tamaño de código, 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", generalmente 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", generalmente uno más 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.

Codificación

Aquí se muestra una vista de alto nivel del algoritmo de codificación:

1. Iniciar el diccionario para contener todas las cadenas de longitud uno.
2. Encuentra la cuerda más larga W en el diccionario que coincide con la entrada actual.
3. Emitir el índice del diccionario W a la salida y la eliminación W de la entrada.
4. Añadir W seguido por el siguiente símbolo en la entrada al diccionario.
5. Vaya al paso 2.

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 la nueva cadena (incluido el último carácter) se añade 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.

De esta manera, las cadenas sucesivamente más largas se registran en el diccionario y están disponibles para la codificación posterior como valores de salida únicos. El algoritmo funciona mejor con datos con patrones repetidos, por lo que las partes iniciales de un mensaje ven poca compresión. Sin embargo, a medida que crece el mensaje, 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 un tiempo infinito).

Decodificación

Aquí se muestra una vista de alto nivel del algoritmo de decodificación:

1. Iniciar el diccionario para contener todas las cadenas de longitud uno.
2. Lea el siguiente símbolo codificado: ¿Está codificado en el diccionario?
   1. Sí:
      1. Emitir la cadena correspondiente W a la salida.
      2. Concatenar la cadena anterior emitida a la salida con el primer símbolo de W. Añadir esto al diccionario.
   2. No:
      1. Concatenar la cadena anterior emitida a la salida con su primer símbolo. Llama a esta cuerda. V.
      2. Añadir V al diccionario y emitir V a la salida.
3. Repita el paso 2 hasta el final de la cadena de entrada

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 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, por lo que su primer carácter es igual que el primer carácter de la cadena actual) y actualiza el diccionario con la nueva cadena. Luego, el decodificador pasa a la siguiente entrada (que ya se leyó en la iteración anterior) y la procesa como antes, y así sucesivamente hasta que agota el flujo de entrada.

Códigos de ancho variable

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 discrepen en los límites entre los códigos individuales de la transmisión. 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 el (por lo que se debe agregar un código) 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 sea p + 1 bits de ancho.

El decodificador siempre está un código detrás del codificador en la construcción de 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 también debe aumentar el ancho aquí, 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 antiguo, de modo que para el decodificador parece que el ancho cambia un código demasiado temprano. Esto se llama "cambio temprano"; causó tanta confusión que Adobe ahora permite ambas versiones en archivos PDF, pero incluye un indicador explícito en el encabezado de cada secuencia comprimida con LZW para indicar si se está utilizando un cambio anticipado. De los formatos de archivo de gráficos que admiten la compresión LZW, TIFF usa el cambio temprano, mientras que GIF y la mayoría de los demás no lo hacen.

Cuando se borra la tabla 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 de nuevo al ancho del código inicial, comenzando con el código que sigue inmediatamente al código de borrado.

Orden de embalaje

Dado que los códigos emitidos normalmente no caen en los límites de bytes, el codificador y el decodificador deben acordar cómo se empaquetan los códigos en bytes. Los dos métodos comunes son LSB primero ("bit menos significativo primero") y MSB-primero ("bit más significativo primero"). En el primer empaque LSB, el primer código se alinea de modo que el bit menos significativo del código cae 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 sobran son alineado con los bits menos significativos del siguiente byte; los códigos adicionales se empaquetan con LSB que ingresa al bit menos significativo que aún no se usa en el byte de flujo actual, y continúa con los bytes adicionales según sea necesario. El primer empaquetado de MSB alinea el primer código para 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; se escriben más códigos con MSB entrando en el bit más significativo aún no utilizado en el byte de flujo actual.

Los archivos GIF utilizan el primer orden de embalaje LSB. Los archivos TIFF y los archivos PDF utilizan el primer orden de embalaje de MSB.

Ejemplo

El siguiente ejemplo ilustra el algoritmo LZW en acción, mostrando el estado de la salida y el diccionario en cada etapa, tanto en la codificación como en la decodificación de los datos. Este ejemplo ha sido construido para dar una compresión razonable en un mensaje muy corto. En los datos de texto real, la repetición suele ser menos pronunciada, por lo que normalmente se necesitan secuencias de entrada más largas antes de que la compresión aumente la eficiencia.

El texto sin formato que se codificará (de un alfabeto que use solo letras mayúsculas) es:

TOBEORNOTOBEORTOBEORNOT

El # es un marcador que se utiliza para mostrar que se ha llegado al final del mensaje. Por lo tanto, hay 26 símbolos en el alfabeto de texto sin formato (las 26 letras mayúsculas A a Z), y el carácter # representa un código de parada. Asignamos arbitrariamente los valores del 1 al 26 para las letras y 0 para '#'. (La mayoría de las versiones de LZW pondrían el código de parada después del alfabeto de datos, pero nada en el algoritmo básico requiere eso. El codificador y el decodificador solo tienen que acordar qué valor tiene).

Una computadora los representa como cadenas de bits. Se necesitan códigos de cinco bits para dar suficientes combinaciones para abarcar este conjunto de 27 valores. El diccionario se inicializa con estos 27 valores. A medida que crece el diccionario, los códigos deben crecer en anchura para dar cabida a las entradas adicionales. Un código de 5 bits da 2⁵ = 32 combinaciones posibles 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 (por todos los valores de código, incluidos los que se emitían anteriormente con solo cinco bits). Tenga en cuenta que dado que se utiliza el código de todos ceros 00000 y está etiquetado como "0", la entrada 33 del diccionario está etiquetada como 32. (La salida generada anteriormente no se ve afectada por el cambio de ancho de 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 de la salida posterior cambia a 6 bits para adaptarse a eso.)

El diccionario inicial, entonces, consta de las siguientes entradas:

Codificación

Caracteres de entrada de búfer en una secuencia ω hasta que ω + el siguiente carácter no esté en el diccionario. Emita el código para ω y agregue ω + el siguiente carácter al diccionario. Comience a almacenar en búfer nuevamente con el siguiente carácter. (La cadena que se codificará es "TOBEORNOTTOBEORTOBEORNOT#").

Longitud no codificada = 25 símbolos × 5 bits/symbol = 125 bits

Longitud codificada = (6 códigos × 5 bits/código) + (11 códigos × 6 bits/código) = 96 bits.

Usar LZW ha ahorrado 29 bits de 125, reduciendo el mensaje en más de un 23 %. Si el mensaje fuera más largo, las palabras del diccionario comenzarían a representar secciones de texto cada vez más largas, enviando palabras repetidas de manera muy compacta.

Decodificación

Para decodificar un archivo comprimido con LZW, es necesario conocer 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 χ +? como la entrada que acaba de agregar el codificador, porque el codificador emitió X para χ precisamente porque χ + ? no estaba en la tabla, y el codificador continúa y lo agrega. Pero, ¿cuál es la letra que falta? Es la primera letra de la secuencia codificada por el siguiente código Z que recibe el decodificador. Entonces, el decodificador busca Z, lo 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, para que puedan decodificarse en secuencias. ¿Qué sucede si el decodificador recibe un código Z que aún no está en su diccionario? Dado que el decodificador siempre está solo un código detrás del codificador, Z puede estar en el diccionario del codificador solo si el codificador solo lo generó, al emitir el código anterior X para χ. Por lo tanto, Z codifica algún ω que es χ + ?, y el decodificador puede determinar el carácter desconocido de la siguiente manera:

1. El decodificador ve X y luego Z, donde X codifica la secuencia χ y Z códigos una secuencia desconocida ω.
2. El decodificador sabe que el encoder acaba de agregar Z como un código para χ + algún personaje desconocido c, así que ω = χ + c.
3. Desde c es el primer personaje en el flujo de entrada después de la χ, y ya que ω es la cadena que aparece inmediatamente después de la χ, c debe ser el primer carácter de la secuencia ω.
4. Puesto que la χ es una subestring inicial de ω, c debe ser también el primer personaje de la χ.
5. Así, aunque el código Z no está en la tabla, el decodificador es capaz de inferir la secuencia desconocida y añade χ + (el primer carácter de χ) a la tabla como el valor de Z.

Esta situación ocurre cada vez que el codificador encuentra una entrada de la forma cScSc, donde c es un solo carácter, S es una cadena y < i>cS ya está en el diccionario, pero cSc no lo está. 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 el segundo c de cScSc) y emite el nuevo código que acaba de insertar. El argumento anterior muestra que cada vez 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.

Codificación adicional

El esquema simple descrito anteriormente se centra en el propio algoritmo LZW. Muchas aplicaciones aplican codificación adicional a la secuencia de símbolos de salida. Algunos 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 adaptable. Dicho codificador estima la distribución de probabilidad para el valor del siguiente símbolo, en función de las frecuencias de valores observadas 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 mayores probabilidades.

Usos

La compresión LZW se convirtió en el primer método universal de compresión de datos ampliamente utilizado en las computadoras. Por lo general, un archivo de texto en inglés grande se puede comprimir a través de LZW a aproximadamente la mitad de su tamaño original.

LZW se usó 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 LZW como porque gzip producía mejores relaciones de compresión. usando el algoritmo DEFLATE basado en LZ77, pero a partir de 2008 al menos FreeBSD incluye tanto comprimir como descomprimir como parte de la distribución. Varias otras utilidades de compresión populares también usaron LZW o métodos estrechamente relacionados.

LZW se volvió muy utilizado cuando se convirtió en parte del formato de imagen GIF en 1987. También se puede usar (opcionalmente) en archivos TIFF y PDF. (Aunque LZW está disponible en el software Adobe Acrobat, Acrobat usa DEFLATE de forma predeterminada para la mayoría de los datos de imagen basados en tablas de colores y texto en archivos PDF).

Patentes

Se han emitido varias patentes en los Estados Unidos y otros países para LZW y algoritmos similares. LZ78 estaba cubierto por U.S. Patente 4.464.650 de Lempel, Ziv, Cohn y Eastman, cedida a Sperry Corporation, más tarde Unisys Corporation, presentada el 10 de agosto de 1981. Se emitieron dos patentes estadounidenses para el algoritmo LZW: U.S. Patente 4.814.746 de Victor S. Miller y Mark N. Wegman y cedida a IBM, presentada originalmente el 1 de junio de 1983 y U.S. Patente 4.558.302 de Welch, cedida a Sperry Corporation, más tarde Unisys Corporation, presentada el 20 de junio de 1983.

Además de las patentes anteriores, la patente de 1983 de Welch también incluye citas de varias otras patentes que influyeron en ella, incluidas dos patentes japonesas de 1980 (JP9343880A y JP17790880A) de Jun Kanatsu de NEC, NOSOTROS. Patente 4.021.782 (1974) de John S. Hoerning, EE. UU. Patente 4.366.551 (1977) de Klaus E. Holtz y una patente alemana de 1981 (DE19813118676) de Karl Eckhart Heinz.

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 de 1993-1994 entre Unisys y CompuServe (CompuServe fue el creador del formato GIF) provocó un debate de Usenet comp.graphics Pensamientos sobre un formato de archivo de reemplazo de GIF, que a su vez fomentó un intercambio de correo electrónico que finalmente culminó con la creación del formato de archivo PNG (Portable Network Graphics) libre de patentes en 1995.

La patente estadounidense de Unisys sobre el algoritmo LZW expiró el 20 de junio de 2003, 20 años después de su presentación. Las patentes que se habían presentado en el Reino Unido, Francia, Alemania, Italia, Japón y Canadá expiraron todas en 2004, también 20 años después de haber sido presentadas.

Variantes

• LZMW (1985, por V. Miller, M. Wegman) – Búsquedas de entrada para la cadena más larga ya en el diccionario (el partido "actual"); añade la concatenación del partido anterior con el partido actual al diccionario. (Las entradas electorales crecen más rápidamente; pero este esquema es mucho más complicado de implementar.) Miller y Wegman también sugieren eliminar entradas de baja frecuencia del diccionario cuando el diccionario se llena.
• LZAP (1988, por James Storer) – modificación de LZMW: en lugar de añadir sólo la concatenación del partido anterior con el partido actual al diccionario, añadir las concatenaciones del partido anterior con cada subestring inicial del partido actual ("AP" significa "todos los prefijos"). Por ejemplo, si el partido anterior es "wiki" y el partido actual es "pedia", entonces el encoder LZAP añade 5 nuevas secuencias al diccionario: "wikip", "wikipe", "wikipedia", "wikipedia", y "wikipedia", donde el encoder LZMW añade sólo la única secuencia "wikipedia". Esto elimina parte de la complejidad de LZMW, al precio de añadir más entradas de diccionario.
• LZWL es una variante basada en sílabas de LZW.