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

ENVIAR A UN AMIGO
COMPARTIR EN FACEBOOK
COMPARTIR EN TWITTER
COMPARTIR EN GOOGLE +
ARTÍCULO ANTERIOR

SIGUIENTE ARTÍCULO

¡SÉ EL PRIMERO EN COMENTAR!
Conéctate o Regístrate para dejar tu comentario.