tarea

INSTITUTO POLITÉCNICO
NACIONAL
ESCUELA SUPERIOR DE CÓMPUTO

Análisis de Algoritmos
Practica 5
“Algoritmo de Huffman”

Introducción
El algoritmo de Huffman es un algoritmo para la construcción de códigos de Huffman, desarrollado por
David A. Huffman en 1952. Este algoritmo toma un alfabeto de n símbolos, junto con sus frecuencias
de aparición asociadas, y produce un código de Huffmanpara ese alfabeto y esas frecuencias.
Este algoritmo consiste en la creación de un árbol binario en el cual se tiene en cada nodo hoja un
caracter correspondiente a la tabla de frecuencias, el arbol está construido de tal forma que siguiéndolo
desde la raíz a cada una de sus hojas se obtiene el código Huffman asociado.
1. Se crean varios árboles, uno por cada uno de los símbolos del alfabeto,consistiendo cada uno
de los árboles en un nodo sin hijos, y etiquetado cada uno con su símbolo asociado y su
frecuencia de aparición.
2. Se toman los dos árboles de menor frecuencia, y se unen creando un nuevo árbol. La etiqueta de
la raíz será la suma de las frecuencias de las raíces de los dos árboles que se unen, y cada uno de
estos árboles será un hijo del nuevo árbol. También seetiquetan las dos ramas del nuevo árbol:
con un 0 la de la izquierda, y con un 1 la de la derecha.
3. Se repite el paso 2 hasta que sólo quede un árbol.
Con este árbol se puede conocer el código asociado a un símbolo, así como obtener el símbolo asociado
a un determinado código.
Para obtener el código asociado a un símbolo se debe proceder del siguiente modo:
1.
2.
3.
4.
5.
6.

Comenzar conun código vacío.
Iniciar el recorrido del árbol en la hoja asociada al símbolo.
Comenzar un recorrido del árbol hacia arriba.
Cada vez que se suba un nivel, añadir al código la etiqueta de la rama que se ha recorrido.
Tras llegar a la raíz, invertir el código.
El resultado es el código Huffman deseado.

Para obtener un símbolo a partir de un código se debe hacer así:
1.
2.
3.
4.Comenzar el recorrido del árbol en la raíz de éste.
Extraer el primer símbolo del código a descodificar.
Descender por la rama etiquetada con ese símbolo.
Volver al paso 2 hasta que se llegue a una hoja, que será el símbolo asociado al código.

En la práctica, casi siempre se utiliza el árbol para obtener todos los códigos de una sola vez; luego se
guardan en tablas y se descarta el árbol.Ejemplo: Implementación en C del algoritmo de
Huffman(Compresor)
Coidificar el siguiente texto: “HOLA MAMA”
Primer paso: Obtener la tabla de frecuencias de cada caracter
Se abrira y leera el archivo en forma binaria, y se empezara el recorrido del archivo.
Recorriendo el texto podemos ver que H, L, O y el espacio solo aparecen una vez por lo que su
frecuencia es uno, entonces se creará un nodoel cual contendra el caracter y su respectiva frecuencia,
podemos observar que M se repite dos veces y A tres por lo que su frecuencia sera dos y tres
respectivamente, igualmente creamos un nodo por cada caracter con su respectiva frecuencia.
Una vez que se crea un nodo este se inserta en una lista, una vez que se recorra todo el texto quedará
armada una losta de frecuencias la cual deveraser ordenada de forma acendente, de tal forma que nos
quede de la siguiente forma:

H

1

O

1

L

1

1

M

2

A

3

Donde cada nodo representara el nodo raiz de un arbol nomario.

Segundo paso: Armar el albol de codificación.
En este paso se creara un nuevo nodo el cual contendra la suma de las frecuencias de los dos primeros
nodos, este nodo igual sera un nodo raiz porlo que asignaremos a su hijo izquierdo el primer nodo y a
su hijo derecho el segundo nodo, tal y como se muestra en la sig. Figuara:

NULL 2

H | 1

O | 1

Despues el nuevo nodo es colocado de forma ordenada en la lista:

| 1

L | 1

M | 2

A | 3

NULL | 2

H | 1

O | 1

De la misma forma seguimos el procedimiento anterior para todos los nodos hasta que solo quede un...