Código como uma Árvore
Um código prefixo mapeia para uma árvore binária: a raiz representa o início da decodificação, as ramificações para a esquerda representam o bit 0, as ramificações para a direita representam o bit 1 e as folhas representam as palavras-código completas.
A restrição geométrica: cada folha termina uma trilha raiz-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 prefix-free).
Isso dá à desigualdade de Kraft uma interpretação geométrica:
Cada folha em uma profundidade d 'ocupa' uma fração 2^(−d) da capacidade total da árvore. A capacidade total de uma árvore binária completa em profundidade D é 1. Um código prefixo usa folhas em várias profundidades; a soma de Kraft mede o uso total da capacidade.
Soma de Kraft = 1: código completo (cada trilha termina em uma folha - embalagem perfeita).
Soma de Kraft < 1: código incompleto (capacidade da árvore não usada - mais símbolos poderiam ser adicionados).
Soma de Kraft > 1: impossível para códigos prefixo (algumas trilhas teriam que compartilhar uma folha).
Folhas Mais Profundas = Códigos Mais Longos = Menor Capacidade
Uma folha em profundidade 1 usa metade da capacidade da árvore (2^(−1) = 0,5).
Uma folha em profundidade 3 usa um oitavo (2^(−3) = 0,125).
Colocar uma palavra-código curta alto na árvore bloqueia todos seus descendentes de serem usados - você troca uma curta código por muitos códigos potenciais mais longos.
Construindo uma Árvore Prefix-Free
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 prefixo. Pelo menos uma extensão 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 adicional em profundidade 3.
Por que a Entropia Limita o Tamanho do Código
A desigualdade de Kraft limita a estrutura do código (os comprimentos devem caber na árvore). A entropia de Shannon limita a eficiência do código (a média da extensão não pode superar um piso teórico).
Comprimentos de código ótimos. Para um símbolo com probabilidade p_i, o código ideal é de comprimento log2 (1 / p_i). Símbolos raros merecem longos códigos; símbolos frequentes merecem curtos. Isso reflete a igualdade de Kraft: 2^(-l_i) = p_i quando l_i = log2 (1 / p_i).
Mas log2 (1 / p_i) raramente é um inteiro. Redondeando para ⌈log2 (1 / p_i)⌉ dá o comprimento de Huffman, que satisfaz H ≤ L < H + 1.
Leitura geométrica. Plote cada símbolo como um ponto na árvore binária em profundidade l_i. A soma de Kraft mede a cobertura total das folhas. A entropia mede a profundidade média ponderada, ponderada pela probabilidade. O teorema de Shannon: a profundidade média ponderada pela probabilidade ≥ o conteúdo de informação ponderado pela probabilidade.
Verificação da Desigualdade de Entropia
O exemplo resolvido: p = [1/2, 1/4, 1/8, 1/8] para símbolos {A, B, C, D}.
Comprimentos ótimos: l_A = log2 (2) = 1, l_B = log2 (4) = 2, l_C = log2 (8) = 3, l_D = log2 (8) = 3.
Esses são todos inteiros - um perfeito encaixe. 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
Pipelin e: dadas as probabilidades, calcule a 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 bloco ingênuo: 4 símbolos → 2 bits cada → L = 2,0. Sobrecarga sobre a entropia: 2,0 - 1,75 = 0,25 bits/símbolo = 12,5% de perda.
O código de comprimento variável economiza 12,5% em relação ao fixo. Para mensagens grandes, isso é substancial.
Taxa de entropia do inglês. Shannon estimou a entropia do inglês escrito em torno de 1,0 a 1,3 bits por caractere, apesar de usar códigos ASCII de 5 bits. Essa razão de 4:1 reflete a enorme redundância na linguagem natural - letras comuns se agrupam, palavras se repetem, a gramática limita as sequências.
A Compressão Não Pode Superar a Entropia
Taxa de compressão: H / (extensão do código de blocos). Para nosso exemplo: 1,75/2,0 = 0,875 - 87,5% de eficiência.
É possível compressar ainda mais? Somente usando contexto: se você codificar pares ou tríades de símbolos juntos, a entropia conjunta H(X,Y) pode ser menor do que 2·H(X) devido a dependências estatísticas. Este é a extensão do teorema de codificação sem ruído para n-grams.