7.2 Método de Huffman.

Técnicas Independientes del tipo de dato.


MÉTODO DE HUFFMAN


COMPACTAR


1.- Realizar un recorrido por el archivo a compactar, e ir acumulando en un arreglo de contadores de incidencias la cantidad de veces que aparece cada carácter.

2.- Construir un árbol binario de recorridos de tal forma que los caracteres encontrados sean hojas en la estructura. Es importante que los caracteres con mayor incidencias queden mas cercanos a la raíz .

3.- Etiquetar las ramas del árbol con bits, 0 rama izquierda, 1 rama derecha.

4.- Crear una tabla de códigos (vector) donde se registre el recorrido desde la raíz hasta una hoja especifica, señalando los bits encontrados en las ramas.

5.- Recorrer el archivo original e ir acumulando los bits de la nueva codificación hasta completar ocho de ellos, escribir en el archivo destino el carácter del ASCII que corresponda a los ocho bits codificados según la codificación normal.


DESCOMPACTAR


1.- Recuperar de los contadores de incidencias almacenados el árbol de recorridos y la cantidad de bits de relleno del ultimo carácter.

2.- Recorrer el archivo compactado aplicando el siguiente procedimiento para cada carácter.

* Obtener ordinal y convertirlo a binario.
* Realizar recorrido al árbol hasta llegar a una hoja.
* Guardar en el archivo destino (descompactado) el carácter encontrado en la hoja.