Introducción a la compresión de datos: Lempel-Ziv, Gzip

A pesar de tan rimbonbante epiteto, el hecho de que estos c�digos sean "�ptimos" no quiere decir necesariamente que sean de utilidad en todos los casos. Todo depende de cu�l sea el caso concreto en el que pensamos utilizarlos. En el contexto de un sistema operativo, lo que se busca habitualmente es comprimir ficheros o salidas de otros programas que se quieren guardar haciendo uso del menor espacio de almacenamiento posible. Pero no es lo mismo comprimir un fichero de texto que guarda el cap�tulo de una novela, que otro que guarda el c�digo fuente de un programa (que, en general, tiene m�s redundancia) o un tercero que, en oposici�n a los archivos de texto, podemos llamar "binario". Incluso entre los archivos "binarios", unos permiten mucha mayor compresi�n que otros.

Luego en esta necesidad concreta estamos buscando un c�digo que se adapte bien a muchos tipos de fuentes, no conocidas -ni mucho menos, caracterizadas- a priori. Y es aqu� donde la codificaci�n Huffman, a pesar de ser "�ptima", como todas las que se basan en asignar palabras c�digo cortas a las secuencias m�s probables, sufre de graves inconvenientes:

  • En primer lugar, en los casos que nos ocupan, la �nica forma de conocer qu� secuencias son m�s probables es examinar de principio a fin aquello que se quiere comprimir. Eso obliga a dar dos pasadas por los datos: una para encontrar las secuencias que m�s se repiten (y con ellas elaborar el c�digo), m�s una segunda para codificar la fuente con el c�digo as� establecido. Este inconveniente es, a su vez, causa de:
    • P�rdida de velocidad en la compresi�n. Lo ideal ser�a poder ir comprimiendo seg�n van llegando los datos para que empecemos a tener resultados de forma inmediata.
    • Imposibilidad de utilizar el compresor como un filtro. La necesidad de dar dos pasadas por los datos se puede satisfacer cuando se est� actuando sobre ficheros, en los que se puede aplicar la operaci�n lseek para moverse a la posici�n deseada del mismo. Pero es muy com�n querer comprimir los datos que se obtienen a trav�s de una tuber�a, como en:
      cat connexiones.log | grep sitio_malo | gzip > sitio_malo.gz
      donde la operaci�n lseek no tiene sentido. Aunque ejemplificado desde el punto de vista del compresor, est� claro que esta limitaci�n afecta, igualmente, al descompresor.
  • Con la asignaci�n de palabras c�digo a secuencias hay que hacerse en estos casos de codificaci�n de fuentes gen�ricas la pregunta de cu�ndo parar. Se pueden establecer y almacenar frecuencias de bytes, y se tendr� una tabla de 256 entradas, desde los m�s frecuentes a los m�s raros. Pero eso no basta: si estamos comprimiendo un texto, dependiendo del idioma en que est� escrito, encontramos que es m�s com�n que unas letras vayan acompa�adas de otras. En espa�ol, por ejemplo, es muy raro encontrar las secuencias "ts", "aa" o "bq". En otros idiomas, o en ficheros binarios, pueden darse m�s unas agrupaciones y menos otras. Si estas agrupaciones se tienen en cuenta en el c�digo, se obtendr� un mayor ratio de compresi�n, pero nos encontramos con una tabla de 256x256 = 65536 entradas. En el ejemplo que presentaremos posteriormente, la codificaci�n Lempel Ziv es capaz de reconocer una secuencia redundante de 8 caracteres y codificarla apropiadamente. Si pretendi�ramos que los c�digos Huffman fueran capaces de hacer esto, habr�a sido necesario construir una tabla que computara las frecuencias de secuencias de 8 caracteres. Esa tabla por s� sola, sin tener en cuenta las que almacenar�an frecuencias de agrupaciones m�s peque�as de caracteres, tendr�a 18.446.744.073.709.551.616 entradas.
  • Suponiendo que fueran aceptables la p�rdida en velocidad, los problemas con las tuber�as y los derivados del tama�o de las tablas, a�n queda otro inconveniente por afrontar: dado que podemos encontrarnos con fuentes de lo m�s variopintas y que por ello no es posible tener a priori c�digos adaptados a cada una de ellas, conocidos en los dos extremos de la comunicaci�n o en compresor y descompresor, no s�lo es necesario guardar o transmitir la secuencia codificada, sino tambi�n el propio c�digo necesario para descodificarla. Dependiendo de lo voluminoso que sea este (y por lo visto en el punto anterior, puede llegar a ser muy voluminosos), podr�a darse el caso de que juntando �mbos sumandos, datos m�s c�digo ocupen m�s que los datos originales sin comprimir.

