Por Qué la Estrategia Codiciosa es Óptima
El algoritmo de Huffman es un algoritmo codicioso: en cada paso, toma la elección localmente óptima (fusiona los dos nodos más baratos) sin mirar hacia adelante. Los algoritmos codiciosos no siempre son globalmente óptimos — pero aquí lo son.
El Argumento de Optimalidad
Supongamos que un código C tiene la longitud promedio mínima L. Considere los dos símbolos con probabilidad más baja, digamos p_a y p_b. En cualquier código óptimo, estos dos símbolos deben aparecer como hojas hermanas al 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 menos probables.
Ahora, si combinas a y b en un meta-símbolo 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 de Huffman en el problema reducido. La inducción completa el argumento.
Vista Geométrica
El algoritmo de Huffman construye el árbol binario de abajo hacia arriba, colocando los símbolos menos probables a la mayor profundidad. Esto minimiza Σ p_i · depth(i) = L.
Una vista equivalente: estás asignando etiquetas a las hojas del árbol para minimizar la longitud de ruta ponderada, donde el peso de cada hoja es su probabilidad.
Ejecutando los Pasos Codiciosos
Probabilidades: p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1. Suma = 1.0 ✓
Paso 1: Los dos 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: Los dos más bajos: B(0.3), CD(0.3) (empate — cualquiera 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.
Hacia atrás: 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 de Longitud de Código
Dos códigos de Huffman pueden lograr la misma L pero tener diferentes distribuciones de longitud de código. La varianza de longitudes de código mide esta dispersión:
Var(l) = E[l²] − (E[l])²
donde E[l] = L (longitud de código promedio) y E[l²] = Σ p_i · l_i².
Por qué la varianza es importante:
1. Requisitos de búfer. En la decodificación en tiempo real, cada símbolo toma un número variable de bits. La varianza alta 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. Latencia de decodificación. Los códigos de alta varianza tienen caminos de decodificación de caso peor largo. Los códigos de baja varianza (frondoso) limitan el caso peor más estrictamente.
3. Robustez. Un bit perdido en un código de alta varianza causa más daño de sincronización porque las palabras de código largas deben ser completamente re-leídas.
La recomendación de Hamming: cuando existen múltiples códigos Huffman válidos (opciones de desempate), prefiere el de menor varianza — el árbol frondoso.
Calculando 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
Código Huffman de 3 Símbolos de Extremo a Extremo
Un ejemplo completo de extremo a extremo: 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). Los dos más bajos: Y(0.3), Z(0.1).
Fusionar → YZ(0.4). Lista: X(0.6), YZ(0.4).
Paso 2: Fusionar 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.
Varianza: 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.
Tu Turno: Una Tubería Completa
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.