Cómo Huffman Construye el Código Óptimo
Hamming presenta la codificación de Huffman como un algoritmo codicioso que construye un código libre de prefijos con longitud promedio mínima. La idea clave: construir el árbol de abajo hacia arriba, fusionando siempre los dos símbolos menos probables.
El Paso Adelante (Construir)
1. Ordenar todos los símbolos por probabilidad, de mayor a menor.
2. Tomar los dos símbolos de menor probabilidad. Combinarlos en un nuevo metasímbolo con probabilidad = suma de los dos.
3. Insertar el metasímbolo en su posición ordenada.
4. Repetir hasta que solo queden dos símbolos.
5. Asignar 0 y 1 a los dos símbolos restantes.
El Paso Hacia Atrás (Asignar Códigos)
Deshacer las fusiones en reversa: en cada división, los dos símbolos que fueron fusionados reciben los mismos bits de prefijo que su padre combinado, más un 0 adicional (un hijo) o 1 (otro hijo). La asignación de 0/1 es arbitraria — cualquiera es válido.
Por qué esto es óptimo: si cualquier otro código tuviera una longitud promedio menor L', aplicando la misma reducción hacia adelante eventualmente produciría dos símbolos con longitud promedio menor a 1 bit — imposible para un código de 2 símbolos. Contradicción.
Rastreando el Algoritmo
Ejemplo de Hamming: cuatro símbolos A, B, C, D con p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125.
Paso adelante:
Paso 1: Ordenado: A(0.5), B(0.25), C(0.125), D(0.125). Los dos más bajos: C, D.
Paso 2: Fusionar CD con p=0.25. Nueva lista: A(0.5), B(0.25), CD(0.25).
Paso 3: Los dos más bajos: B(0.25), CD(0.25). Fusionar BCD con p=0.5.
Paso 4: Dos símbolos restantes: A(0.5), BCD(0.5). Asignar A=0, BCD=1.
Paso hacia atrás:
BCD → B obtiene 10, CD obtiene 11. CD → C obtiene 110, D obtiene 111.
Código final: A=0 (l=1), B=10 (l=2), C=110 (l=3), D=111 (l=3).
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75 bits.
Múltiples Códigos de Huffman Válidos
Hamming señala dos fuentes de no unicidad:
1. Asignación arbitraria de 0/1. En cada división, puedes asignar 0 a cualquier hijo. Intercambiar 0 y 1 en todas partes da un código diferente con L idéntico.
2. Desempate. Cuando dos nodos tienen probabilidad igual, cualquiera puede colocarse 'más alto' (fusionarse primero). Diferentes opciones de desempate pueden producir árboles estructuralmente diferentes — 'largos' vs 'frondosos' — con el mismo L pero diferentes distribuciones de longitud de código.
Largo vs Frondoso
Árbol largo (sesgado): un símbolo en cada nivel de profundidad (estructura similar a Fibonacci). Las longitudes de código varían ampliamente: un símbolo obtiene un código corto, otros se propagan a códigos más largos.
Árbol frondoso (equilibrado): símbolos distribuidos uniformemente en niveles de profundidad. Las longitudes de código se agrupan cerca del promedio. Menor varianza.
Recomendación de Hamming: cuando tengas opción, prefiere el árbol frondoso. Mismo L, pero menor varianza en las longitudes de código → tiempo de decodificación más uniforme → menores requisitos de búfer en aplicaciones en tiempo real.
Calculando la Varianza de Longitud de Código
Varianza de las longitudes de código: Var = E[l²] − (E[l])²
Para el código {A=0 l=1, B=10 l=2, C=110 l=3, D=111 l=3} con p=[0.5, 0.25, 0.125, 0.125]:
E[l] = L = 1.75
E[l²] = 0.5·1² + 0.25·2² + 0.125·3² + 0.125·3² = 0.5 + 1.0 + 1.125 + 1.125 = 3.75
Var = 3.75 − 1.75² = 3.75 − 3.0625 = 0.6875
Un código frondoso alternativo para símbolos equiprobables usa todos los códigos de longitud 2: L=2, Var=0.
Ganancias de Compresión vs Distribución de Símbolos
Regla de Hamming: la codificación de Huffman se justifica solo cuando las probabilidades de los símbolos difieren sustancialmente.
Probabilidades iguales. Si todos los símbolos 2^k tienen probabilidad igual 1/2^k, Huffman produce un código de bloque: cada símbolo obtiene longitud k. L = H = k. Sin ganancia sobre el código de bloque simple.
Probabilidades sesgadas. Si un símbolo domina (p >> 1/2^k para otros), Huffman le asigna un código muy corto (longitud 1 o 2), reduciendo dramáticamente L.
El código de coma (término de Hamming). Cuando cada probabilidad excede 2/3 del total restante, Huffman naturalmente produce: p(s1)→0, p(s2)→10, p(s3)→110, ..., hasta dos códigos de longitud igual al final. Este es un 'código de coma': el 0 final después de una serie de 1s actúa como una coma.
Hamming observa: la compresión de datos del mundo real (copia de seguridad, archivo de archivos) puede reducir el almacenamiento a más de la mitad cuando la fuente tiene probabilidades sesgadas — el texto en inglés siendo un ejemplo principal.
Huffman vs Código de Bloque: Comparación Numérica
Segundo ejemplo de Hamming: p(s1)=1/3, p(s2)=1/5, p(s3)=1/6, p(s4)=1/10, p(s5)=1/12, p(s6)=1/20, p(s7)=1/30, p(s8)=1/30.
Código de bloque: 8 símbolos → 3 bits cada uno → L_block = 3.
Hamming calcula el código de Huffman e informa L_Huffman ≈ 2.58 bits.
Ahorros: (3 − 2.58)/3 ≈ compresión del 14% sobre codificación de bloque.
Cuando las probabilidades de los símbolos difieren mucho (1/3 vs 1/30 aquí, una proporción de 10:1), la codificación de longitud variable se justifica sustancialmente.
Programas Autocompilables
Hamming termina el Capítulo 11 con una idea impactante: un codificador de Huffman puede codificarse a sí mismo. El árbol de decodificación (que le dice al decodificador cómo leer el mensaje comprimido) se transmite junto con los datos comprimidos. El receptor no necesita conocimiento previo del código.
El codificador: muestrea los datos, estima probabilidades, construye el código de Huffman, codifica el árbol de decodificación como encabezado, luego codifica los datos.
El decodificador: lee el encabezado para reconstruir el árbol, luego decodifica los datos usando el mismo.
Punto de Hamming: todo este pipeline puede ejecutarse como una función de biblioteca sin intervención humana. Lo llamas, y comprime y descomprime automáticamente. Los formatos de archivo modernos (ZIP, gzip, bzip2) implementan exactamente este patrón.
El principio más profundo: la inteligencia está en el algoritmo, no en una tabla de códigos fija. El algoritmo se adapta a cualquier dato que reciba. Este es el patrón que Hamming ve en todos los grandes sistemas de ingeniería: adaptabilidad incorporada, no añadida.