Tipos de algoritmos de compresión y sus características

A la hora de hablar de compresión hay que tener presentes dos conceptos:

1. Redundancia: Datos que son repetitivos o previsibles 2. Entropía: La información nueva o esencial que se define como la diferencia entre la

cantidad total de datos de un mensaje y su redundancia.

La información que transmiten los datos puede ser de tres tipos:

1. Redundante: información repetitiva o predecible. 2. Irrelevante: información que no podemos apreciar y cuya eliminación por tanto no

afecta al contenido del mensaje. Por ejemplo, si las frecuencias que es capaz de captar el oído humano están entre 16/20 Hz y 16.000/20.000 Hz s, serían irrelevantes aquellas frecuencias que estuvieran por debajo o por encima de estos valores.

3. Básica: la relevante. La que no es ni redundante ni irrelevante. La que debe ser transmitida para que se pueda reconstruir la señal.

Teniendo en cuenta estos tres tipos de información, se establecen tres tipologías de compresión de la información:

1. Sin pérdidas reales: es decir, transmitiendo toda la entropía del mensaje (toda la información básica e irrelevante, pero eliminando la redundante).

2. Subjetivamente sin pérdidas: es decir, además de eliminar la información redundante se elimina también la irrelevante.

3. Subjetivamente con pérdidas: se elimina cierta cantidad de información básica, por lo que el mensaje se reconstruirá con errores perceptibles pero tolerables (por ejemplo: la videoconferencia).

Compresión sin pérdidas y compresión con pérdidas

En realidad, hay fundamentalmente dos "estilos" diferente de compresión de datos: con pérdidas y sin pérdidas. La compresión sin pérdidas implica una transformación de la representación de un conjunto de datos, entonces es posible reproducir exactamente el mismo conjunto de datos originales al realizar la transformación por descompresión.

La compresión con pérdidas es una representación que le permite reproducir algo "bastante parecido" al conjunto de datos original. Una ventaja de las técnicas con pérdidas es que pueden producir con frecuencia representaciones de datos más compactas que las técnicas de compresión sin pérdidas.

Hay que tener en cuenta que una vez realizada la compresión, no se puede obtener la señal original, aunque sí una aproximación cuya semejanza con la original dependerá del tipo de compresión. Más a menudo, las técnicas de compresión con pérdidas se utilizan para imágenes, archivos de audio y video. La compresión con pérdidas podría ser la adecuada en aquellas áreas en las que los observadores humanos no perciben un patrón de bits literal de una imagen o sonido digital, sino que características gestálticas generales de la imagen/sonido subyacente.

Desde el punto de vista de los datos "normales", la compresión con pérdidas no es una opción. No queremos un programa que haga "prácticamente lo mismo" que el que escribimos. No queremos una base de datos que contenga "prácticamente el mismo" tipo de información que la que incluimos.

Compresión de espacios en blanco

Generalmente, la compresión de espacios en blanco puede caracterizarse como "eliminar lo que no nos interesa". Aunque esta técnica es una técnica de compresión con pérdidas, es útil para muchos tipos de representaciones de datos que encontramos en el mundo real. Por ejemplo, aunque HTML es mucho más legible en un editor de textos si se agregan espacios de indentación o verticales, ninguno de los "espacios en blanco" debería hacer ninguna diferencia en la representación del documento HTML por un navegador web. Si usted sabe que un documento HTML está destinado solo para un navegador web (o para un robot/araña), entonces podría ser una buena idea sacar todos los espacios en blanco para transferirlos más rápidamente y ocupar menos espacio de almacenamiento. En realidad, lo que eliminamos en la compresión de espacios en blanco, nunca tuvo un propósito funcional para comenzar.

La compresión de espacios en blanco es extremadamente "barato" de realizar. Es simplemente cuestión de leer una transmisión de datos y de excluir algunos valores específicos desde la transmisión de salida. En muchos casos, no se incluye el paso de "descompresión". Pero incluso donde nos gustaría recrear algo parecido al original en algún lugar por debajo de la transmisión de datos, eso requeriría poco en términos de CPU o de memoria. Lo que reproducimos puede o no ser exactamente con lo que empezamos, según qué normas y restricciones se incluían en el original. Una página HTML escrita por un humano en un editor de texto probablemente tendrá el espacio que es idiosincrático. Una vez más, a menudo, las herramientas automatizadas producen una indentación "razonable" y espacio para HTML.

