LZW

De Wikipedia, la enciclopedia libre

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.

Tabla de contenidos

1 Descripción del Algoritmo
- 1.1 Un ejemplo simple de un algoritmo de compresión basado en diccionario
2 Usos
3 El asunto de las patentes
4 Lempel-Ziv-Welch vs. Ziv-Lempel-Welch
5 Enlaces externos

[editar] Descripción del Algoritmo

La clave del método reside en que es posible crear previamente y de manera automática un diccionario de cadenas que se encuentren dentro del texto a comprimir. Dicho diccionario no tiene porqué ser transmitido con el texto comprimido, puesto que el descompresor puede construirlo de la misma forma 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 con 256 entradas, una para cada carácter posible. Cada vez que se encuentra una cadena que no está en el diccionario, una cadena más larga consistente, esa cadena encontrada unida con el siguiente carácter que le sigue en el texto se almacena en el diccionario.

La salida del algoritmo consiste en índices enteros del diccionario. Estos inicialmente son de 9 bits cada uno aunque, según crece el diccionario, pueden llegar a ocupar hasta 16 bits. Un símbolo especial se reserva para nivelar el diccionario, lo que hace que se vuelva a la situación original de 256 entradas e índices de 9 bits. Esto tiene utilidad si se está comprimiendo un texto que tiene características variables, pues de este modo un diccionario construido al principio no tendrá mucha utilidad más adelante (cuando las características del texto varíen).

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.

[editar] Un ejemplo simple de un algoritmo de compresión basado en diccionario

En general, la compresión basada en diccionario reemplaza frases con tokens o señales. Si el número de bits del token es menor que el número de bits de la frase, la compresión ocurrirá.

Texto sin comprimir:

"soy tonto y como soy tonto, no puedo decirte que soy tonto"

Texto comprimido:

"$1 y como $1, no puedo decirte que $1. $1=[soy tonto]"

Por supuesto el ejemplo dista mucho de ser eficiente, pero ilustra la compresión a través del reemplazo de frases.

[editar] Usos

El método llegó a ser moderadamente, aunque ampliamente, usado 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 y 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.

[editar] El asunto de las patentes

Varias patentes han sido concedidas en los Estados Unidos de América y otros países por el algoritmo LZW y similares. El LZ78 estaba bajo la pantente 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. expirará en agosto de 2006.

[editar] Lempel-Ziv-Welch vs. Ziv-Lempel-Welch

Aunque el acrónimo LZW obviamente se refiere a los inventores como Lempel, Ziv y Welch, alguna gente opina que el derecho de propiedad intelectual va a Ziv primero, de modo que el método debe llamarse algoritmo Ziv-Lempel-Welch, y no el algoritmo Lempel-Ziv-Welch.