Cadificacion Huffman

CODIFICACIÓN DE HUFFMAN
Resumen: En ciencias de la computación y teoría de la información, la codificación Huffman es un algoritmo usado para compresión de datos, los árboles binarios han sidousados para para esta aplicación, desarrollada por David A. Huffman en 1952.

Índice de Términos: algoritmo, código, árboles binarios, compresión de datos.
INTRODUCCIÓN

“Un código de Huffman es uncódigo de longitud variable, en el que la longitud de cada código depende de la frecuencia relativa de aparición de cada símbolo en un texto: cuanto más frecuente sea un símbolo, su código asociadoserá más corto. Además, un código Huffman es un código libre de prefijos: es decir, ningún código forma la primera parte de otro código; esto permite que los mensajes codificados sean no ambiguos.Este es el codificador estadístico más popular, y erróneamente se tiende a pensar que su funcionamiento es óptimo. Este algoritmo es capaz de producir un código óptimo en el sentido de MínimaRedundancia para el código de entrada. Esta compresión sólo será óptima si las probabilidades de todos los símbolos de entrada son potencias enteras de 1/2. Y el peor de todos los casos se presentarácuando alguno de los símbolos posea una probabilidad cercana al 100%”. [1]
Definición del problema

1. Descripción informal
* Dados un conjunto de símbolos y sus pesos(normalmente proporcionales aprobabilidades). Encontrar en código binario prefijo (un conjunto de elementos del código) con longitud de palabra esperada mínima (de forma equivalente, un árbol con longitud del camino mínima).2. Descripción formal
Entradas
El alfabeto, que es el alfabeto de símbolos de tamaño .
El conjunto , que es el conjunto de pesos (positivos) de los símbolos (normalmente proporcionales aprobabilidades), es decir .
Salida
El código, que es el conjunto de elementos del código (binario), donde  es la palabra del código para .
Objetivo
Sea  la longitud del camino ponderado del código ....