Código como un Árbol
Un código libre de prefijo se asigna a un árbol binario: la raíz representa el comienzo de la decodificación, las ramas izquierdas representan el bit 0, las ramas derechas representan el bit 1, y las hojas representan palabras de código completas.
La restricción geométrica: cada hoja termina una ruta de la raíz a la hoja. Ninguna hoja puede tener un descendiente (si lo hiciera, su palabra de código sería un prefijo de la palabra de código del descendiente, violando la propiedad libre de prefijo).
Esto le da a la desigualdad de Kraft una interpretación geométrica:
Cada hoja a profundidad d 'ocupa' una fracción 2^(−d) de la capacidad total del árbol. La capacidad total de un árbol binario completo a profundidad D es 1. Un código libre de prefijo usa hojas a varias profundidades; la suma de Kraft mide la ocupación total.
Suma de Kraft = 1: código completo (cada ruta termina en una hoja — empaquetamiento perfecto).
Suma de Kraft < 1: código incompleto (algo de capacidad del árbol sin usar — se podrían agregar más símbolos).
Suma de Kraft > 1: imposible para códigos libres de prefijo (algunos caminos tendrían que compartir una hoja).
Hojas Más Profundas = Códigos Más Largos = Menos Capacidad
Una hoja a profundidad 1 usa la mitad de la capacidad del árbol (2^(−1) = 0.5).
Una hoja a profundidad 3 usa un octavo (2^(−3) = 0.125).
Colocar una palabra de código corta alta en el árbol bloquea a todos sus descendientes de ser usados — intercambias un código corto por muchos códigos potencialmente más largos.
Construyendo un Árbol Libre de Prefijo
Considera 5 símbolos con longitudes l = {1, 2, 3, 3, 3}. Suma de Kraft = 2^(−1) + 2^(−2) + 3·2^(−3) = 0.5 + 0.25 + 0.375 = 1.125 > 1.
Esto excede 1: estas longitudes son incompatibles con un código libre de prefijo. Al menos una longitud debe aumentar.
Arreglo: cambiar l_1 de 1 a 2. Nuevas longitudes {2, 2, 3, 3, 3}: Kraft = 2·2^(−2) + 3·2^(−3) = 0.5 + 0.375 = 0.875 < 1. Válido, pero incompleto.
Arreglo: cambiar l_1 de 2 a 2, agregar l_2 = 3 para usar la capacidad restante. Kraft = 0.875; restante = 0.125 = 2^(−3): espacio para una hoja más a profundidad 3.
Por Qué la Entropía Limita la Longitud del Código
La desigualdad de Kraft restringe la estructura del código (las longitudes deben ajustarse al árbol). La entropía de Shannon restringe la eficiencia del código (la longitud promedio no puede superar un piso teórico).
Longitudes óptimas del código. Para un símbolo con probabilidad p_i, la longitud de código ideal es log₂(1/p_i). Los símbolos raros merecen códigos largos; los símbolos frecuentes merecen códigos cortos. Esto refleja la igualdad de Kraft: 2^(−l_i) = p_i cuando l_i = log₂(1/p_i).
Pero log₂(1/p_i) rara vez es un entero. Redondeando hacia arriba a ⌈log₂(1/p_i)⌉ se obtiene la longitud de Huffman, que satisface H ≤ L < H + 1.
Lectura geométrica. Traza cada símbolo como un punto en el árbol binario a profundidad l_i. La suma de Kraft mide la cobertura total de hojas. La entropía mide la profundidad promedio ponderada, ponderada por probabilidad. Teorema de Shannon: la profundidad promedio ponderada por probabilidad ≥ contenido de información ponderado por probabilidad.
Verificación del Límite de Entropía
El ejemplo resuelto: p = [1/2, 1/4, 1/8, 1/8] para símbolos {A, B, C, D}.
Longitudes óptimas: l_A = log₂(2) = 1, l_B = log₂(4) = 2, l_C = log₂(8) = 3, l_D = log₂(8) = 3.
Estos son todos enteros — una coincidencia perfecta. Código de Huffman: A=0, B=10, C=110, D=111.
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 0.5 + 0.5 + 0.375 + 0.375 = 1.75.
H = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75. L = H exactamente: código óptimo.
Un Ejemplo Resuelto Completo
Tubería completa: dadas las probabilidades, calcula la entropía, verifica que un código cumpla con el límite.
Fuente: p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125.
H = 1.75 bits (calculado arriba).
Un código de bloque ingenuo: 4 símbolos → 2 bits cada uno → L = 2.0. Sobrecarga sobre entropía: 2.0 − 1.75 = 0.25 bits/símbolo = 12.5% de desperdicio.
El código de longitud variable ahorra 12.5% en comparación con longitud fija. Para mensajes grandes, esto es sustancial.
Tasa de entropía del inglés. Shannon estimó la entropía del inglés escrito en aproximadamente 1.0 a 1.3 bits por carácter, a pesar de usar códigos ASCII de 5 bits. Esa relación 4:1 refleja la redundancia masiva en el lenguaje natural — las letras comunes se agrupan, las palabras se repiten, la gramática restringe las secuencias.
La Compresión No Puede Vencer a la Entropía
Relación de compresión: H / (longitud del código de bloque). Para nuestro ejemplo: 1.75/2.0 = 0.875 — 87.5% de eficiencia.
¿Puedes comprimir más? Solo usando contexto: si codificas pares o triples de símbolos juntos, la entropía conjunta H(X,Y) puede ser menor que 2·H(X) debido a dependencias estadísticas. Esta es la extensión del teorema de codificación sin ruido a n-gramas.