Codificación de duración

La codificación de duración (RLE) es la técnica de compresión sin pérdidas más utilizada y simple. Al igual que la compresión de espacios en blanco, es "económica", especialmente para decodificar. La idea de trasfondo es que muchas representaciones de datos consisten de grandes series de bytes repetidos.

Si los bytes repetidos son prominentes dentro de la representación de datos esperada, podría ser adecuado y eficiente que el algoritmo especifique uno o más bytes de conteo de iteración seguido de un caracter. Sin embargo, si tiene lugar una serie caracteres extensa, esa serie requerirá dos (o más) bytes para decodificarlos, es decir, 00000001 01011000 podría ser la transmisión de bits de salida requerida para un ASCII "X" de la transmisión de entrada. Entonces, cien "X" en una fila sería una salida de 01100100 01011000, lo que es bastante bueno.

Lo que se realiza con frecuencia en las variantes RLE consiste en utilizar selectivamente los bytes para indicar los conteos de iterador o bien que los bytes se representen a sí mismos. Al menos un valor de un byte debe reservarse para hacer esto, pero puede liberarse en la salida de datos, si fuese necesario.

Codificación Huffman

El algoritmo de Huffman es un algoritmo para la construcción de códigos de Huffman, desarrollado por David A. Huffman en 1952 y descrito en A Method for the Construction of Minimum-Redundancy Codes.

Descripción

El algoritmo consiste en la creación de un árbol binario que tiene cada uno de los símbolos por hoja, y construido de tal forma que siguiéndolo desde la raíz a cada una de sus hojas se obtiene el código Huffman asociado.

1. Se crean varios árboles, uno por cada uno de los símbolos del alfabeto, consistiendo cada uno de los árboles en un nodo sin hijos, y etiquetado cada uno con su símbolo asociado y su frecuencia de aparición.

2. Se toman los dos árboles de menor frecuencia, y se unen creando un nuevo árbol. La etiqueta de la raíz será la suma de las frecuencias de las raíces de los dos árboles que se unen, y cada uno de estos árboles será un hijo del nuevo árbol. También se etiquetan las dos ramas del nuevo árbol: con un 0 la de la izquierda, y con un 1 la de la derecha.

3. Se repite el paso 2 hasta que sólo quede un árbol.

Con este árbol se puede conocer el código asociado a un símbolo, así como obtener el símbolo asociado a un determinado código.

Para obtener el código asociado a un símbolo se debe proceder del siguiente modo:

1. Comenzar con un código vacío 2. Iniciar el recorrido del árbol en la hoja asociada al símbolo 3. Comenzar un recorrido del árbol hacia arriba 4. Cada vez que se suba un nivel, añadir al código la etiqueta de la rama que se ha

recorrido 5. Tras llegar a la raíz, invertir el código

El resultado es el código Huffman deseado

Para obtener un símbolo a partir de un código se debe hacer así:

1. Comenzar el recorrido del árbol en la raíz de éste 2. Extraer el primer símbolo del código a descodificar 3. Descender por la rama etiquetada con ese símbolo 4. Volver al paso 2 hasta que se llegue a una hoja, que será el símbolo asociado al

código

En la práctica, casi siempre se utiliza el árbol para obtener todos los códigos de una sola vez; luego se guardan en tablas y se descarta el árbol.

Compresión Lempel-Ziv

LZW (Lempel-Ziv-Welch) es un algoritmo de compresión sin pérdida desarrollado por Terry Welch en 1984 como una versión mejorada del algoritmo LZ78 desarrollado por Abraham Lempel y Jacob Ziv.

Probablemente, la técnica de compresión sin pérdidas más significativa es la técnica Lempel-Ziv. La idea en LZ78 es codificar una secuencia de bytes en transferencia con una tabla dinámica

La mayoría de los métodos de compresión se basan en un análisis inicial del texto para identificar cadenas repetidas para armar un diccionario de equivalencias, asignando códigos breves a estas cadenas. En una segunda etapa, se convierte el texto utilizando los códigos equivalentes para las cadenas repetidas. Esto requiere dos etapas, una de análisis y una segunda de conversión y también requiere que el diccionario se encuentre junto con el texto codificado, incrementando el tamaño del archivo de salida.

