Elalgoritmo de compresiónlz77 (acrónimo deAbrahamLempel,JacobZiv y 1977) pertenece a la familia de compresores sin pérdida, también llamadoscompresores de texto, a los cuales se les llama así porque no omiten información del archivo al comprimirlo, al contrario que los compresores que utilizanalgoritmos del tipolossy, que omiten algo de información pero que disminuyen considerablemente eltamaño del archivo original, el cual es el caso de los archivosMP3,MPG,jpeg, etc.
Los compresores basados enalgoritmos 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 modelolz77 es muy usado porque es fácil de implementar y es bastante eficiente.
En 1977Abraham Lempel yJacob Ziv presentaron su modelo de compresión basado endiccionario, 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 llamadolz77. 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 siguientebyte 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 1982James Storer yThomas Szymanski basados en el trabajo deLempel yZiv, presentaron su modelo, ellzss. 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 ochobits para representar un byte) de manera que elLZSS usa otro truco para mejorarlo: usa banderas (flags), que ocupan un solobit 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 ellzss es comúnmente llamadolz77, así que lo llamaremoslz77 de este punto en adelante, pero es importante recordar que también puede ser llamadoLZSS.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 delz77, 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”.
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.
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”
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 unabandera, de forma similar a uninterruptor 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 unapalabra clave. Una palabra clave es un grupo de bits (o bytes) que contienen alguna clase de información usada por elcompresor y eldescompresor. La otra salida posible delz77 es unliteral, la cual es simplemente un byte sin comprimir, de manera que la salida delz77 puede ser de tres formas:
Ahora, como ejemplo, veamos de nuevo nuestra cadena y una salidareal de un algoritmolz77:
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 unflujo de bits, porque es un flujo de símbolos de tamaño variable, y la unidad mínima es el bit.
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 laventana corrediza. La ventana corrediza es unbuffer 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 unbuffer con los datos en la posición actual y unbuffer con laventana 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 unbuffer, el cual contiene alarchivo. Luego solo debemos preocuparnos delpuntero 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 de8K necesitaremos 13 bits para el desplazamiento.
Otro aspecto que debemos elegir es eltamañ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 5bits.
Otro aspecto importante es la longitud mínima de una coincidencia. En nuestro caso hemos elegido utilizar 13bits en el desplazamiento y 5 en la longitud de la coincidencia, 18bits en total, de manera que una coincidencia debería ser de, por lo menos, 3bytes. Porque sicodificamos una coincidencia con dosbytes (16 bits) y utilizamos 18bits 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 5bits, 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.
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:
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 losdatos. Puede ser utilizado en una posibleinterfaz 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:
Como puede verse, los desplazamientos y tamaños son delongitud variable, y lasbanderas toman únicamente unbit, de manera que debemos usarbits en lugar debytes. Esto es muy importante en la mayoría de losalgoritmos decompresión.
La mayoría de operaciones trabajan conbytes y cuando se escribeinformación a unarchivo la unidad mínima es elbyte, entonces, para escribirbits hacemos un uso inteligente de algunasinstrucciones.
Para realizar esto podemos usarASM, o si no, puede ser implementado enC. Continuaremos las operaciones conbits en ASM. La idea principal es mantener unbyte y uncontador con losbits escritos, luego cuando tenemos 8bits, escribimos esebyte al archivo y comenzamos de nuevo con el siguientebyte. A continuación se presenta un ejemplo utilizando instrucciones deASM.
@@put_bits_loop:push cx ;el número de bits a escribirmov 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 alshr al,1 ;desplazamos al a la derecha, first bit in the carry flagxor ah, ah ;ah=0adc ah,0 ;ah 0 y el acarreomov bl, al ;guarda el byte de entradamov cl,_total_bits ;bits que hemos escritoshl ah, cl ;pone el bit en su posición desplazando a la izquierdaor bh, al ;pone el bit en el byte de salidamov _byte_out,bh ;guardarloinc _total_bits ;bits escritoscmp _total_bits,8 ;¿Tenemos que escribir todo el byte?jne @@no_write_byte ;nop E-)mov di,ptr_buffer ;el puntero al buffermov es:[di],bh ;el byte (es el segmento del buffer)inc di ;byte en el buffermov ptr_buffer,di ;guardado para la próxima vezinc bytes_writed ;cuando el buffer está lleno escribirmov _byte_out,0 ;a file or something like that so the next time is clear@@no_write_byte: ;lo hemos guardadopop cx ;¿más bits para escribir?dec cx ;sí, repetir todojnz @@put_bits_loop
Se presenta la rutinaputbits, los nombres de las variables se explican por sí solos pero aún y todo presentamos aquí una descripción:
Cuando se ingresa esta rutinacx debe tener el número debits a escribir, y_bite_in losbits a escribir. Hay que tener cuidado, después de ingresar elciclo hay que probar sicx es 0 porque si es cero y no se prueba escribirá unbit, luego haríacx - 1, lo que daría 255 con la consecuencia de escribir 255bits.
Recuerde:
Test cx, cxjz@@put_bits_end
Esta es laestructura (cómo son escritos losbits) para unbyte:
| 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únbits 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.
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:
Recordemos como trabajalz77, 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 esosbytes cuando uno se encuentra en dicha posición) una coincidencia,bytes que son iguales a losbytes en la posición actual; si se encuentran se escribe una palabra clave, de otra forma se escribe una literal para poder seguir comprimiendo.
La forma en que se buscan las coincidencias es la siguiente: se mantiene unpuntero a la posición actual. Al principio de cualquieriteración, secomputa el desplazamiento a laventana corrediza. Esto se puede hacer fácilmente obteniendo elpuntero a la posición actual y restándole el tamaño de laventana corrediza, en caso de que sea menos que cero (negativo) simplemente se ajusta a cero.
Digamos que tenemos unaventana corrediza de 4bytes de largo (así que gastamos dosbits 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"
DondePa es elpuntero albyte actual, y Pvc es elpuntero al inicio de laventana corrediza. Cuando se usanpunteros alarchivo de entrada completo, debemos cuidar el tamaño de laventana corrediza.
| Control de autoridades |
|
|---|
Datos:Q2679