LZSS

El algoritmo de compresión lz77 (acrónimo de Abraham Lempel, Jacob Ziv y 1977) pertenece a la familia de compresores sin pérdida, también llamados compresores de texto, a los cuales se les llama así porque no omiten información del archivo al comprimirlo, al contrario que los compresores que utilizan algoritmos del tipo lossy, que omiten algo de información pero que disminuyen considerablemente el tamaño del archivo original, el cual es el caso de los archivos MP3, MPG, jpeg, etc.

Características

Los compresores basados en algoritmos sin pérdida se utilizan cuando la información a comprimir es crítica y no se puede perder información, por ejemplo en los archivos ejecutables, tablas de bases de datos, o cualquier tipo de información que no admita pérdida.

El modelo lz77 es muy usado porque es fácil de implementar y es bastante eficiente.

En 1977 Abraham Lempel y Jacob Ziv presentaron su modelo de compresión basado en diccionario, para compresión de texto –compresión de texto se refiere a compresión sin pérdida para cualquier tipo de datos–. Hasta la fecha todos los algoritmos de compresión desarrollados eran básicamente compresores estáticos. El nuevo modelo fue llamado lz77. La salida consistía siempre en desplazamientos o corrimientos y tamaños del texto visto anteriormente. También se incluía en la salida el siguiente byte después de una coincidencia, porque el contexto (últimos bytes vistos) de este byte es la frase, y si no era parte de la frase (la coincidencia), luego tal vez no se había comprimido, así que, ¿para qué desperdiciar tiempo tratando de encontrar una coincidencia (o espacio) para él?

En 1982 James Storer y Thomas Szymanski basados en el trabajo de Lempel y Ziv, presentaron su modelo, el lzss. La diferencia principal es en la salida, lz77 siempre daba un par desplazamiento/tamaño, aun si la coincidencia era de un solo byte (en cuyo caso usaban más de ocho bits para representar un byte) de manera que el LZSS usa otro truco para mejorarlo: usa banderas (flags), que ocupan un solo bit y nos informan de lo que viene luego: una literal o un par desplazamiento/tamaño y este algoritmo es el que actualmente usamos, pero el lzss es comúnmente llamado lz77, así que lo llamaremos lz77 de este punto en adelante, pero es importante recordar que también puede ser llamado LZSS. LZSS también puede usar árboles binarios o árboles de sufijos para hacer búsquedas más eficientes.

La teoría es muy simple e intuitiva. Cuando se halla una coincidencia (también llamada frase o conjunto de bytes que ya han sido vistos en el archivo de entrada) en lugar de escribir dichos bytes se escribe el desplazamiento o tamaño de la repetición: dónde está y su longitud.

Éste es un modelo basado en diccionario, porque se mantiene un diccionario (que en este caso se conoce como “ventana corrediza”) y se hace referencia a ella con pares desplazamiento/tamaño. Esta versión de lz77, usa una ventana corrediza, la cual tiene un tamaño máximo, de manera que la ventana no puede ser el archivo completo, en su lugar, la ventana corrediza mantiene los últimos bytes “vistos”.

Comprimiendo

Imaginemos que estamos comprimiendo el texto “ab ab”, leemos hasta “ab ” y lo escribimos sin comprimir, luego leemos “ab” y escribimos lo siguiente: con el “desplazamiento” de 0 se halló una coincidencia de dos bytes repetidos.

Descomprimiendo

Es bastante simple. Primero leemos “ab ” y luego copiamos los bytes de ahí así:

Obtener ‘a’.  “a”
Obtener ‘b’.  “ab”
Obtener ‘ ‘.  “ab ”

Obtener desplazamiento/tamaño. Copiar dos bytes desde la posición 0. (“ab”) 
“ab ab”

¿Cómo funciona?

Pero, ¿cómo sabe el descompresor si lo que lee es un par desplazamiento/tamaño o un byte sin comprimir? La respuesta es simple, usamos un prefijo, un bit que actúa como una bandera, de forma similar a un interruptor con dos estados que nos permite saber qué tipo de datos vienen a continuación.

Si el prefijo es 0, entonces lo que viene es un byte sin comprimir. Si, por el contrario, el prefijo es 1, entonces lo que sigue a continuación es un par desplazamiento/tamaño. A estos prefijos también se les llama “banderas”.

El par desplazamiento/tamaño es llamado una palabra clave. Una palabra clave es un grupo de bits (o bytes) que contienen alguna clase de información usada por el compresor y el descompresor. La otra salida posible de lz77 es un literal, la cual es simplemente un byte sin comprimir, de manera que la salida de lz77 puede ser de tres formas:

Literales: son simplemente bytes sin comprimir.
Palabras clave: en nuestro caso son pares tamaño/desplazamiento.
Banderas: simplemente nos indican si los datos que hay a continuación son literales o palabras clave.

