LZW
LZW (Lempel-Ziv-Welch) es un algoritmo de compresión sin pérdida desarrollado por Terry Welch en 1984 como una versión mejorada del algoritmo LZ78 desarrollado por Abraham Lempel y Jacob Ziv.
Descripción del algoritmo
La mayoría de los métodos de compresión se basan en un análisis inicial del texto para identificar cadenas repetidas para armar un 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. Esto requiere dos etapas, una de análisis y una segunda de conversión y también requiere que el diccionario se encuentre junto con el texto codificado, incrementando el tamaño del archivo de salida.
La clave del método LZW reside en que es posible crear sobre la marcha, de manera automática y en una única pasada un diccionario de cadenas que se encuentren dentro del texto a comprimir mientras al mismo tiempo se procede a su codificación. Dicho diccionario no es transmitido con el texto comprimido, puesto que el descompresor puede reconstruirlo usando la misma lógica con que lo hace el compresor y, si está codificado correctamente, tendrá exactamente las mismas cadenas que el diccionario del compresor tenía.
El diccionario comienza pre-cargado con 256 entradas, una para cada carácter (byte) posible más un código predefinido para indicar el fin de archivo. A esta tabla se le van agregando sucesivos códigos numéricos por cada nuevo par de caracteres consecutivos que se lean (esto no es literalmente cierto, según se describe más adelante), aun cuando todavía no sea posible prever si ese código se reutilizará más adelante o no.
Es en este detalle donde se encuentra 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í incluir el diccionario dentro del texto comprimido. Se puede objetar que el diccionario estará plagado de códigos que no se utilizarán y por tanto será innecesariamente grande, pero en la práctica el diccionario no crece demasiado y aún si lo hiciera no importa mucho pues el objetivo es que el archivo 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.
Cada vez que se lee un nuevo carácter se revisa el diccionario para ver si forma parte de alguna entrada previa. 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 cadena más larga posible. Si el carácter leído no forma parte de más de una cadena 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. Si el carácter leído sí forma parte de más de una cadena del diccionario, se lee un nuevo carácter para ver si la secuencia formada por el carácter previo y el nuevo es alguna de las encontradas en el diccionario. 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 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.
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. Para esto serían necesarios códigos de 9 bits, lo cual quiere decir que aún hay disponibles 255 códigos de 9 bits para representar cadenas de caracteres. Cuando se llenan estas 255 entradas del diccionario, se amplían los códigos con un nuevo bit, lo cual permite 512 nuevas entradas. Cuando se completan estas 512 entradas, se agrega un bit y se disponen de 1024 nuevas entradas y así sucesivamente. 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.
A su vez, 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. El algoritmo preve que, cuando una cadena fuera a forzar la ampliación del diccionario a 17 bits, 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 este límite de códigos de 16 bits, esto quiere decir que un diccionario nunca podrá contener más de 65536 entradas, cada una de ellas de 2 códigos de 16 bits, o sea cuatro bytes por entrada. El diccionario, entonces, se arma como una tabla donde el código es el índice y las cadenas que representa son las entradas de esta tabla. Adviértase que el código en si no se almacena en la tabla sino que es el índice de la misma por lo cual no se almacena sino que se calcula por la posición en la tabla. En total, una tabla llena ocupa 65536 entradas de 4 bytes cada una, o sea 262144 caracteres (256 kbytes) lo que es absurdamente poco para los ordenadores actuales.
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.
Un ejemplo simple del algoritmo LZW de compresió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.
Usos
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.
Patentes
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 thread, 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.
Enlaces externos
- United States Patent 4,558,302
- "LZW Data Compression", by Mark Nelson (DDJ Artículo con código fuente)
- (Artículo corto y posiblemente con una simplificación de la verdadera historia, que se puede encontrar algo más detallada en la página de GIF)
- List of LZW libraries, papers and other resources el 1 de diciembre de 2005 en Wayback Machine.
- Lista de manuales de algoritmos de compresión sin pérdida