DEFINICION Y REPRESENTACION DE UN ARBOL DE PESOS:
El peso de un árbol en un nodo dado es el número de nodos en el árbol son contarse el mismo.
El peso de un nodo de un árbol es la longitud del camino más largo del nodo a una hoja.
El peso del árbol se define por la suma de sus aristas, ya que estas están etiquetadas o mejor dicho se le conocen como peso.
Ejemplo:
RELACIÓN DE UN ÁRBOL CON EL CÓDIGO DE HUFFMAN:
El algoritmo de Huffman sirve para la encriptación de datos mediante el estudio de la frecuencia de aparición de caracteres. Este funciona a partir de un conjunto dado de símbolos con sus respectivos pesos.
El algoritmo consiste en la creación de un árbol binario que tiene cada uno de los símbolos por hoja, y 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 se etiquetan 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- Comenzar con un código vacío
2- Iniciar el recorrido del árbol en la hoja asociada al símbolo
3- Comenzar un recorrido del árbol hacia arriba
4- Cada vez que se suba un nivel, añadir al código la etiqueta de la rama que se ha recorrido
5- Tras llegar a la raíz, invertir el código
6- El resultado es el código Huffman deseado
Referencias:
MATEMÁTICAS DISCRETAS: ÁRBOLES CON PESO (mate-booleanas.blogspot.com)
Algoritmo de Huffman.pdf (uvigo.es)
Algoritmo de Huffman | Algoritmos | Matemáticas Aplicadas (scribd.com)
No hay comentarios:
Publicar un comentario