algoritmo de huffman 2
Post on 19-Jan-2016
69 Views
Preview:
TRANSCRIPT
ESTRUCTURA DE DATOS
ALGORITMO DE HUFFMAN
INTRODUCCIÓN
Este Algoritmo fue desarrollado por el norteamericano David Albert Huffman en 1952 mientras hacia su doctorado en el MIT.
El algoritmo funciona a partir de un conjunto dados de símbolos con sus respectivos pesos(frecuencia).
La salida del algoritmo es el mismo conjunto de símbolos de entrada codificado mediante un código binario con un tamaño menor.
DEFINICION
Es un algoritmo usado para la comprensión o encriptación de datos mediante el estudio de la frecuencia de aparición de los caracteres o simbolos .
Este algoritmo se usa precisamente para construir códigos de Huffman.
CODIGO DE HUFFMAN
Un código de huffman es un código de longitud variable, en el que la longitud de cada código depende de la frecuencia de aparición de cada símbolo en un texto.
Cuanto mas frecuente sea un símbolo su código asociado será mas corto. Además, un código Huffman es un código libre de prefijos, es decir ningún código forma parte de otro código; esto permite que los mensajes codificados sean no ambiguos.
OBJETIVOS
El objetivo mas importante es reducir la cantidad de espacio que ocupa la información a codificar .
VENTAJAS Y DESVENTAJAS
Ventajas:Es muy fácil codificar y decodificar - Solo reemplazar -Cada código tiene las misma longitud Desventaja: -La cadena resultante es muy larga
comparada con el mensaje
EJEMPLO :
PASO 1:Empezemos con una palabra , sea el caso ingeniero
PASO 2: Lo siguiente es ordenar estos caracteres en función a las frecuencias obtenidas, de menor a mayor y dejando solo el carácter con su correspondiente frecuencia, quedaría de la siguiente manera.
Paso 3: Lo siguiente es la construcción de un árbol binario mediante la unión de nodos que contienen el carácter y su respectiva frecuencia, los nodos que tenemos hasta ahorita son los siguientes.
PASO 4: Ahora lo que toca hacer es ir uniendo los nodos consecutivos en pares, sumaremos las frecuencias de esos dos nodos y luego con ellos crearemos un nuevo nodo. El nuevo nodo contendrá un caracter "null", seguido de la frecuencia obtenida al sumar las 2 frecuencias de los nodos con que se formó. Para entender mejor el concepto realizaremos este paso con los primeros 2 nodos de nuestro conjunto. El resultado es el siguiente.
PASO 5: Ahora, si seguimos el mismo procedimiento podemos concluir que obtendremos un árbol binario, donde las hojas del mismo serán los caracteres de nuestra palabra. Al seguir realizando el mismo procedimiento obtendremos lo siguiente
PASO 6:Seguimos el proceso secuencialmente.
PASO 7: Hacemos el mismo procedimiento con los nodos nuevos, se crea un nodo nuevo con la suma de las frecuencias, y le antecede un null.
PASO 8: Al final queda un árbol binario de la siguiente manera.
PASO 9: Lo siguiente es asignar ceros y unos a las ramas del árbol, las de la izquierda serán ceros, mientras que las de la derecha serán unos.
PASO 10: Lo siguiente es asignar ceros y unos a las ramas del árbol, las de la izquierda serán ceros, mientras que las de la derecha serán unos.
PASO 11:Codificamos las letras
i->111n->00
g->100e->01
r->101 o->110
Paso 12:Al final obtenemos nuestro código de huffman.
i-n-g-e-n-i-e-r-o11100100010011101101110
VIDEO
top related