LZW

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 entra 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 sí al principio se establece ese tamaño al que se vaya a aumentar. El compresor deberá emitir un código especial señalando dicha 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 (por ejemplo) 16 bits, quiere decir que un diccionario nunca podrá contener más de 65536 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 su 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.

1. Diccionario lleno: Indicará al descompresor que debe hacer la acción que se espera, típicamente borrar e inicializar el diccionario. Como se ha indicado más arriba, puede optarse al comprimir por dejar el diccionario fijo o alguna otra opción, de haber varias opciones, podría seguirle otro código (que no es interpretable para descomprimir), refiriendo la acción a tomar (típicamente valores: 0,1,2,3... que identifica la acción seguida por el compresor).
2. Fin de fichero: Señala que se alcanzó el final de la descompresión. Si existe contenido detrás no pertenece al fichero a descomprimir. Típicamente puede ser un comentario que se acompaña al fichero comprimido.
3. Aumento del tamaño del código en 1 bit más: Cuando las entradas en el diccionario han ocupado todas las posiciones que son direccionables con los bits actuales, puede emitirse un código especial para indicar al descompresor que haga lo mismo. Teniendo en cuenta que el descompresor recrea el diccionario en la misma medida, la emisión de este código no es estrictamente necesaria. Si bien es posible elegir empezar directamente con 12 bits u otro valor que el descompresor no tenga previsto, luego si un descompresor considera que siempre se empieza con 9 bits, podría recibir antes que nada varios de estos códigos para empezar a usar los bits que el compresor haya estimado como el valor inicial. Así mismo este valor inicial de bits podría ser consignado en la cabecera del fichero. Por lo que definitivamente no tiene una utilidad práctica si en el diseño del sistema se ha previsto la situación.

De forma resumida el algoritmo de compresión sigue estos pasos:

1. Inicializar el diccionario con todas las entradas prefijadas. Bits = 9; EntradasPrefijadas = 257 (256 bytes + 1 código especial); LimiteDupSecuencias = 512; index = EntradasPrefijadas
2. Hacer: Leer la entrada actual.
3. Repetir mientras se localice en el diccionario la secuencia más larga que además contenga la entrada actual.
4. Emitir a la salida el índice de la secuencia más larga localizada (es el dato a guardar con el actual tamaño de Bits).
5. Añadir al diccionario (en posición index) la entrada actual apuntando al índice de la secuencia guardada. index +=1
6. Si el diccionario está lleno, vaciar el diccionario y volver al paso 1.
7. Si la ocupación del diccionario = LimiteDupSecuencias (duplica el tamaño) a partir de ahora los códigos que se emitan usarán un bit más. Bits +=1; LimiteDupSecuencias *=2
8. Volver al paso 2 hasta fin de fichero
9. Emitir el código especial de fin de fichero.

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:

1. Inicializar el diccionario con todas las entradas prefijadas. Bits = 9; EntradasPrefijadas = 257 (256 bytes + 1 código especial); LimiteDupSecuencias = 512; index = EntradasPrefijadas
2. Leer el código actual comprimido (con el tamaño de bits actual).
3. Si (código actual = fin de fichero. Salir.
4. Hacer: mientras (código actual > EntradasPrefijadas)
5. Concatenar valor en la posición index del diccionario a la secuencia.
6. código actual = el código al que apunta el código actual en la posición del diccionario
7. Repetir
8. Concatenar valor en la posición index del diccionario a la secuencia.
9. Emitir a la salida la secuencia concatenada en orden inverso.
10. Añadir al diccionario (en posición index) la entrada actual apuntando al índice de la secuencia guardada. index +=1; Vaciar secuencia (la secuencia concatenada).
11. Si el diccionario está lleno, vaciar el diccionario y volver al paso 1.
12. Si la ocupación del diccionario = LimiteDupSecuencias (duplica el tamaño) a partir de ahora los códigos que se emitan usarán un bit más. Bits +=1; LimiteDupSecuencias *=2
13. Volver al paso 2 hasta fin de fichero

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 va 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 dicioario. 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:

La columna Indice dico apunta a la siguiente entrada vacía en el diccionario y en la que se guardarán los datos.

La columna Hash secuencia, contiene el hash que se ha calculado a la nueva secuencia que se forma con el hash de la secuencia previa y el carácter actual siendo tratado.

La columna Emite a fichero contiene el código (se expone en decimal), que se guardará como valor de la compresión, con la cantidad de bits actuales. En el presente ejemplo, actualmente son 9 bits.

La columna Guarda en dico contiene el valor del carácter actual que se añade y que por tanto extiende la secuencia, como se muestra en la columna Secuencia referida.

La columna Secuencia referida, muestra la secuencia que se aloja en el diccionario bajo el índice que se muestra en su columna. Es decir a futuro podrá localizarse esa secuencia, que yace en el diccionario con el índice indicado, tomado de la tabla hash, en el índice que señala el hash.

La columna Num Chars en secuencia', señala cuantos caracteres tiene actualmente la secuencia que es referida el diccionario por el índice. Esta columna se mantiene solo para reflejar como evoluciona el algoritmo.

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
dico    secuencia  fichero      en dico  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 primer carácter es la; 't', que se localiza en el índice 116 del diccionario (es una entrada precargada, se han omitido por razones de extensión y obviedad).

- Tomamos de la entrada el siguiente carácter: 'r', ahora computamos el hash para la entrada formada por la secuencia 116 y 114 (los valores 't' + 'r'), nos arroja el hash 32528, consultamos la tabla hash en el índice 32528 y contiene el valor 257, que es el índice en el diccionario, si miramos dicha entrada (ver línea index 257), en efecto allí se localiza la secuencia 'tr', así como los índices 116 y 114 (secuencia previa y la que la extiende).

- De nuevo tomamos otro carácter de la entrada: 'i', computamos el hash para 257 y 105 (valores en diccionario de 'tr' + 'i'), el hash calculado resulta ser el 24505, ahora miramos el contenido en la tabla hash en ese índice (24505) que contiene el índice del diccionario donde se localiza esa secuencia: 262. Podemos mirar dicha línea y ahí se verán todos estos datos.

- Una vez más tomamos el siguiente carácter de la entrada: 'g', computamos su hash para los valores 262 y 103 (valores en el diccionario para la secuencia 'tri' y 'g', la secuencia encontrada y el actual carácter). Y nos ofrece el hash 01285, consultamos la tabla hash en dicho índice y esta vez resulta que está vacío. No existe, entonces tomamos el índice actual no ocupado en el diccionario que es la posición 288, en dicha posición se guardan los valores: 262 y 103, para que puedan ser buscados en lo sucesivo. En la tabla hash en el índice calculado 01285, guardamos el índice que referencia a la secuencia recién formada, 288, y a fichero se emite el código 262. Así este último código emitido de 9 bits, ha logrado comprimir 3 caracteres y ha extendido esa secuencia en 1 más. Aumentamos la entrada libre del diccionario en 1 (289).

- Como la secuencia ha extendido la previa porque no existía en el diccionario, tomamos el carácter que ha extendido la secuencia anterior 'g', que es una entrada precargada y se localiza en la posición 103.

- Ahora tomamos el siguiente carácter que es 'a', conmutamos el hash para 103 y 98 (valores en diccionario de 'g' + 'a'), el hash calculado resulta ser 22647, mirando en la tabla hash en ese índice, encontramos el valor 274, que es donde se localiza esa secuencia en el diccionario.

- Tomamos el siguiente carácter 'l', computamos el hash para 274 y 108 (valores en diccionario de 'ga' + 'l'), que arroja el hash 55387, este hash no está ocupado en la tabla hash, entonces almacenamos en la tabla hash la posición libre actual del diccionario (289), que será donde se localice en lo sucesivo la secuencia 'gal' y la entrada del diccionario 289, apunta a la secuencia menor 'ga' posicionada en la posición 274 del diccionario.

- Como hemos llegado al final del fichero, emitimos el código especial 256 con la cantidad de bits actuales, que son 9.

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.

La cadena original precisaba: (47*8)= 376 bits.

La cadena ahora comprimida precisa: (33*9)= 297 bits.