Sistemas de Representación y Procesamiento Automático del Conocimiento

Adquisición de los conceptos de codificación y compresión de la información electrónica.

Adquisición de los diferentes tipos de codificaciones para cada uno de los materiales multimedia existentes en la red.

Desde el principio de los tiempos la información se almacenó en distintos soportes, más o menos ineficientes a la hora localizar y recuperarla. La introducción de los medios electrónicos permitió una gestión de esta, más efectiva y eficiente. La capacidad de almacenamiento de los soportes electrónicos se ha visto desde entonces desbordada constantemente, por un lado por el crecimiento del volumen de información, y por el otro por la naturaleza cambiante de esta. Hace unos años una capacidad de almacenamiento de 1 GB resultaba una cantidad desorbitada y hoy es algo bastante normal como para que nos llame la atención.

Por ello, en muchos no es posible almacenar la información “tal como está”, sino que necesita algún tipo de compresión para optimizar el espacio disponible. La implantación y popularidad de Internet también impulsó la necesidad de métodos de compresión de datos, ya que el ancho de banda, al igual que el espacio de almacenamiento, es un bien que nunca parece ser suficiente. Dentro de este fenómeno, la aparición de información multimedia en la red, hay llevado a los especialistas a emplearse a fondo para mejorar constantemente los algoritmos de compresión de datos.

La compresión de datos se da de manera natural en el ser humano, generalmente mediante las abreviaturas. Por ejemplo, los títulos de revistas muchas veces aparecen abreviados y sin embargo tenemos la capacidad de determinar de que revista se trata. La siguiente es una abreviatura:

J AM SOC INF SCI TECH -> Journal of the American Society for Information Science and Technology (JASIS)

Este proceso se da de dos maneras. La primera es por la memoria, conocemos el JASIS por lo tanto sabemos que la abreviatura hace mención a dicho título. El segundo es por contexto, seguramente no tenemos la capacidad de conocer los miles de títulos que recoge el ISI, sin embargo, podemos determinar el título exacto en muchos casos, ya que las abreviaturas se determinan por contexto. Una J puede significar muchas palabras, pero en este caso se utilizará para “journal”. En caso de tener otra palabra con J se incluirá de manera más extendida. P.ej. la palabra (incluir ejemplo con J).

Ahora bien, por qué se eligió la abreviatura más corta para journal? Porque en el contexto de las revistas científicas, la palabra con J que más se repite es journal.

Lo mismo pasará con “bulletin” (B) o con otras palabras como science (SCI).

Este ejemplo es ilustrativo del principio general utilizado en la compresión de datos: la redundancia informativa. Si a un elemento dado (p.ej. journal) que se repite muchas veces lo representamos con un conjunto de caracteres menor, estaremos ahorrando espacio y por tanto optimizando su almacenamiento y transferencia.

La compresión de datos consiste en crear ficheros más pequeños que los originales mediante la predicción de los bytes más frecuentes. Esto involucra al menos dos tareas diferentes: predecir la probabilidad de que aparezca una determinada entrada y asignarle un código.

Existen dos grandes familias de algoritmos de compresión: sin pérdida (lossless compression) y con pérdida de datos (lossy compression). En el primer caso, al descomprimir se consigue idénticos datos que en origen (bit a bit), mientras que en el segundo no es así, los datos son aproximadamente parecidos al original. El primer tipo de compresión se aplica generalmente a textos y ficheros binarios, mientras que el segundo generalmente se aplica a imágenes, video y sonido.

A la hora de utilizar un algoritmo de compresión determinado, es necesario tomar dos decisiones importantes. La primera consiste en determinar el nivel de compresión, que puede ser a nivel de caracteres o nivel de palabras. Si trabajamos con frecuencia de caracteres o grupos de caracteres, tendremos la ventaja de que con una pequeña serie de elementos podremos representar cualquier tipo de texto. En cambio, si trabajamos con frecuencias de palabras deberemos manejar listas que incluyan decenas de miles de palabras. Sin embargo, en este último caso, el algoritmo resultante será más rápido de ejecutar que uno realizado a nivel de caracteres.

La segunda decisión consiste en elegir el tipo de modelo de datos que será usado. Básicamente, todas las técnicas de compresión están basadas en la distribución estadística de los objetos a ser comprimidos, ya sean caracteres o palabras. El concepto básico es que los códigos de compresión cortos y eficientes deben ser utilizados para los símbolos que aparecen frecuentemente, mientras que una compresión menos eficiente puede ser tolerada por los símbolos que aparecen más raramente.

Hay dos grandes tipos de modelos de datos, los modelos estáticos y los adaptativos. En el caso del modelo estático, se construye examinando una pequeña muestra de texto y creando las tablas estadísticas correspondientes a esta muestra. Posteriormente este modelo se aplica a la totalidad del texto a comprimir.

En el caso del modelo adaptativo, se comienza con una distribución estadística a priori, pero esta se va modificando dinámicamente con cada carácter o palabra codificada. A medida que se comprime más texto, el modelo se adapta más satisfactoriamente a la totalidad del texto.