Ahora, como ejemplo, veamos de nuevo nuestra cadena y una salida real de un algoritmo lz77:

Obtener ‘a’.  Sin coincidencia.  Bandera 0. Literal ’a’.
Obtener ‘b’.  Sin coincidencia.  Bandera 0. Literal ’b’.
Obtener ‘ ’.  Sin coincidencia.  Bandera 0. Literal ’ ’.
Obtener ‘a’.  Coincidencia.      Bandera 1. Palabra clave: desplazamiento = 0, tamaño = 2.

Como puede verse la bandera solo tiene dos estados posibles, de manera que solo necesitamos un bit para representarla. Ahora no deberíamos representar la banderas como bytes completos, deberíamos trabajar con bits. La salida de esta compresión es llamada un flujo de bits, porque es un flujo de símbolos de tamaño variable, y la unidad mínima es el bit.

Ventana Corrediza

Si se observa el ejemplo anterior nuevamente, uno podría preguntarse: ¿Dónde buscamos las coincidencias para una frase? La respuesta es buscar hacia atrás, en los datos que ya hemos procesado. Esto es conocido como la ventana corrediza. La ventana corrediza es un buffer que mantiene los bytes que están antes de la posición actual en el archivo. Todos los bytes no comprimidos de la salida (las literales) se añaden a la ventana corrediza y también los bytes que forman una coincidencia.

Veamos nuestro ejemplo nuevamente:

Obtener ‘a’. VC: “”.    Sin coincidencia.  Bandera 0. Literal ’a’.
Obtener ‘b’. VC: “a”.   Sin coincidencia.  Bandera 0. Literal ’b’.
Obtener ‘ ’. VC: “ab”.  Sin coincidencia.  Bandera 0. Literal ’ ’.
Obtener ‘a’. VC: “ab ”. Coincidencia.      Bandera 1. Palabra clave: desplazamiento = 0, tamaño = 2.

Como puede verse, cuando buscamos coincidencias, comparamos los datos que tenemos en nuestra ventana corrediza (VC) con los datos en la posición actual.

¿Así que debemos mantener un buffer con los datos en la posición actual y un buffer con la ventana corrediza? En algunas implementaciones esto puede ser verdad, pero la implementación que se muestra aquí no es la forma en que se hacen las cosas; porque ambos, la ventana corrediza y los bytes en la posición actual, no son más que el archivo mismo. Solo mantenemos un buffer, el cual contiene al archivo. Luego solo debemos preocuparnos del puntero a la posición actual, y la ventana corrediza esta justo antes de dicho puntero. De hecho se recomienda tener el archivo completo (o al menos un bloque grande del mismo) y comprimirlo, de manera que no nos preocupamos de leer más bytes.

Hablemos ahora sobre la ventana corrediza, ¿qué tamaño debería tener? Podríamos trabajar con el archivo completo, pero debemos pensar en el desplazamiento necesario para especificar la posición o la coincidencia. Este desplazamiento no es desde la posición 0 (el principio del archivo) a la coincidencia, es desde la posición actual hacia atrás. De manera que en el ejemplo el desplazamiento debe ser de 3 en lugar de 0 (de manera que, cuando se descomprime, el descompresor obtiene un tres y lo resta del desplazamiento actual). Como es de esperar, cuanto mayor sea el tamaño de la ventana, mayor número de bits necesitaremos para almacenar el puntero, de manera que debemos elegir un tamaño para la ventana corrediza. 4K es un tamaño utilizado normalmente, pero se sabe que cuanto mayor es la ventana corrediza, mejor es la compresión. De manera que cuando se implementa se puede escoger cualquier tamaño y considerar que si, por ejemplo, elegimos un tamaño de 8K necesitaremos 13 bits para el desplazamiento.

Tamaños

Otro aspecto que debemos elegir es el tamaño de la longitud. Así que, ¿cuántos bits utilizamos para la longitud? Podemos elegir cualquier tamaño que deseemos, pero debemos considerar que afinar los bits del tamaño de la longitud y los bits del puntero de desplazamiento podemos mejorar la compresión en algunos archivos y empeorarla en otros, así que si estamos diseñando un compresor para un único archivo, deberían encontrarse los valores más apropiados, de lo contrario usaremos un tamaño de 0-32, de solo 5 bits.

Otro aspecto importante es la longitud mínima de una coincidencia. En nuestro caso hemos elegido utilizar 13 bits en el desplazamiento y 5 en la longitud de la coincidencia, 18 bits en total, de manera que una coincidencia debería ser de, por lo menos, 3 bytes. Porque si codificamos una coincidencia con dos bytes (16 bits) y utilizamos 18 bits para almacenar la cadena estamos utilizando 2 bits más que si lo guardamos como un literal.

