Edición de «LZSS»

El [[Compresión de datos|algoritmo de compresión]] '''lz77''' (acrónimo de ''Abraham '''L'''empel'', ''Jacob '''Z'''iv'' y 19'''77''') 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 de archivo|tamaño del archivo]] original, el cual es el caso de los archivos [[MP3]], [[MPG]], [[jpeg]], etc.

== Características ==
Los compresores basados en [[algoritmo]]s 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 19'''77''' ''[[Abraham Lempel]]'' y ''[[Jacob Ziv]]'' presentaron su modelo de compresión basado en [[Codificación por diccionario|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 digital|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 de datos|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 informático|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 [[Longitud dimensional|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 [[codificar|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 [[interface|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 informático|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 de datos|compresión]].

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

Para realizar esto podemos usar [[Lenguaje ensamblador|ASM]], o si no, puede ser implementado en [[C (lenguaje de programación)|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 [[Lenguaje ensamblador|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'':

{| border="1" align="center"
|-----
| 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 datos|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 (informática)|archivo]] sin [[comprimir]].
* Se repite hasta que se ha [[descomprimido]] todo el [[Archivo (informática)|archivo]].
* Se lee un [[bit]] (''la bandera'').
* Si es 0:
** Se leen 8 ''bits'', se escriben al [[buffer de datos|buffer]] de salida (recordar que son un ''byte'' descomprimido) y se incrementa el [[Puntero (informática)|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 (informática)|archivo]] de entrada completo, debemos cuidar el tamaño de la ''ventana corrediza''.

== Véase también ==
* [[Sistema de compresión]]
* [[Algoritmo de compresión]]
* [[Compresión digital]]
* [[Algoritmo de compresión sin pérdida]]
* [[Algoritmo de compresión con pérdida]]
* [[7z]]
* [[Algoritmo de Huffman]]

== Enlaces externos ==
* [http://sites.google.com/site/compactamos/ Lista de manuales de algoritmos de compresión sin pérdida] {{Wayback|url=http://sites.google.com/site/compactamos/ |date=20090131111336 }} (''Español'')

{{Control de autoridades}}
[[Categoría:Siglas de informática]]
[[Categoría:Algoritmos de compresión]]