codificacion huffman

CODIFICACIÓN HUFFMAN
En ciencias de la computación y teoría de la información, lacodificación Huffman es un algoritmo usado para compresión de datos. El término se refiere al uso de una tabla decó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 probabilidadestimada de aparición de cada posible valor de dicho símbolo. Fue desarrollado por David A. Huffman mientras era estudiante de doctorado en elMIT, y publicado en "A MethodfortheConstruction ofMinimum-RedundancyCodes".
La codificación Huffman usa un método específico para elegir la representación de cada símbolo, que da lugar a un código prefijo (es decir, la cadena de bits que representa a un símboloen particular nunca es prefijo de la cadena de bits de un símbolo distinto) que representa los caracteres más comunes usando las cadenas de bits más cortas, y viceversa. Huffman fue capaz de diseñarel método de compresión más eficiente de este tipo: ninguna representación alternativa de un conjunto de símbolos de entrada produce una salida media más pequeña cuando las frecuencias de los símboloscoinciden con las usadas para crear el código. Posteriormente se encontró un método para llevar esto a cabo en un tiempo lineal si las probabilidades de los símbolos de entrada (también conocidascomo "pesos") están ordenadas.
Para un grupo de símbolos con una distribución de probabilidad uniforme y un número de miembros que es potencia de dos, la codificación Huffman es equivalente a unacodificación en bloque binaria, por ejemplo, la codificación ASCII. La codificación Huffman es un método para crear códigos prefijo tan extendido que el término "codificación Huffman" es ampliamente usadocomo sinónimo de "código prefijo", incluso cuando dicho código no se ha producido con el algoritmo de Huffman.
Aunque la codificación de Huffman es óptima para una codificación símbolo a símbolo...