Con este modelo de compresi�n s�lo se pueden ofrecer soluciones parciales y poco eficientes a esta serie de problemas. Para el caso de los filtros no quedar�a m�s remedio que guardar lo que le llega al compresor/descompresor por su entrada estandard en un fichero intermedio, y despu�s comprimir ese fichero, lo cual, dependiendo de lo cuantiosa que sea la salida del filtro, podr�a implicar la imposibilidad de llevar a cabo la operaci�n si en el disco duro no cupieran, simultaneamente, el fichero temporal sin comprimir m�s la salida del gzip, ya comprimida. Por la misma raz�n de espacio, la soluci�n de guardar TODOS los datos en memoria durante la primera pasada y volver sobre ellos en la segunda soluciona el problema de las tuber�as pero es de dudosa utilidad, a menos que se cuente con memoria infinita.

Para evitar tener que guardar o transmitir datos comprimidos y c�digo necesario para descomprimirlos, se podr�a tratar de hacer un estudio de muchas fuentes y en funci�n de �l sacar un �nico c�digo que se aplicara a todas las fuentes. Evidentemente, eso ser�a poco eficiente. Por ser fruto del c�lculo de una "media", probablemente no ser�a �ptimo para ninguna fuente. Pero, al fin y al cabo, esta es la soluci�n adoptada, por ejemplo, en el c�digo Morse, que este a�o desaparece del mundo de la navegaci�n tras m�s de cien salvando vidas. En �l, la asignaci�n de puntos y rayas a las letras no es aleatoria: el punto se hace corresponder con la letra ``e'', la m�s frecuente en el idioma ingl�s. E igualmente con el resto de las letras: todas ellas codificadas en funci�n de su frecuencia en el susodicho idioma. Mientras nos mantengamos en �l, es razonablemente eficiente, pero en cuanto la transmisi�n se lleve a cabo en otro idioma, es probable que las letras m�s usadas sean tambi�n las que tienen un c�digo de puntos y rayas m�s largo.

La p�rdida de velocidad no tiene soluci�n, ni siquiera una no �ptima, si no se quiere usar un c�digo gen�rico. Las dos pasadas hay que darlas, y hasta que no se haya llevado a cabo la primera, no es posible empezar a comprimir en la segunda.

En resumen, hace falta alg�n algoritmo o tipo de codificaci�n que sea capaz de adaptarse a su fuente, que a partir de ella genere el c�digo m�s acertado posible y lo transmita junto con la fuente sin llegar a hacer in�til la compresi�n por el overhead que implica enviar el c�digo junto con los datos, y que adem�s empiece a hacer todo esto desde el primer momento en el que le van llegando los datos al compresor o descompresor, sin tener que llegar a conocer todo el mensaje.

Parece complicado, porque adem�s implica un cierto (y atractivo) sentido de inteligencia por parte del codificador, que va aprendiendo de su fuente y localizando secuencias que tienen m�s redundancia.

A continuaci�n presentaremos un algoritmo que cumple con esas restrictivas condiciones. Evidentemente lo hace al precio de alejarse algo m�s del l�mite impuesto por la entrop�a. En ese sentido, los c�digos Huffman comprimir�an mejor, pero esto demuestra que un algoritmo que sea m�s eficiente en un sentido puede resultar poco pr�ctico en conjunto.

COMPARTE ESTE ARTÍCULO

COMPARTIR EN FACEBOOK
COMPARTIR EN TWITTER
COMPARTIR EN LINKEDIN
COMPARTIR EN WHATSAPP
ARTÍCULO ANTERIOR

SIGUIENTE ARTÍCULO