Existe un tercer tipo de modelo, el semi estático, y consiste en un compromiso entre los dos primeros modelos.

Los diferentes modelos de datos tienen diferentes efectos en la compresión. Primero, los modelos estáticos necesitan de poco procesamiento de máquina y generalmente realizan una compresión y descompresión rápida. Segundo, los modelos adaptativos se aproximan más fielmente a la estructura del texto, por lo que generan una mayor compresión. Tercero, debido a que el funcionamiento de los modelos adaptativos depende del análisis dinámico de la totalidad texto comprimido, para descomprimir una determinada parte será necesario descomprimir desde el principio del fichero. En caso contrario, no podríamos adaptar el algoritmo de descompresión para “comprender” la parte deseada.

La compresión adaptativa conlleva un pequeño dilema. Funciona de manera más eficiente cuando se codifican ficheros relativamente grandes, pero el acceso aleatorio al fichero comprimido, un proceso sumamente importante en recuperación de la información, es imposible. Una solución de compromiso para este problema consiste en la introducción de puntos de sincronización, donde el algoritmo adaptativo se para y vuelve a iniciarse. Si bien esta solución no permite un acceso aleatorio real, al menos evita decodificar el fichero desde el principio.

Existen tres ejemplos de codificación utilizados para comprimir texto: los códigos Huffman, los códigos Ziv-Lempel, y los códigos aritméticos.

Es el más viejo de estos métodos. Fue desarrollado a principios de los años ’50 por David Huffman y es lo suficientemente bueno como para siga aún siendo usado en nuestros días (Huffman 1952). Es un código estático, por lo que su capacidad de compresión no es muy alta ya que codifica, de forma algo tosca, los caracteres mediante cinco bits mientras que otros métodos adaptativos lo hacen con menos de tres.

El modelo en el que se basa el código Huffman es la frecuencia de distribución de los símbolos a ser codificados, tanto palabras como caracteres, mediante la construcción de un árbol binario recursivo. Inicialmente cada símbolo es considerado como un árbol binario por separado. Los dos árboles con la frecuencia más baja son seleccionados y combinados en un nuevo árbol binario cuya frecuencia correspondiente es la suma de las frecuencias de los dos anteriores. Este proceso se repite hasta agrupar todos los árboles formando uno solo. A cada rama del árbol binario se le asigna un 1 o 0, de forma tal que cada símbolo puede ser descrito por una sucesión de 0 y 1 dependiendo de la rama del árbol en la que se encuentre. El código Huffman es un código de longitud variable, porque los símbolos que más se repiten son codificados con menos bits que los que menos se repiten.

Este código, que también se conoce como de Lempel-Ziv, se basa en un principio diferente al anterior ya que asume que determinadas frases se repetirá en el texto. Identifica cada segmento de texto cada vez que aparece y simplemente cada vez que aparece nuevamente dicho segmento lo enlaza (mediante un puntero) con el original en lugar de repetirlo. Es por lo tanto un modelo adaptativo que funciona mejor cuanto más texto se codifica, ya que ocupa menos lugar un puntero que el segmento al que apunto. A más texto, más punteros. A más punteros, más compresión. Con grandes volúmenes de texto se consigue unas tasas de compresión mucho mayores con Zip-Lempel que con Huffman.

Este algoritmo de compresión tiene su raíz en el trabajo de Jacob Ziv y Abraham Lempel, quienes en 1977 publicaron un artículo en el sentaron las bases del método (Ziv Lempel 1977), y al que agregaron al año siguiente otro más que trataba sobre una variación de la compresión basada en diccionarios (Ziv Lempel 1978). Estos algoritmos son conocidos como LZ77 y LZ78. En 1984, Terry Welch realizó una modificación del LZ78 y desarrolló el ampliamente conocido LZW.

Para la completar satisfactoriamente la presente práctica, el alumno deberá aplicar el código Huffman al siguiente texto, el primer párrafo de El Quijote:

"En un lugar de la Mancha, de cuyo nombre no quiero acordarme, no ha mucho tiempo que vivía un hidalgo de los de lanza en astillero, adarga antigua, rocín flaco y galgo corredor. Una olla de algo más vaca que carnero, salpicón las más noches, duelos y quebrantos los sábados, lentejas los viernes, algún palomino de añadidura los domingos, consumían las tres partes de su hacienda."

Luego, deberá calcular la tasa de compresión lograda, restando el volumen de bits del texto en código ASCII (8 bits por caracter) al volumen de bits del texto comprimido.

Huffman, David. A method for the construction of minimum redundancy codes. Proceedings of IRE. 40(9):1098-1101, 1952.

Ziv, J. & A. Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory. 23:337-343, 1977.

Ziv, J. & A. Lempel. Compression of individual sequences via variable rate coding . IEEE Transactions on Information Theory. 24:530-536, 1978.