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:
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.
Busca los dos árboles que presenten las menores
probabilidades de aparición.
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.
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.