Por qué la Estrategia Codificadora Es Óptima
El algoritmo de Huffman es un algoritmo codificador: en cada paso, elige la opción óptima local (fusionar los dos nodos más baratos) sin mirar hacia adelante. Los algoritmos codificadores no siempre son óptimos a nivel global, pero aquí lo son.
El Argumento de Óptimo
Supongamos un código C con una longitud media mínima L. Considere los dos símbolos de menor probabilidad, digamos p_a y p_b. En cualquier código óptimo, estos dos símbolos deben aparecer como hojas hermanas en el nivel más profundo del árbol. ¿Por qué?
Si no compartieran un padre, podrías intercambiar el símbolo más profundo con un código más corto - reduciendo L. Por lo tanto, las hojas más profundas deben ser los símbolos de menor probabilidad.
Ahora, si combinás a y b en un símbolo meta ab (con p_ab = p_a + p_b), cualquier código óptimo para el alfabeto reducido menos un símbolo es precisamente el código Huffman en el problema reducido. La inducción completa el argumento.
Visión Geométrica
El algoritmo de Huffman construye el árbol binario de abajo hacia arriba, colocando los símbolos de menor probabilidad en la mayor profundidad. Esto minimiza Σ p_i · profundidad(i) = L.
Una vista alternativa: estás asignando etiquetas a las hojas del árbol para minimizar la longitud de camino ponderada, donde cada hoja tiene un peso igual a su probabilidad.
Ejecución de los Pasos Codificadores
Probabilidades: p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1. Suma = 1.0 ✓
Paso 1: Más bajos: C(0.2), D(0.1). Fusionar → CD(0.3). Lista: A(0.4), B(0.3), CD(0.3).
Paso 2: Más bajos: B(0.3), CD(0.3) (empate - cualquiera es válido). Fusionar → BCD(0.6). Lista: A(0.4), BCD(0.6).
Paso 3: Fusionar A(0.4), BCD(0.6) → raíz(1.0). Asignar A=0, BCD=1.
De vuelta: BCD → B=10 (l=2), CD=11 → C=110 (l=3), D=111 (l=3).
L = 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 0.4+0.6+0.6+0.3 = 1.9 bits.
Varianza del largo del código
Dos códigos de Huffman pueden lograr el mismo L, pero tener distribuciones de longitudes de código diferentes. La varianza de las longitudes de código mide este despliegue:
Var(l) = E[l²] − (E[l])²
donde E[l] = L (longitud media del código) y E[l²] = Σ p_i · l_i².
Por qué la varianza importa:
1. Requisitos de búfer. En la descodificación en tiempo real, cada símbolo toma un número variable de bits. Alta varianza significa que algunos símbolos toman muchos bits. Necesitas un búfer de entrada más grande para garantizar que siempre puedas leer un símbolo completo.
2. Retardo de descodificación. Los códigos de alta varianza tienen caminos de descodificación peor caso largos. Los códigos de baja varianza (espesos) limitan el peor caso más estrechamente.
3. Robustez. Una pérdida de un bit en un código de alta varianza causa más daño en la sincronización porque los codewords largos deben leerse completamente de nuevo.
La recomendación de Hamming: cuando existen varios códigos Huffman válidos (elecciones de empate), elija el que tenga una menor varianza: el árbol espeso.
Calculando la varianza para dos árboles
Usando p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1 y el código A=0, B=10, C=110, D=111:
E[l] = L = 1.9
E[l²] = 0.4·1² + 0.3·2² + 0.2·3² + 0.1·3² = 0.4+1.2+1.8+0.9 = 4.3
Var = 4.3 − 1.9² = 4.3 − 3.61 = 0.69
Ejemplo Finalizado de 3 Símbolos de Huffman
Un ejemplo completo finalizado: construir código de Huffman, calcular L, calcular H, verificar L ≥ H, calcular Var.
Fuente: p(X)=0.6, p(Y)=0.3, p(Z)=0.1.
Construcción de Huffman:
Paso 1: Ordenado: X(0.6), Y(0.3), Z(0.1). Menores dos: Y(0.3), Z(0.1).
Unir → YZ(0.4). Lista: X(0.6), YZ(0.4).
Paso 2: Unir X(0.6), YZ(0.4) → raíz(1.0). Asignar X=0, YZ=1.
YZ → Y=10, Z=11.
Código: X=0 (l=1), Y=10 (l=2), Z=11 (l=2).
L = 0.6·1 + 0.3·2 + 0.1·2 = 0.6 + 0.6 + 0.2 = 1.4 bits.
Entropía: H = −0.6·log₂(0.6) − 0.3·log₂(0.3) − 0.1·log₂(0.1)
log₂(0.6) ≈ −0.737, log₂(0.3) ≈ −1.737, log₂(0.1) ≈ −3.322
H = 0.6·0.737 + 0.3·1.737 + 0.1·3.322 = 0.442 + 0.521 + 0.332 = 1.295 bits.
L = 1.4 ≥ H = 1.295 ✓. L/H = 1.4/1.295 ≈ 1.081. 8.1% por encima de la entropía.
Desviación estándar: E[l²] = 0.6·1 + 0.3·4 + 0.1·4 = 0.6+1.2+0.4 = 2.2. Var = 2.2 − 1.4² = 2.2 − 1.96 = 0.24.
Es Tu Turno: Un Pipelines Completo
Valores de log₂ para referencia: log₂(0.5)=−1.000, log₂(0.25)=−2.000, log₂(0.125)=−3.000, log₂(0.375)≈−1.415, log₂(0.625)≈−0.678.