Luego se levanta otra pregunta. ¿Si nunca tendremos coincidencias de 0, 1 o 2 bytes, entonces por qué tenemos espacio para ellas en la longitud?

Para sacar el mayor provecho posible. Nuestro tamaño aún será representado con 5 bits, pero su rango en lugar de ser 0-32 será 3-35. ¿Cómo hacemos esto? Simplemente restamos al tamaño (antes de guardarlo) 3, y el descompresor lo leerá y añadirá 3.

Marcador de Fin

Ahora que sabemos cómo se realiza la descompresión debemos notar que el descompresor debería saber cómo terminar o cuándo parar. Esto puede realizarse de dos formas:

Se tiene un símbolo que marca el final de los datos.
Se guarda junto a la cadena de bits el tamaño del archivo de entrada.

Tal vez el segundo método sea preferible. Es un poco más lento, pero al mismo tiempo que se usa para conocer el final de los datos. Puede ser utilizado en una posible interfaz y puede ayudarnos a evitar algunos problemas. De cualquier manera, si se desea utilizar un marcador de fin de datos podríamos usar tamaño cero para ello. La forma en que se hace es la siguiente:

El rango será de 3-34, en este caso debemos restar al tamaño (cuando lo guardamos) 2. De manera que el rango 1-32 se convierte 3-34, y el compresor solo debe ocuparse de esto al comprimir el archivo, una vez la compresión es finalizada, la salida desplazamiento/tamaño tiene tamaño de 0.
El descompresor debe entonces verificar cada vez que lee un tamaño si este tamaño es 0, para saber si se ha alcanzado el final del archivo.

Trabajando con Bits

Como puede verse, los desplazamientos y tamaños son de longitud variable, y las banderas toman únicamente un bit, de manera que debemos usar bits en lugar de bytes. Esto es muy importante en la mayoría de los algoritmos de compresión.

La mayoría de operaciones trabajan con bytes y cuando se escribe información a un archivo la unidad mínima es el byte, entonces, para escribir bits hacemos un uso inteligente de algunas instrucciones.

Para realizar esto podemos usar ASM, o si no, puede ser implementado en C. Continuaremos las operaciones con bits en ASM. La idea principal es mantener un byte y un contador con los bits escritos, luego cuando tenemos 8 bits, escribimos ese byte al archivo y comenzamos de nuevo con el siguiente byte. A continuación se presenta un ejemplo utilizando instrucciones de ASM.

@@put_bits_loop:
push cx                ;el número de bits a escribir
mov bh,_byte_out       ;el byte de salida (dónde escribir)
mov bl,_byte_in        ;el byte de entrada (los bytes a escribir)
mov al, bl             ;al ;almacenamos el byte a leer en al
shr al,1               ;desplazamos al a la derecha, first bit in the carry flag
xor ah, ah             ;ah=0
adc ah,0               ;ah 0 y el acarreo
mov bl, al             ;guarda el byte de entrada
mov cl,_total_bits     ;bits que hemos escrito
shl ah, cl             ;pone el bit en su posición desplazando a la izquierda
or bh, al              ;pone el bit en el byte de salida
mov _byte_out,bh       ;guardarlo
inc _total_bits        ;bits escritos
cmp _total_bits,8      ;¿Tenemos que escribir todo el byte?
jne @@no_write_byte    ;nop E-)
mov di,ptr_buffer      ;el puntero al buffer
mov es:[di],bh         ;el byte (es el segmento del buffer)
inc di                 ;byte en el buffer
mov ptr_buffer,di      ;guardado para la próxima vez
inc bytes_writed       ;cuando el buffer está lleno escribir
mov _byte_out,0        ;a file or something like that so the next time is clear
@@no_write_byte:       ;lo hemos guardado
pop cx                 ;¿más bits para escribir?
dec cx                 ;sí, repetir todo
jnz @@put_bits_loop

Se presenta la rutina putbits, los nombres de las variables se explican por sí solos pero aún y todo presentamos aquí una descripción:

_byte_out: el byte que será escrito en el buffer de salida, mantiene los bits que estamos escribiendo actualmente.
_byte_in: el byte que contiene los bits que deseamos escribir.
_total_bits: el número de bits que se han escrito actualmente, cero al principio.
Ptr_buffer: desplazamiento del buffer.

Cuando se ingresa esta rutina cx debe tener el número de bits a escribir, y _bite_in los bits a escribir. Hay que tener cuidado, después de ingresar el ciclo hay que probar si cx es 0 porque si es cero y no se prueba escribirá un bit, luego haría cx - 1, lo que daría 255 con la consecuencia de escribir 255 bits.

Recuerde:

