[Infraestructura Net 8.0] - Algoritmo LZW

Enlaces de descarga

Algoritmo LZW Descripción

Algoritmo LZW, es un algoritmo de compresión sin pérdida. 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.

Descripción del algoritmo

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

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.

La entradas nuevas al diccionario

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.

Códigos especiales

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.

Compresión

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.

Descompresión

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.