Aula Macedonia


ArtÝculos Varios


ArtÝculo realizado por
JosÚ Conde "Rewin".





Fundamentos de los algoritmos compresores

Con este artículo vamos a tratar de dar una idea de como funcionan estos pequeños programas que utilizamos asiduamente y desconocemos su método de trabajo.

Primero indicar que la compresión de datos puede ser tanto software como hardware. Vamos a ver sólo esta primera.

Los programas compresores de datos utilizan diversos algoritmos para llevar a cabo su función. Se basan todos ellos en la búsqueda de caracteres repetidos y su frecuencia de aparición (aunque algún otro usa alguna técnica más sencilla).

Estos algoritmos representan un conjunto de bits en otro de tamaño menor, pero entre los cuales se establece una relación única. Debemos señalar que un mal uso de un algoritmo para un conjunto de datos puede llevarnos al efecto contrario al que buscamos (la expansión del archivo). Para eliminar esta posibilidad, los programas compresores de datos hacen un estudio de los datos del archivo, realizando una lectura previa y analizando cual es el algoritmo que mayor compresión generará, para después aplicarlo.

Los métodos empleados convierten cada byte (8 bits) en un secuencia de bits de menor tamaño.

Existen varios métodos de compresión de datos:



Método de los 7 bits:

Se puede usar únicamente para archivos cuyo contenido esté en código ASCII no extendido, es decir, todos sus caracteres están representados por valores entre el 0 y el 127 del código ASCII. Cada carácter de estos archivos desaprovecha el primer bit, ya que su información se representa por 7 bits, estando el primero siempre a 0. Este algoritmo elimina este primer bit de cada byte, escribiendo los 7 bits de información uno a continuación del otro. Su razón de compresión es siempre constante y es de 12,5 por 100 de reducción. Su compresión es rápida y simple.



Método Run Length Encoding (RLE):

Se basa en las posibles repeticiones consecutivas de un carácter. Veamos esto con un ejemplo. Si vamos leyendo un archivo y nos encontramos con la siguiente secuencia rrrrr podemos sustituirla en el archivo comprimido por un 5r, escribiendo primero el número de veces consecutivas que se repite el byte y después cuál es el carácter representado. Debemos tener en cuenta que cuando aparezca un carácter sin repetición, ocuparía más espacio codificar 1r que r. Teniendo en cuenta esta excepción, es fácil de realizar el algoritmo de compresión y descompresión.



Método de Huffman:

Se basa en las diferentes frecuencias de aparición de los caracteres en un archivo. Se codifican los caracteres como secuencias de bit, los más frecuentes tienen secuencias más pequeñas y los menos frecuentes, más largas. El objetivo del algoritmo es formar un árbol binario que represente el código. En los nodos terminales (hojas) de este árbol se almacenarán los caracteres que se desea codificar junto con la probabilidad de aparición de cada uno de ellos. Además, los caracteres que tienen probabilidad más alta, estarán más próximos a la raíz que a los de menor probabilidad. Así, el camino desde la raíz del árbol a cualquier hoja del mismo representará el código para el carácter de esa hoja.
El algoritmo de Huffman realiza los siguientes pasos:

  1. Crea tantos árboles independientes como caracteres se vayan a codificar. Cada carácter será la raíz de un árbol independiente, junto con su probabilidad de aparición.

  2. Busca los dos árboles que presenten las menores probabilidades de aparición.

  3. Agrupa los dos árboles encontrados en uno sólo. En la raíz de este nuevo árbol no se almacena ningún carácter. Unicamente la probabilidad de aparición de los caracteres agrupados, que se obtendrá sumando las probabilidades respectivas de cada árbol.

  4. Repite los pasos 2 y 3 hasta que sólo quede un árbol que agrupe a todos los caracteres.



Método de Lempel-Ziv:

Es una combinación del método de Huffman y de la redundancia en los bloques de datos. El algoritmo leerá un bloque de caracteres en el archivo, y verificará si se encuentra repetido con respecto a lo ya leído. Si es así, se informarán dos parámetros: el primero con la posición de inicio del bloque y el segundo con la longitud del bloque.





AULA MACEDONIA
a
MACEDONIA Magazine