.
Algortimo de Huffman
El algoritmo de Huffman es un algoritmo que permite comprimir y encriptar datos basándose en la probabilidad de ocurrencia de cada uno de los caracteres contenidos en el mensaje (o archivo) a comprimir/encriptar.
El objetivo de este trabajo es aplicar el algoritmo de Huffman para desarrollar un programa que permita comprimir y descomprimir archivos.
Teoría de Huffman
El algotirmo de Huffman asigna a cada caracter del archivo un código (que llamaremos código Huffman) de longitud variable (medida en cantidad de bits). A los caracteres con mayor cantidad de ocurrencias se les asigna un código Huffman con menor longitud y a los que tienen menor cantidad de ocurrencias se les asigna un código con longitud mayor.
A continuación vamos a analizar un ejemplo completo para comprender como funciona el algoritmo que utilizaremos para comprimir y descomprimir archivos.
Ejemplo
Supongamos que tenemos que comprimir un archivo que contiene el siguiente texto:
Paso 1
Contar las ocurrencias de cada caracter.
Para contar las ocurrencias utilizamos una tabla (que luego implementaremos como un array de 0 a 255 registros) en la que almacenamos el caracter (en la posición del array que coincide con su código ASCII) y la cantidad de ocurrencias de este caracter en el archivo (que llamaremos n).
Paso 2
Creamos una lista ordenada ascendentemente por la cantidad de ocurrencias de cada caracter. Primero los menos ocurrentes y luego los más ocurrentes. Si dos caracteres ocurren con igual probabilidad entonces primero colocamos al que tiene menor valor ASCII. Por ejemplo: en la tabla vemos que los caractetes I, N, R, S, U ocurren una sola vez. Tienen la misma probabilidad de ocurrencia entre si por lo tanto en la lista ordenada que veremos a continuación los colocaremos por orden ascendente de su código ASCII (léase de izquierda a derecha y de arriba hacia abajo).
Paso 3
Tomamos los dos primeros nodos de la lista y creamos un pequeño árbol binario que tandrá un nodo raíz con un caracter ficticio que llamaremos *1 (asterisco uno) y una probabilidad de ocurrencia igual a la suma de las probabilidades de los dos nodos que estamos procesando. En la rama derecha colocamos el primer nodo y en la rama izquierda colocamos el segundo nodo.
Luego insertamos el nuevo nodo en la lista respetando el criterio de ordenamiento. Si en la lista existe un caracter con la misma probabilidad (en este caso 2) la inserción la haremos a continuación del caracter existente.
Ahora repetimos la operación tomando los nodos R(1) y S(1):
Continuamos con este proceso hasta obtener un único nodo cuya probabilidad (cantidad de ocurrencias) sea igual a la suma de las probabilidades de los caracteres del archivo.
El desarrollo completo del árbol puede verse en este link.
Paso 4
Con el árbol terminado, comenzamos a codificar los caracteres asignando 0 (cero) a cada nodo a la izquierda y 1 (uno) a cada nodo a la derecha.
Entonces para obtener la codificación Huffman de un caracter simplemente recorremos el árbol hasta llegar a la hoja que contiene el caracter que queremos codificar. Asignamos unos o ceros según nos indique camino que tomamos.
Así, el código Huffman para codificar el caracter R será: 10101, cuya longitud (que llamaremos nCod) es 5. En cambio para codificar el caracter M el código será: 001 y su nCod = 3. Y para codificar el caracter O (letra “O”) obtendremos el código: 01, con nCod = 2.
Podemos observar que el caracter que más se repite en el texto (o archivo) que estamos procesando (la letra O) obtuvo un código de longitud menor (nCod = 2), en cambio el caracter R (uno de los que menos veces aparece) obtuvo un código de longitud mayor (nCod = 5). Y un caracter intermedio como la M que aparece 5 veces obtuvo un código de longitud intermedia: nCod = 3.
Recordemos que cada carecter ocupa 1 byte (8 bits). Huffman permite reemplazar los 8 bits de (por ejemplo) el caracter M por los 3 bits del código que obtuvimos.
Paso 5
Volvamos a la tabla de ocurrencias para asignar el código Huffman (cod) y el nCod que le corresponde a cada caracter del texto que estamos procesando.
Paso 6
Para finalizar el proceso simplemente reemplazamos cada caracter por su código Huffman y luego agrupamos en paquetes de a 8 bits para obtener los bytes que serán el resultado del algoritmo.
Como resultado logramos comprimir un texto de 39 bytes (39 caracteres) en solo 16 bytes. El algoritmo permite comprimir este texto casi un 59%.
