El término se refiere al uso de una tabla de códigos de longitud variable para codificar un determinado símbolo (como puede ser un carácter en un archivo), donde la tabla ha sido rellenada de una manera específica basándose en la probabilidad estimada de aparición de cada posible valor de dicho símbolo. Fue desarrollado por David A. Huffman mientras era estudiante de doctorado en el MIT, y publicado en "A Method for the Construction of Minimum-Redundancy Codes".
El algoritmo de construcción del árbol puede resumirse así:
- Crear un nodo hoja para cada símbolo, asociando un peso según su frecuencia de aparición e insertarlo en la lista ordenada ascendentemente.
- Mientras haya mas de un nodo en la lista:
- Eliminar los dos nodos con menor probabilidad de la lista
- Crear un nuevo nodo interno que enlace a los nodos anteriores, asignándole como peso la suma de los pesos de los nodos hijos.
- Insertar el nuevo nodo en la lista, (en el lugar que le corresponda según el peso).
- El nodo que quede es el nodo raíz del árbol.
Github
Material de apoyo
No hay comentarios.:
Publicar un comentario