CÓDIGO LEMPEL - ZIV
Objetivos:
- Aprender acerca del código de compresión para poder utilizar menos espacio de almacenamiento y transmitir archivos más rápidamente, ahorrando así tiempo y costo.
- Desarrollar nuevas técnicas que nos sean útiles y faciliten nuestro aprendizaje en la teoría de la información y codificación.
- Analizar la metodología y procedimiento utilizado por este código para ejecutarlo correctamente.
HISTORIA
Los
creadores de este clásico algoritmo de compresión fueron Abraham Lempel y Jacob Ziv en el año 1977,
nacía el LZ77.
Un
año después crearon el compresor de imágenes o cualquier dato que fuera binario
llamado LZ78. En 1984, un ingeniero de la empresa Unisys llamado Terry Welch
modificó el código para implementarlo en los controladores de disco duro dando
su apellido al algoritmo LZW.
El compresor LZW es un sistema de
compresión/descompresión muy rápido que se basa en la multiplicidad de los
caracteres en la cadena que se va a codificar. A partir de la cadena creaba
unos patrones que los integraba en un diccionario.
El LZW trabaja con bits y no con bytes,
lo que consigue gran compatibilidad a la hora de procesar datos. Este formato
es muy utilizado en la comprensión de imágenes
TIFF o GIF. Por otra parte, el PNG utiliza el LZ77 por tanto es totalmente
libre.
COMPRESIÓN DE DATOS
La
compresión es un caso particular de la codificación cuya característica
principal es que el código resultante tiene menor tamaño que el original.
La
compresión de datos se basa fundamentalmente en buscar repeticiones en series
de datos para después almacenar solo el dato junto al número de veces que se
repite, para ello se utilizan algoritmos de compresión como el de Lempel Ziv .
El objetivo
de la compresión es siempre reducir el tamaño de la información, intentando que
esta reducción de tamaño no afecte al contenido. No obstante, la reducción de
datos puede afectar o no a la calidad de la información:
- Compresión sin pérdidas: en esta compresión los datos antes y después de comprimirlos son exactos, pero una mayor compresión implica más tiempo de proceso.
- Compresión con pérdidas: puede eliminar datos para reducir aún más el tamaño, con lo que se suele reducir la calidad. En este tipo de compresión no se obtiene la señal original una vez realizada la compresión. Se utiliza principalmente en la compresión de imágenes, videos y sonido.
Son técnicas que no requieren conocer de la probabilidad de aparición de cada símbolo. Por ello sera útiles en aquellas aplicaciones donde no sea posible conocer las probabilidades de los símbolos. Estos códigos se basan en algunas cadenas podrían ser sustituidas por una palabra de un nuevo código que ocupe menos espacio.Para ello tanto el emisor como el receptor construirán tablas que contendrán toda la información necesaria para llevar a cabo la compresión y descompresión. Son códigos eficientes cuando se utilizan en ficheros y mensajes grandes.
EJEMPLO: Otra forma de realizar el código de Lempel Ziv.
Tenemos una secuencia S=00101011
Supongamos también que los tres primeros elementos, 001, ya han sido codificados; en este momento nos da igual que hayan sido comprimidos o tomados como literales. Posteriormente nos ocuparemos de ese aspecto, pero ahora tenemos que codificar lo que sigue: 01011. Llamaremos a la secuencia ya codificada secuencia 1 y a la que está siendo codificada ahora secuencia 2.
La extensión reproducible de Ls, empezando a buscar en la parte ya "codificada" (las n-Ls primeras posiciones del buffer), aparece en gris.
Aquí, la extensión periódica de los elementos a partir de la posición 10 se haya en la posición 8. Empezando tanto por 8 como por 10 encontramos la secuencia 010, así que S2 es la parte que se repite del comienzo de Ls, 010 (posiciones 10 a 12), más el siguiente elemento, 2, que ya no se repite (posición 13). Luego S2=0102, que se codifica como C2=732. Desplazamos 4 posiciones a la izquierda, que es lo que mide S2, y la "repetición'' de la secuencia Ls se encuentra en la zona marcada en la figura 4.
Comprobemos que la secuencia comprimida C=821732672280 puede decodificarse unívocamente dando como resultado la secuencia original S=001010210210212021021200. Es importante darse cuenta de que, si bien la longitud de las subcadenas no es fija (aunque sí limitada), la de las palabras código sí lo es: en este caso, 3 caracteres. Esto permite separar a partir de C palabra código de palabra código de forma simple. Incluso dentro de una misma palabra código, los tamaños asignados a una u otra función (posición a partir de la que empieza una repetición, longitud de esta y elemento siguiente a ella), son también fijos, y fácilmente separables.
La primera palabra que se lee es '021'. El '0' sirve de puntero en el buffer, y lo llamaremos "p''. Se debe leer el carácter que está en la posición p+1, luego se lee el de la posición 1. Como inicialmente el buffer estaba puesto a 0, no sorprende que lo que encontremos en la posición 1 sea un '0'. Tal y como está el buffer, se desplazan todos sus elementos una posición hacia la izquierda, y en el hueco que queda a la derecha se introduce el carácter leído con anterioridad en esa posición 1. El segundo carácter de la palabra código es un '2'. Ello indica que la operación anterior de leer y desplazar se debe hacer dos veces, por lo que la repetimos: nuevamente se lee la posición 1.
EJEMPLO: Otra forma de realizar el código de Lempel Ziv.
Tenemos una secuencia S=00101011
Se
los tabula, de forma que podamos hacer referencia a cada elemento de la
secuencia fijándonos en el orden en el que aparece dentro de esta.
La
primero fila de la figura indica la posición dentro del buffer y la segunda su
contenido. Consideraremos la posición más a la izquierda como posición 1.
Supongamos también que los tres primeros elementos, 001, ya han sido codificados; en este momento nos da igual que hayan sido comprimidos o tomados como literales. Posteriormente nos ocuparemos de ese aspecto, pero ahora tenemos que codificar lo que sigue: 01011. Llamaremos a la secuencia ya codificada secuencia 1 y a la que está siendo codificada ahora secuencia 2.
Si
a una persona normal le pedimos que encuentre en 01011 una secuencia que esté
repetida a partir de lo que ya hemos codificado (001), nos dirá que los dos
primeros elementos de la secuencia a codificar (posiciones 4 y 5 dentro del
buffer) son iguales a los dos últimos de 001 (posiciones 2 y 3), y que ahí hay
una repetición. Y tendrá razón, pero la genialidad de LZ está en darse cuenta
de que se puede ir más allá y utilizar la propia secuencia a codificar como
lugar donde seguir buscando repeticiones. ¡Eso a pesar de que aún no la hemos
codificado!
Veámoslo:
la secuencia 2 empieza por 0101 (posiciones 4 a 7). Si empezamos a mirar en lo
que ya hemos codificado, la secuencia 1, tenemos que finaliza en 01, pero si
seguimos entrando en la secuencia 2 ahora veremos que empieza por 01. Si
juntamos el final de la secuencia 1 con el principio de la secuencia 2, tenemos
0101, que es igual al comienzo de la secuencia a codificar o secuencia 2. Es
decir: los elementos 4, 5, 6 y 7 de la secuencia total son una "repetición''
de los elementos 2, 3, 4 y 5. Por tanto se codificarán como un puntero a la
posición número 2 más una longitud de 4. Luego veremos en un ejemplo cómo esto,
aunque parezca imposible, funciona a la hora de decodificar.
La
codificación se lleva a cabo introduciendo los datos dentro de un buffer de una
longitud prefijada, n, dentro del cual se van buscando subcadenas ya repetidas
haciendo uso del método que acabamos de explicar. En gzip, la longitud máxima
de esas subcadenas, Ls, es de 258 bytes. Si una cadena no ocurrió dentro de los
32 Kbyte anteriores, se emite literalmente.
Un
ejemplo ayudará a ver cómo se llevan a cabo la compresión y la descompresión.
Utilizaremos una simplificación de uno propuesto por los creadores del
algoritmo.
Supongamos
que queremos codificar la secuencia:
S=001010210210212021021200...
Por
razones didácticas (aunque no prácticas) usaremos un buffer de longitud n=18 y
una longitud máxima de cadena Ls de 9. Inicialmente se llenan las n-Ls
posiciones del buffer con ceros, y las Ls restantes con los primeros datos de
la secuencia, con lo que el buffer en la posición inicial quedaría como se ve
en la figura 2.
La extensión reproducible de Ls, empezando a buscar en la parte ya "codificada" (las n-Ls primeras posiciones del buffer), aparece en gris.
La
primera subcadena a codificar se formará a partir de esa extensión
reproducible, 00, seguida del siguiente elemento que ya no está repetido 1,
luego S1=001.
La
palabra código que representa a esa subcadena será, por convenio y en ese
orden, el puntero al comienzo de la repetición menos 1, seguido de la longitud
de la repetición, seguido del elemento final, que no entraba en la repetición.
Es decir, para este caso: C1=021.
Puesto
que S1 tenía longitud 3, todo el contenido del buffer es desplazado hacia la
izquierda 3 posiciones. En esta situación 2 seguiremos, como siempre, a partir
de la posición 10, buscando la extensión reproducible de 0102... La encontramos
en la figura 3.
Aquí, la extensión periódica de los elementos a partir de la posición 10 se haya en la posición 8. Empezando tanto por 8 como por 10 encontramos la secuencia 010, así que S2 es la parte que se repite del comienzo de Ls, 010 (posiciones 10 a 12), más el siguiente elemento, 2, que ya no se repite (posición 13). Luego S2=0102, que se codifica como C2=732. Desplazamos 4 posiciones a la izquierda, que es lo que mide S2, y la "repetición'' de la secuencia Ls se encuentra en la zona marcada en la figura 4.
En ella se
observa con claridad que, dado que Ls empieza por 10, había una repetición en
las posiciones 5 y 6, que también son 10, que sin embargo no hemos marcado en
negrita dentro de la figura. Esto es debido a que la secuencia formada por las
posiciones 5 y 6, si bien representa una repetición de lo que aparece en Ls, no
se trata de su extensión periódica ya que tiene longitud 2, mientras que la
coloreada en la figura tiene longitud mayor: 7. Por ello S3=10210212 y C3=672.
Por último, tras desplazar las 8 posiciones que ocupa S3, se obtiene
S4=021021200 y C4=280 (figura 5).
Comprobemos que la secuencia comprimida C=821732672280 puede decodificarse unívocamente dando como resultado la secuencia original S=001010210210212021021200. Es importante darse cuenta de que, si bien la longitud de las subcadenas no es fija (aunque sí limitada), la de las palabras código sí lo es: en este caso, 3 caracteres. Esto permite separar a partir de C palabra código de palabra código de forma simple. Incluso dentro de una misma palabra código, los tamaños asignados a una u otra función (posición a partir de la que empieza una repetición, longitud de esta y elemento siguiente a ella), son también fijos, y fácilmente separables.
La
longitud de cada uno de estos campos, y de la palabra código como suma de todos
ellos, está directamente relacionada con el tamaño del buffer, n, y con el de
la máxima subcadena, Ls. Más detalles se pueden encontrar en el artículo de
Lempel-Ziv.
Para
descomprimir se emplea un buffer de longitud n-Ls donde se van guardando los
símbolos descodificados. Inicialmente el buffer se pone todo a 0.
Seguidamente
se van leyendo palabras código, lo cual puede hacerse sin especiales cuidados
al tener todas la misma longitud. También en este caso ilustraremos la
descompresión paso por paso. El primero se ilustra en la figura 6.
La primera palabra que se lee es '021'. El '0' sirve de puntero en el buffer, y lo llamaremos "p''. Se debe leer el carácter que está en la posición p+1, luego se lee el de la posición 1. Como inicialmente el buffer estaba puesto a 0, no sorprende que lo que encontremos en la posición 1 sea un '0'. Tal y como está el buffer, se desplazan todos sus elementos una posición hacia la izquierda, y en el hueco que queda a la derecha se introduce el carácter leído con anterioridad en esa posición 1. El segundo carácter de la palabra código es un '2'. Ello indica que la operación anterior de leer y desplazar se debe hacer dos veces, por lo que la repetimos: nuevamente se lee la posición 1.
Aunque
la posición es la misma, el dato leído no tiene por qué serlo, ya que el buffer
se desplazó hacia la izquierda. En este caso volvemos a tener un '0', y el
buffer tiene el mismo aspecto que antes. Al segundo elemento de las palabras
código lo llamaremos a partir de ahora "n''. Puesto que ya hemos hecho dos
veces la operación, tantas como indicaba el n de la palabra código que estamos
decodificando, ahora se desplaza una vez más a la izquierda, y en el hueco que
ha aparecido se introduce el tercer carácter de la palabra código (a partir de
ahora "c''), sin modificar: el '1'.
Al
final de todas las figuras se resalta en negrita la parte del buffer que
corresponde a la descodificación de la palabra código. Evidentemente, este
tramo se encuentra siempre al final del buffer, y su longitud es bien simple de
calcular: n+1.
La
siguiente palabra a decodificar es 732. Como antes, y esta vez por 3 veces, se
guarda el carácter de la posición 7+1 y se coloca a la derecha del buffer tras
desplazarlo. El último carácter que se introduce por la derecha nos viene dado
en la palabra código: ahora es un '2' (figura 7).
El
proceso con las dos palabras código restantes es exactamente igual, y no
requieren mayor explicación. No obstante, se ofrecen las figuras
correspondientes para que el lector interesado pueda seguir el proceso hasta el
final (figuras 8 ).
Extrayendo
los tramos en negrita del final de cada paso, obtenemos 001, 0102, 10210212 y
021021200, que juntos vuelven a conformar la secuencia original S.
VÍDEO EJEMPLO CODIFICACIÓN LEMPEL-ZIV
INTEGRANTES
http://cronograma-lempel-ziv.blogspot.com/
BIBLIOGRAFIA:
- Guanopatín Cristian
- Loachamín Robinson
- Rodríguez Angélica
http://cronograma-lempel-ziv.blogspot.com/
