El compresor LZW se basa en el desarrollado por Abraham Lempel y Jakob Ziv en 1.977, denominado LZ77. Posteriormente, en 1.984, Terry A. Welch lo modificó y su nombre quedó como lo conocemos ahora, LZW.
LZW es un compresor sin pérdida que utiliza un diccionario de símbolos/patrones recurrentes que se crean según se leen los caracteres (bytes) a procesar, agrupa los símbolos en cadenas y estas las convierte en códigos. Una subcadena se representa con un único número de código, muy diferente al método Huffman que se basa en la construcción de árboles.
La forma de construir el diccionario hará que este tenga muchos índices que no se utilizarán; Inconveniente que surge al realizar sólo una pasada del fichero, pero que aporta la ventaja de reducir el tiempo de proceso al leerse una sola vez el documento a comprimir y sin necesidad de enviar el diccionario para la decodificación del archivo resultante.
Existe una peculiaridad en este algoritmo, si el archivo a comprimir no contiene ninguna información repetitiva, el fichero comprimido puede ser de mayor tamaño que el original. En las primeras versiones del algoritmo se definía un número máximo de entradas en el diccionario para que el proceso no se quedara sin memoria, solían utilizar subcadenas de longitud de 12 bits (2 ^ 12 = 4096).
El algoritmo se comenzó a utilizar para la compresión de comunicaciones vía modem, para ficheros GIF y PDF, y también en el comando ‘compress’ de Unix/Linux. Además, es/era una práctica de codificación para los estudiantes de informática. Existen versiones y herramientas que aplicadas a condiciones particulares pueden mejorar su rendimiento, algunas son: LZAP, LZJB, LZMW, LZRW1-5, LZW-FP, LZWL, MultiPLZW, OLZW, SharpLZW y otras.
Veamos cómo trabaja:
- En primer lugar, tanto el compresor como el descompresor crean un diccionario con todos los símbolos que componen el lenguaje. El diccionario del ejemplo se crea con los 256 valores ASCII que podrían ser sustituidos por cualquier otro conjunto de símbolos.
- Para la compresión lee los datos byte a byte y los codifica con el número que representa su índice en el diccionario. Cada vez que encuentra una nueva subcadena (más de un carácter) que no está en el diccionario, la agrega asignándola el último índice + 1, en el caso de que exista, lee otro carácter realizando nuevamente las comprobaciones anteriores y grabando o no un nuevo código con la subcadena obtenida. Como resultado tendrá un diccionario con una serie de códigos numéricos que representarán las palabras o subpalabras del texto origen.
- Para la descompresión crea el diccionario con todos los símbolos pero con valores numéricos como claves (256 valores ASCII). Después comienza a leer los códigos del fichero a descomprimir, busca el código/índice en el diccionario y genera la subcadena asociada con él. En secuencia utiliza el mismo procedimiento de entrada al diccionario que en la compresión. Cuando en la lectura del fichero encuentra un código que se sale del rango de valores (0-255) toma la subcadena que previamente introdujo en el diccionario.
Ejemplo del algoritmo LZW:
Tal como ha sido diseñado el ejemplo, tenéis que tener en cuenta que para ficheros grandes, digamos de gigabytes, el rendimiento del proceso caerá y la memoria del equipo puede agotarse. Por otro lado, podéis crear vuestro propio compresor, eficiente, y adaptado a vuestras necesidades. El tiempo de ejecución se limita a grabar y buscar en el diccionario de códigos para crear/determinar si hay una coincidencia
En el gráfico de salida se puede comprobar que existen muchos códigos que no se utilizan. Si el documento a comprimir fuese mayor, la ratio de compresión mejoraría y los códigos del diccionario serían más utilizados.
Más abajo está el fuente en Java y el fichero que he utilizado para ver el rendimiento y que nuestro amigo Miguel de Cervantes ha sido tan amable de proporcionar. En este caso los resultados son halagüeños, el tamaño del texto origen es de 1.018.040 bytes, comprimido: 180.370 bytes, reduciendo el fichero origen al 0,177% de su tamaño.
Código fuente: LZW programa en JAVA
Fichero de prueba: DON QUIJOTE DE LA MANCHA