Test cx, cx
jz@@put_bits_end

Esta es la estructura (cómo son escritos los bits) para un byte:

Bit 8

Bit 7

Bit 6

Bit 5

Bit 4

Bit 3

Bit 2

Bit 1

Cuando se han escrito todos los bits (la compresión ha finalizado) debe probarse si hay aún bits esperando para ser escritos, así que si hay algunos (total_bits != 0) escribimos _byte_out, e incrementamos todos los punteros de manera que no dejemos datos sin escribir.

Archivo de Salida

Ahora debemos definir el formato del archivo de salida, el cual será simple, únicamente debe llenar nuestras necesidades, los datos comprimidos se verán como:

Primero una palabra con el tamaño del archivo original y si se desea algunos números como identificación.
Luego el flujo de bits, el cual constituye y contiene los datos comprimidos.

Pseudocódigo

Recordemos como trabaja lz77, uno se encuentra en una posición dada y trata de hallar hacia atrás (porque se está seguro de que el descompresor ya ha decodificado esos bytes cuando uno se encuentra en dicha posición) una coincidencia, bytes que son iguales a los bytes en la posición actual; si se encuentran se escribe una palabra clave, de otra forma se escribe una literal para poder seguir comprimiendo.

Secuencia básica: Compresor

Guardar el tamaño del archivo a comprimir.
Repetir hasta que no haya más bytes para comprimir.
Escanear el buffer de entrada comenzando en posición_actual - tamaño_de_ventana_corrediza hasta el byte actual que estamos comparando. (Notar que el descompresor no puede copiar bytes de una posición desde donde sus bytes no han sido previamente definidos).
¿Hemos encontrado un byte igual al actual?
Caso Si:
- Comparamos el siguiente byte desde la posición actual con el byte en la posición siguiente de donde encontramos un byte igual al primero.
- Continuar comparando hasta que encontremos un byte que no es igual.
- Se ha encontrado un byte que no es igual. ¿Es el número de bytes mayor que tres?
- Caso Si:
  - Escribir el desplazamiento del PRIMER byte hallado y el número de bytes repetidos (tamaño).
  - Movemos el puntero a la posición con el número de bytes repetidos (porque no los hemos “salvado”) y seguimos buscando.
  - También se escribe una bandera 1.
- Caso No:
  - Continúa la búsqueda.
Caso No:
- Si no se encuentra ninguna coincidencia, simplemente se escribe un byte sin comprimir (también se escribe un literal si no hay datos en la ventana corrediza).
- Debe recordar poner la bandera a 0.

Secuencia básica: Descompresor

Se lee el tamaño del archivo sin comprimir.
Se repite hasta que se ha descomprimido todo el archivo.
Se lee un bit (la bandera).
Si es 0:
- Se leen 8 bits, se escriben al buffer de salida (recordar que son un byte descomprimido) y se incrementa el puntero a la salida.
Si es 1:
- Se lee el desplazamiento completo (13 bits), luego el tamaño, copiar “tamaño” bytes de “desplazamiento” a la posición actual, y añadir al puntero a la salida “tamaño”.

Buscando Coincidencias

La forma en que se buscan las coincidencias es la siguiente: se mantiene un puntero a la posición actual. Al principio de cualquier iteración, se computa el desplazamiento a la ventana corrediza. Esto se puede hacer fácilmente obteniendo el puntero a la posición actual y restándole el tamaño de la ventana corrediza, en caso de que sea menos que cero (negativo) simplemente se ajusta a cero.

Digamos que tenemos una ventana corrediza de 4 bytes de largo (así que gastamos dos bits para especificar el desplazamiento) y tenemos la siguiente cadena: “1234567”

Pa:0. Pvc=0-4=0. Actual: "1234567" Ventana Corrediza: "..."
Pa:1. Pvc=1-4=0. Actual: "234567" Ventana Corrediza: "1"
Pa:2. Pvc=2-4=0. Actual: "34567" Ventana Corrediza: "12"
Pa:3. Pvc=3-4=0. Actual: "4567" Ventana Corrediza: "123"
Pa:4. Pvc=4-4=0. Actual: "567" Ventana Corrediza: "1234"
Pa:5. Pvc=5-4=1. Actual: "67" Ventana Corrediza: "2345"
Pa:6. Pvc=6-4=2. Actual: "7" Ventana Corrediza: "3456"

Donde Pa es el puntero al byte actual, y Pvc es el puntero al inicio de la ventana corrediza. Cuando se usan punteros al archivo de entrada completo, debemos cuidar el tamaño de la ventana corrediza.

Véase también

Enlaces externos

Lista de manuales de algoritmos de compresión sin pérdida Archivado el 31 de enero de 2009 en Wayback Machine. (Español)

Datos: Q2679