El algoritmo de Lempel Ziv y Welch, o abreviadamente como mejor se le conoce Algoritmo LZW, es un algoritmo de compresión sin pérdida basado en diccionario, desarrollado por Terry Welch en 1984 bastante tiempo después que fuera publicado el algoritmo LZ78 del que es una versión mejorada, que a su vez era una mejora sustancialmente distinta del algoritmo LZ77.
Si bien, a la luz de la aparición de los algoritmos de Zip y Lempel sobrevino un resurgimiento de la compresión, que permanecía atascada y limitada en los algoritmos estadísticos, este algoritmo abre el camino hacia una mayor eficiencia y velocidad.
La mayoría de los métodos de compresión basados en diccionario requieren dos etapas, una de análisis y una segunda de conversión.
La etapa de análisis inicial tiene por objeto identificar cadenas repetidas para armar el diccionario de equivalencias, asignando códigos breves a estas cadenas. En una segunda etapa, se convierte el texto utilizando los códigos equivalentes para las cadenas repetidas.
Dichos algoritmos también requieren que el diccionario se almacene junto con el texto codificado, incrementando el tamaño del archivo de salida.
El Algoritmo LZ77 desarrollado por Abraham Lempel y Jacob Ziv precisaba guardar 3 datos (Index, Count y Offset), para almacenar una secuencia. Las críticas constructivas vertidas sobre dicho algoritmo influencian la creación del Algoritmo LZ78, desarrollado también por los mismos autores, que solo precisa 2 datos para almacenar la referencia de la secuencia comprimida (count y Offset). El algoritmo LZW mejora los previos en dicho aspecto, pues solo precisa guardar como dato para referenciar la secuencia comprimida 1 dato (index), lo que a su vez simplifica y acelera toda la operativa.
La gran ventaja del algoritmo LZW es que permite crear sobre la marcha el diccionario de cadenas que se encuentren dentro del texto a comprimir y al mismo tiempo (sin requerir otra etapa) se procede a su codificación.
Además, dicho diccionario no precisa ser transmitido con el texto comprimido, puesto que el descompresor puede reconstruirlo, siguiendo el mismo procedimiento que hace el compresor. Si está codificado correctamente, tendrá exactamente las mismas cadenas que tenía el diccionario del compresor.
El diccionario suele comenzar con un tamaño predefinido, y de entrada se precarga con las primeras 256 entradas, una para cada carácter (byte) posible, más un código predefinido usado como un indicador de final de fichero.
Cuando el diccionario se llena al comprimir, se debe elegir entre vaciar el diccionario y volver a precargarlo y empezar de nuevo, o dejar el diccionario fijo. La opción de aumentar el tamaño del diccionario es equivalente a si al principio se establece ese tamaño al que se vaya a aumentar. El compresor deberá emitir un código especial señalando la opción elegida si no está prefijada (no elegible). Originalmente en el diseño del algoritmo, el tamaño del diccionario venía determinado por la limitación de la memoria, era pues frecuente que en las primeras implementaciones del algoritmo el diccionario tuviera solo 4096 entradas (12 bits), que luego se fueron ampliando a 14, 15 y 16 bits (64kb). El tamaño del diccionario en las implementaciones recientes (a fecha de 2022) del algoritmo, es elegible por el usuario.
Durante la descompresión se sigue el mismo procedimiento que durante la compresión. El diccionario se precarga y cuando se ha llenado debe tomarse la misma acción que tomó el compresor. Si no está prefijada por convención en el algoritmo, al comprimir se debe emitir un código especial que el descompresor debe poder reconocer, para realizar exactamente la misma acción.
El algoritmo originalmente contempla que, cuando una secuencia fuera a forzar la ampliación del diccionario por encima del límite de bits prefijado, el diccionario se borre por completo, se inicialice nuevamente con los 256 códigos iniciales más el código de fin de archivo y se recomience el proceso.
Nótese que dado un límite teórico de códigos de n bits, un diccionario nunca podrá contener más de 2n entradas. El diccionario se arma como una tabla donde el código que se emite como salida, es el índice y las cadenas que representa son las entradas de esta tabla. Adviértase que el código en sí no se almacena en la tabla sino que es el índice de la misma por lo que se calcula por la posición en la tabla.
Otra característica importante del algoritmo es que los códigos en la salida se representan por cadenas de bits variables. El diccionario contiene inicialmente 257 códigos, 256 códigos para los 256 caracteres simples posibles con 8 bits y un código que representa el fin de archivo.
Como las 256 entradas precargadas exigen 8 bits para ser referidas por el índice donde se localizan, la siguiente entrada al diccionario comenzará a almacenar a fichero los índices con 9 bits (en el código puede usarse por comodidad enteros de 16 o 32 bits), lo que da para llenar el diccionario hasta la entrada 511. Al llegar a la posición 512, se precisará usar 10 bits, y siguiendo el mismo esquema con cada potencia de 2 (la entradas realizadas se duplican), se requerirá 1 bit más.
En la práctica, se verifica que las primeras entradas, correspondientes a códigos de 12 bits de longitud (4096 entradas) se llenan rápidamente por lo que es habitual comenzar el proceso no con códigos de 9 bits sino directamente con códigos de 12 bits.
Así cada vez que se duplica el tamaño del diccionario exige un bit más. No es preciso emitir un código especial de salida para reconocer la situación, basta simplemente considerarlo en el código para reconocer el caso, tanto en el compresor como en el descompresor, pues van sincronizados en cuanto a la lógica, lo que se conoce en el argot como lockstep. El modo adecuado de reconocer dicha situación es precisamente asignar un código especial, al comienzo será el valor 512, luego 1024, 2048, etc. comprobando con cada entrada que cuando se alcanza dicho valor se suma 1 a los bits que se tendrán que guardar.
A esta tabla se le van agregando sucesivos códigos numéricos por cada nuevo par de caracteres consecutivos que se lean que aún no constan en el diccionario.
Es en este detalle donde reside la brillantez del método: al armar el diccionario sobre la marcha se evita hacer dos pasadas sobre el texto, una analizando y la otra codificando y dado que la regla de armado del diccionario es tan simple, el descompresor puede reconstruirlo a partir del texto comprimido mientras lo lee, evitando así la necesidad de incluir el diccionario dentro del fichero comprimido. Se puede objetar que el diccionario contendrá códigos que no se utilizarán y por tanto contribuye a un tamaño grande del mismo, pero el objetivo es que el fichero comprimido sea pequeño aun cuando los procesos de compresión y descompresión pudieran ocupar mucha memoria con el diccionario.
Las entradas del diccionario pueden representar secuencias de caracteres simples o secuencias de códigos de tal forma que un código puede representar dos caracteres o puede representar secuencias de otros códigos previamente cargados que a su vez representen, cada uno de ellos, otros códigos o caracteres simples, o sea que un código puede representar desde uno a un número indeterminado de caracteres. En realidad, el algoritmo no discrimina entre códigos y caracteres simples pues el diccionario se carga inicialmente de códigos que representan los primeros 256 caracteres simples por lo que estos no son más que otros códigos dentro del mismo diccionario.
Todos los caracteres están inicialmente predefinidos en el diccionario así que siempre habrá al menos una coincidencia, sin embargo, lo que se busca es la secuencia más larga posible. Cada vez que se lee un nuevo carácter se revisa el diccionario para ver si forma parte de alguna entrada previa. Cuando el carácter leído no encuentre una secuencia más larga, entonces se emite la más larga que se hubiera encontrado y se agrega al diccionario una entrada formada por cualquiera que hubiera sido el código previo y este nuevo código. En tanto los caracteres sucesivos que se vayan leyendo ofrezcan más de una entrada posible en el diccionario, se siguen leyendo caracteres. Cuando la cadena sólo tiene una entrada en el diccionario, entonces se emite (guarda, escribe) el código correspondiente a esa entrada y se incorpora al diccionario una nueva entrada que representa el último código emitido y el nuevo.
Se ha comprobado empíricamente que la información en un archivo presenta 'regionalidad', o sea, que diferentes regiones de un mismo archivo presentan distintas regularidades, lo cual hace que el diccionario que se hubiera formado para una región de un archivo pueda no ser útil en otra región distinta.
Que el tamaño de los índices pueda ser incrementado de manera variable es una de las contribuciones de Welch. Otra de ellas fue especificar una estructura de datos eficiente para guardar el diccionario.
Como se ha venido comentando, el diccionario puede incluir códigos especiales que se reservan una posición en el diccionario y que de incluirlos, forman parte de la inicialización del diccionario (como entradas 256 y 257).
Tales códigos son el de diccionario lleno y el de fin de fichero.
De forma resumida el algoritmo de compresión sigue estos pasos:
El diccionario comienza inicialmente añadiendo muchos códigos, porque las secuencias en ese punto son cortas, a medida que el diccionario crece, las secuencias van siendo cada vez más largas, lo que implica que el código emitido está comprimiendo más bytes (caracteres) que lo que sucedía al comienzo, si bien la cantidad de bits, incluso para índices bajos, es mayor (pues como se ha indicado anteriormente, se requiere un bit más cada vez que se duplica el tamaño ocupado del diccionario).
El algoritmo es tanto más eficaz cuanto más secuencias estén parcialmente repetidas y más largas sean. El ratio de compresión suele describir una curva a medida que el diccionario crece y mientras se mantenga la regionalidad vigente.
De forma resumida el algoritmo de descompresión sigue estos pasos:
Durante la descompresión, el diccionario es inicializado con todas las secuencias de tamaño 1 (byte, carácter) y es reconstruido a medida que se van descomprimiendo las entradas, lo que hace innecesario tener que guardar o enviar el diccionario con los datos comprimidos.
El proceso de descompresión va leyendo de la entrada un código de cada vez, del tamaño de los bits que estén vigente. Como el diccionario está inicializado, siempre encuentra el primer y segundo códigos, que son usados para añadir una entrada nueva al diccionario. Más adelante las entradas o refieren a códigos precargados o a los códigos que se han ido añadiendo al diccionario durante la descompresión.
Dado que el algoritmo sirve para comprimir cualquier secuencia de bits, independientemente de si es texto o cualquier otro tipo de información, el ejemplo a continuación no ha sido traducido del original en inglés. En él se supone que los textos a comprimir se componen solamente de letras mayúsculas sin espacios, para lo cual bastan (en inglés) 26 códigos, del 1 al 26, para las mayúsculas más un código (en este caso se ha adoptado el cero, aunque en la práctica el 0 es un carácter válido) para representar el fin de archivo, que se ha representado gráficamente por el símbolo #. El texto a comprimir es:
TOBEORNOTTOBEORTOBEORNOT#
y el proceso de compresión queda representado por la tabla siguiente. Para interpretarla, se sugiere ignorar la representación binaria, que se incluye simplemente para contabilizar el tamaño del archivo de salida. Los códigos del 1 al 26 se corresponden con caracteres simples 1 = A, 2 = B, ... 26 = Z y 27 = "fin de archivo". Del 28 en adelante cada código representa más de un carácter.
Carácter: Código emitido Entrada en el diccionario: (salida): T 20 = 10100 O 15 = 01111 28: TO B 2 = 00010 29: OB E 5 = 00101 30: BE O 15 = 01111 31: EO <--- se agotaron los códigos de 5 bits R 18 = 010010 32: OR <--- se comienza a usar códigos de 6 bits N 14 = 001110 33: RN O 15 = 001111 34: NO T 20 = 010100 35: OT TO 28 = 011100 36: TT BE 30 = 011110 37: TOB OR 32 = 100000 38: BEO TOB 37 = 100101 39: ORT EO 31 = 011111 40: TOBE RN 33 = 100001 41: EOR OT 35 = 100011 42: RNO # 0 = 000000 43: OT#
El texto original, compuesto de 25 caracteres que pueden representarse con 5 bits cada uno nos daría 125 bits. El resultado comprimido produce 5 códigos de 5 bits más 12 códigos de 6 bits, lo cual resulta en 97 bits, una reducción a menos del 78% del original. Nótese que cada carácter leído genera una nueva entrada en el diccionario, independientemente de si se utilizará o no. Esta simplicidad por parte del algoritmo de compresión permite que el descompresor pueda reconstruir el diccionario sin errores.
Cuando se comienza a utilizar 6 bits por código, todos los códigos se emiten con 6 bits, incluso los que originalmente sólo usaran 5 bits, completándose con ceros por izquierda.
Se han dispuesto 6 columnas, se explica el significado de cada una:
Sea la cadena siguiente la que se pretende comprimir:
"tres tristes tigres tragaban trigo en un trigal"
----------------------------------------------------------------- Indice Hash Emite a Guarda Secuencia Num chars dic secuencia fichero en dic referida en secuencia ----------------------------------------------------------------- 257 32528 00116 (t) 114 |tr| 2 258 31101 00114 (r) 101 |re| 2 259 07016 00101 (e) 115 |es| 2 260 11069 00115 (s) 032 |s | 2 261 41259 00032 ( ) 116 | t| 2 262 24505 00257 (r) 105 |tri| 3 263 60675 00105 (i) 115 |is| 2 264 64251 00115 (s) 116 |st| 2 265 18710 00116 (t) 101 |te| 2 266 20494 00259 (s) 032 |es | 3 267 04369 00261 (t) 105 | ti| 3 268 47103 00105 (i) 103 |ig| 2 269 38756 00103 (g) 114 |gr| 2 270 10446 00258 (e) 115 |res| 3 271 08364 00260 ( ) 116 |s t| 3 272 08089 00257 (r) 097 |tra| 3 273 28803 00097 (a) 103 |ag| 2 274 22647 00103 (g) 097 |ga| 2 275 28071 00097 (a) 098 |ab| 2 276 27045 00098 (b) 097 |ba| 2 277 17132 00097 (a) 110 |an| 2 278 34553 00110 (n) 032 |n | 2 279 32125 00261 (t) 114 | tr| 3 280 23582 00114 (r) 105 |ri| 2 281 30853 00268 (g) 111 |igo| 3 282 42809 00111 (o) 032 |o | 2 283 31557 00032 ( ) 101 | e| 2 284 01124 00101 (e) 110 |en| 2 285 41070 00278 ( ) 117 |n u| 3 286 01856 00117 (u) 110 |un| 2 287 33600 00278 ( ) 116 |n t| 3 288 01285 00262 (i) 103 |trig| 4 289 55387 00274 (a) 108 |gal| 3 256 Código especial fin de fichero.
Sigamos el rastro para comprimir la última palabra 'trigal'.
El fichero de salida, contendrá los valores que figuran en la columna Emite a fichero, pero cada código se habrá escrito con 9 bits. Por razones de simplicidad se obvia toda supuesta cabecera que suele acompañar a un fichero comprimido.
El texto a comprimir tiene 47 caracteres, pero solo ha sido preciso emitir (289-257)= 32 códigos + 1 código especial de fin de fichero. Si bien en este punto no se ahorran muchos bits, ya que cada código se emite ahora mismo con 9 bits y al estar el diccionario vacío, las secuencias que se empiezan a formar son cortas. Todavía al final ya puede verse alguna secuencias de 4 caracteres.
Este algoritmo ha influenciado en mayor o menor medida otros que han derivado de éste, así como muchos programas. Otro capítulo referente a la historia de dicho algoritmo es el asunto relativo a las patentes, descrito más ampliamente en una sección más abajo.
El método llegó a ser utilizado de forma moderada, pero en toda su amplitud en el programa compress que llegó a ser más o menos la utilidad estándar de compresión en sistemas Unix alrededor de 1986 (ahora ha desaparecido prácticamente tanto por asuntos legales como técnicos). Otras utilidades de compresión también utilizan este método u otros relativamente cercanos.
Se usó ampliamente desde que se convirtió en parte del formato gráfico GIF en 1987. Puede ser también usado, aunque opcionalmente, en archivos TIFF.
La compresión LZW proporcionaba una relación de compresión mejor en muchas aplicaciones que otros métodos de compresión conocidos en esa época. Llegó a convertirse en el primer método de propósito general de compresión de datos usado ampliamente. En textos largos, comprime aproximadamente a la mitad del tamaño original. Otros tipos de datos son también comprimidos útilmente en muchos casos.
Varias patentes han sido concedidas en Estados Unidos de América y otros países por el algoritmo LZW y similares. El LZ78 estaba bajo la patente 4,464,650, pedida por Lempel, Ziv, Cohn y Eastman y asignada a Sperry Corporation, más tarde Unisys Corporation, el 10 de agosto de 1981. Dos patentes de los Estados Unidos fueron creadas para el LZW: la patente de EE. UU. 4,814,746 por Victor S. Miller y Mark N. Wegman y asignada a IBM, originalmente el 1 de junio de 1983, y la patente estadounidense 4,558,302 por Welch, asignada a Sperry Corporation, más tarde Unisys Corporation, el 20 de junio de 1983.
La patente estadounidense 4,558,302 es la que ha causado la mayor controversia. Unisys una vez garantizó licencias libre de patentes a desarrolladores de software libre y software propietario freeware (gratuito, sin fines comerciales). La compañía finalizó esas licencias en agosto de 1999.
Muchos expertos en leyes concluyen que la patente no cubre dispositivos que sólo descompriman LZW y no puedan comprimir datos usándolo, por esta razón el popular programa Gzip puede leer archivos .Z pero no escribirlos.
Se informó en Debian Weekly News basándose en un hilo de comp.compression, que la patente de Unisys en EE. UU. expiró en diciembre de 2002 - 17 años y 10 días después de ser patentado. Sin embargo la mayoría de las fuentes informan que expiró en junio de 2003, 20 años después de que fuera archivada, porque 35 USC §154(c)(1) especifica que las patentes subsisten 20 años después del Uruguay Round Agreements Act.
De acuerdo con una declaración en la web de Unisys, las patentes de LZW en el Reino Unido, Francia, Alemania, Italia y Japón han expirado en junio de 2004 y la patente canadiense en julio de 2004.
La patente de IBM en EE. UU. expiró en agosto de 2006.