La clave del método LZW reside en que es posible crear sobre la marcha, de manera automática y en una única pasada un diccionario de cadenas que se encuentren dentro

del texto a comprimir mientras al mismo tiempo se procede a su codificación. Dicho diccionario no es transmitido con el texto comprimido, puesto que el descompresor puede reconstruirlo usando la misma lógica con que lo hace el compresor y, si está codificado correctamente, tendrá exactamente las mismas cadenas que el diccionario del compresor tenía.

El diccionario comienza pre-cargado con 256 entradas, una para cada carácter (byte) posible más un código predefinido para indicar el fin de archivo. A esta tabla se le van agregando sucesivos códigos numéricos por cada nuevo par de caracteres consecutivos que se lean (esto no es literalmente cierto, según se describe más adelante), aun cuando todavía no sea posible prever si ese código se reutilizará más adelante o no.

Es en este detalle donde se encuentra la brillantez del método: al armar el diccionario sobre la marcha se evita hacer dos pasadas sobre el texto, una analizando y la otra codificando y dado que la regla de armado del diccionario es tan simple, el descompresor puede reconstruirlo a partir del texto comprimido mientras lo lee, evitando así incluir el diccionario dentro del texto comprimido. Se puede objetar que el diccionario estará plagado de códigos que no se utilizarán y por tanto será innecesariamente grande, pero en la práctica el diccionario no crece demasiado y aún si lo hiciera no importa mucho pues el objetivo es que el archivo comprimido sea pequeño aun cuando los procesos de compresión y descompresión pudieran ocupar mucha memoria con el diccionario.

Las entradas del diccionario pueden representar secuencias de caracteres simples o secuencias de códigos de tal forma que un código puede representar dos caracteres o puede representar secuencias de otros códigos previamente cargados que a su vez representen, cada uno de ellos, otros códigos o caracteres simples, o sea que un código puede representar desde uno a un número indeterminado de caracteres. En realidad, el algoritmo no discrimina entre códigos y caracteres simples pues el diccionario se carga inicialmente de códigos que representan los primeros 256 caracteres simples por lo que estos no son más que otros códigos dentro del mismo diccionario.

Cada vez que se lee un nuevo carácter se revisa el diccionario para ver si forma parte de alguna entrada previa. Todos los caracteres están inicialmente predefinidos en el diccionario así que siempre habrá al menos una coincidencia, sin embargo, lo que se busca es la cadena más larga posible. Si el carácter leído no forma parte de más de una cadena más larga, entonces se emite la más larga que se hubiera encontrado y se agrega al diccionario una entrada formada por cualquiera que hubiera sido el código previo y este nuevo código. Si el carácter leído sí forma parte de más de una cadena del diccionario, se lee un nuevo carácter para ver si la secuencia formada por el carácter previo y el nuevo es alguna de las encontradas en el diccionario. En tanto los caracteres sucesivos que se vayan

leyendo ofrezcan más de una entrada posible en el diccionario, se siguen leyendo caracteres. Cuando la cadena sólo tiene una entrada en el diccionario, entonces se emite el código correspondiente a esa entrada y se incorpora al diccionario una nueva entrada que representa el último código emitido y el nuevo.

Otra característica importante del algoritmo es que los códigos en la salida se representan por cadenas de bits variables. El diccionario contiene inicialmente 257 códigos, 256 códigos para los 256 caracteres simples posibles con 8 bits y un código que representa el fin de archivo. Para esto serían necesarios códigos de 9 bits, lo cual quiere decir que aún hay disponibles 255 códigos de 9 bits para representar cadenas de caracteres. Cuando se llenan estas 255 entradas del diccionario, se amplían los códigos con un nuevo bit, lo cual permite 512 nuevas entradas. Cuando se completan estas 512 entradas, se agrega un bit y se disponen de 1024 nuevas entradas y así sucesivamente. En la práctica, se verifica que las primeras entradas, correspondientes a códigos de 12 bits de longitud (4096 entradas) se llenan rápidamente por lo que es habitual comenzar el proceso no con códigos de 9 bits sino directamente con códigos de 12 bits.