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.

MÉTODO DE HUFFMAN