El algoritmo de codificación de Huffman fue desarrollado por David Huffman como parte de su tarea en el MIT.
La optimización (solo para un conjunto particular de probabilidades, es decir, para un modelo dado) de este algoritmo puede probarse considerando las siguientes dos comprobaciones que siempre son válidas al codificar utilizando el algoritmo Huffman:
1.) En un código óptimo, los símbolos que ocurren con mayor frecuencia (tienen una mayor probabilidad de ocurrencia) tendrán palabras de código más cortas que los símbolos que ocurren con menos frecuencia.
- ¿Cómo entender el algoritmo SHA-1? ¿Cuáles son los mejores ejemplos para ello?
- Cómo encontrar un elemento en un árbol de búsqueda binario
- ¿Cómo resuelven los árboles de segmentos el problema de apuñalamiento (todos los intervalos que contienen un punto dado)?
- Si una computadora toma el control total del control del tráfico aéreo, ¿cómo será el algoritmo? ¿Cómo manejará los aterrizajes de emergencia y cómo manejará una pista paralela?
- ¿Cuál es la complejidad temporal del tipo de conteo y fusión?
Prueba :
¡La prueba se explica por sí sola aquí! Por un lado, tenemos esta observación (o verificación) de que los símbolos más frecuentes tienen códigos más pequeños y viceversa. Por lo tanto, un código que asigna palabras de código más largas a los símbolos que ocurren con mayor frecuencia no puede ser óptimo. Por lo tanto, el algoritmo de Huffman es óptimo.
2.) En un código óptimo, los dos símbolos que ocurren con menos frecuencia tendrán la misma longitud.
Prueba :
Estamos demostrando este punto utilizando el principio de contradicción.
Supongamos que existe un código óptimo en el que las dos palabras de código correspondientes a los dos símbolos menos probables son diferentes. Entonces, digamos, la palabra de código más larga (Código2) es k bits más larga que la palabra de código más corta (Código1): 
Como se trata de un código de prefijo, la palabra de código más corta no puede ser un prefijo de la palabra de código más larga. Esto significa que incluso si dejamos caer los últimos k bits de la palabra de código más larga, las dos palabras de código seguirían siendo distintas. 
Como estas palabras de código corresponden a los símbolos menos probables del alfabeto, ninguna otra palabra de código puede ser más larga que estas palabras de código; por lo tanto, no hay peligro de que la palabra de código acortada se convierta en el prefijo de alguna otra palabra de código. Además, al soltar estos k bits obtenemos un nuevo código que tiene una longitud promedio más corta que el anterior. Pero esto viola nuestra discusión inicial. Por lo tanto, para un código óptimo, la segunda observación también es cierta.
¡Espero eso ayude!
Fuente: Libro “Compresión de datos” por Khalid Sayood
http://rahilshaikh.weebly.com/up…
