Código como uma Árvore
Um código sem prefixo mapeia para uma árvore binária: a raiz representa o início da decodificação, ramos esquerdos representam o bit 0, ramos direitos representam o bit 1, e folhas representam palavras-código completas.
A restrição geométrica: toda folha termina um caminho da raiz para a folha. Nenhuma folha pode ter um descendente (se tivesse, sua palavra-código seria um prefixo da palavra-código do descendente, violando a propriedade sem prefixo).
Isso dá à desigualdade de Kraft uma interpretação geométrica:
Cada folha a profundidade d 'ocupa' uma fração 2^(−d) da capacidade total da árvore. A capacidade total de uma árvore binária completa a profundidade D é 1. Um código sem prefixo usa folhas em várias profundidades; a soma de Kraft mede a ocupação total.
Soma de Kraft = 1: código completo (todo caminho termina em uma folha — empacotamento perfeito).
Soma de Kraft < 1: código incompleto (alguma capacidade de árvore não utilizada — mais símbolos poderiam ser adicionados).
Soma de Kraft > 1: impossível para códigos sem prefixo (alguns caminhos teriam que compartilhar uma folha).
Folhas Mais Profundas = Códigos Mais Longos = Menos Capacidade
Uma folha a profundidade 1 usa metade da capacidade da árvore (2^(−1) = 0,5).
Uma folha a profundidade 3 usa um oitavo (2^(−3) = 0,125).
Colocar uma palavra-código curta no topo da árvore bloqueia todos os seus descendentes de serem usados — você troca um código curto por muitas palavras-código potencialmente mais longas.
Construindo uma Árvore Sem Prefixo
Considere 5 símbolos com comprimentos l = {1, 2, 3, 3, 3}. Soma de Kraft = 2^(−1) + 2^(−2) + 3·2^(−3) = 0,5 + 0,25 + 0,375 = 1,125 > 1.
Isso excede 1: esses comprimentos são incompatíveis com um código sem prefixo válido. Pelo menos um comprimento deve aumentar.
Correção: altere l_1 de 1 para 2. Novos comprimentos {2, 2, 3, 3, 3}: Kraft = 2·2^(−2) + 3·2^(−3) = 0,5 + 0,375 = 0,875 < 1. Válido, mas incompleto.
Correção: altere l_1 de 2 para 2, adicione l_2 = 3 para usar a capacidade restante. Kraft = 0,875; restante = 0,125 = 2^(−3): espaço para uma folha de profundidade 3 adicional.
Por que a Entropia Limita o Comprimento do Código
A desigualdade de Kraft restringe a estrutura do código (os comprimentos devem caber na árvore). A entropia de Shannon restringe a eficiência do código (o comprimento médio não pode superar um limite teórico).
Comprimentos de código ideais. Para um símbolo com probabilidade p_i, o comprimento de código ideal é log₂(1/p_i). Símbolos raros merecem códigos longos; símbolos frequentes merecem códigos curtos. Isso espelha a igualdade de Kraft: 2^(−l_i) = p_i quando l_i = log₂(1/p_i).
Mas log₂(1/p_i) raramente é um inteiro. Arredondar para cima até ⌈log₂(1/p_i)⌉ dá o comprimento de Huffman, que satisfaz H ≤ L < H + 1.
Leitura geométrica. Trace cada símbolo como um ponto na árvore binária a profundidade l_i. A soma de Kraft mede a cobertura total de folhas. A entropia mede a média ponderada da profundidade, ponderada pela probabilidade. O teorema de Shannon: a profundidade média ponderada por probabilidade ≥ conteúdo de informação ponderado por probabilidade.
Verificação do Limite de Entropia
O exemplo resolvido: p = [1/2, 1/4, 1/8, 1/8] para símbolos {A, B, C, D}.
Comprimentos ideais: l_A = log₂(2) = 1, l_B = log₂(4) = 2, l_C = log₂(8) = 3, l_D = log₂(8) = 3.
Estes são todos inteiros — uma correspondência perfeita. 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 exatamente: código ótimo.
Um Exemplo Completo Resolvido
Pipeline completo: dadas probabilidades, calcule entropia, verifique se um código atende ao limite.
Fonte: p(A)=0,5, p(B)=0,25, p(C)=0,125, p(D)=0,125.
H = 1,75 bits (calculado acima).
Um código de bloco ingênuo: 4 símbolos → 2 bits cada → L = 2,0. Overhead sobre entropia: 2,0 − 1,75 = 0,25 bits/símbolo = 12,5% de desperdício.
O código de comprimento variável economiza 12,5% comparado ao código de comprimento fixo. Para mensagens grandes, isso é substancial.
Taxa de entropia do inglês. Shannon estimou a entropia do inglês escrito em cerca de 1,0 a 1,3 bits por caractere, apesar de usar códigos ASCII de 5 bits. Essa razão 4:1 reflete a redundância massiva na linguagem natural — letras comuns se agrupam, palavras se repetem, a gramática restringe sequências.
Compressão Não Pode Superar a Entropia
Razão de compressão: H / (comprimento de código de bloco). Para nosso exemplo: 1,75/2,0 = 0,875 — 87,5% de eficiência.
Você pode comprimir ainda mais? Apenas usando contexto: se você codificar pares ou triplos de símbolos juntos, a entropia conjunta H(X,Y) pode ser menor que 2·H(X) devido a dependências estatísticas. Esta é a extensão do teorema de codificação sem ruído para n-gramas.