El Algoritmo Lempel-Ziv
Fue ideado por Jacob Ziv y Abraham Lempel, y publicado en el IEEE Transactions on Information Theory, vol. IT-23, No 3 de Mayo de 1977, si bien ya había sido presentado anteriormente en el IEEE International Symposium on Information Theory celebrado en Ronneby, Suecia, en Junio de 1976.
Desde entonces recibe el nombre de compresión Lempel-Ziv o, para abreviar, LZ.
Existe una variante de LZ, denominada LZW (Lempel-Ziv-Welch), que se ha hecho muy famosa por ser la que se utiliza para comprimir en el formato de imágenes GIF. Se trata de una modificación de LZ que, a costa de un menor ratio de compresión, ofrece mejoras en cuanto a velocidad y uso de memoria, lo que hizo que se usara en los modems que soportan el protocolo V42bis. Es también el algoritmo empleado en el programa compress. Sin embargo, a pesar de su atractivo, no lo trataremos aquí porque, desgraciadamente, se trata de un algoritmo sujeto a patentes. Pese a que la información sobre su funcionamiento se encuentra accesible líbremente ("A Technique for High-Performance Data Compression'', Terry A. Welch, IEEE Computer, Junio 1984, páginas 8-19), su funcionamiento en cambio no lo es. Contrariamente a lo que se podría pensar, la patente no es de Terry Welch, que durante 7 años, y hasta que en 1983 se marchó a DEC, estuvo trabajando en el Sperry Research Center de Sudbury, Massachusetts. Desde el principio fue Sperry el propietario de la patente, aunque nunca trató de sacarle partido. Al menos hasta que en 1986 se unió a Burroughs para formar Unisys. Fue entonces cuando empezaron a utilizarla contra los fabricantes de modems. Actualmente la patente pertenece a Unisys, que legalmente puede cobrar por su uso, como ya hizo con Compuserve, con la que llegó a un acuerdo para crear una licencia para productores de software sobre el formato GIF, que antes era libre. No obstante lo dicho, Unisys al final decidió no cobrar derechos de patentes por código libre que se hubiera publicado con anterioridad a la decisión de hacer efectiva la patente, y por ello hay una librería -giflib- que se puede usar para código libre sin pagar patentes; la librería está ahora mantenida por Eric S. Raymond: http://www.ccil.org/ esr/giflib.
La idea en que se basa LZ resulta simple, visto todo lo que le hemos pedido al algoritmo en la sección anterior: básicamente busca secuencias repetidas dentro de los datos, y cada vez que encuentra una de ellas la reemplaza por un puntero a la zona en la que comienza la primera secuencia, más la longitud que se debe tomar a partir de esa posición. En caso de que no haya repeticiones, se emite la secuencia como un literal.
Lo más importante, y lo que conforma el núcleo de la idea, es identificar lo que Lempel-Ziv llaman extensión reproducible de una cadena dentro de otra y que difiere un tanto de lo que coloquialmente llamamos "repeticiones''.
Veámoslo con el mismo ejemplo del artículo original de los autores, pero desde un punto de vista más descriptivo y menos matemático para facilitar un poco su lectura: supongamos que tenemos la secuencia S=00101011. Pongámoslo tabulado, 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 1 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 secuncia 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 Kbytes 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 secuncia, 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 despplazado 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 cmo 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 secuancia 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 tambin 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 y 9).
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.
Tutoriales
