Códigos, a Desigualdade de Kraft e o Limite de Shannon

Item da lista de Ilya: nenhum, diretamente. Este artigo constrói o pré-requisito de teoria da informação que o tutorial de Minimum Description Length de Rissanen — tratado em IL04 e IL05 — assume conhecido do leitor.

Índice da Série: A Lista de Ilya

• 1. A Lista, a Tese e Por Que Ela Começa em Compressão
• 2. Códigos, a Desigualdade de Kraft e o Limite de Shannon (Você está aqui)

O artigo anterior usou uma fórmula sem provar que ela significava alguma coisa. Definimos o comprimento de descrição de uma sequência $s$ sob um modelo $Q$ como

e a atenta leitora que aceitou aquilo foi generosa. Nada garantia que existisse um código capaz de atingir esse número. Poderia ser uma quantidade de conveniência, elegante e inatingível, como a média de filhos por casal.

Este artigo paga a dívida em três parcelas. Primeiro, mostramos que nem todo conjunto de comprimentos é realizável, e caracterizamos exatamente quais são — a desigualdade de Kraft. Depois, provamos que a entropia é um piso que nenhum código honesto atravessa. Por fim, exibimos um código que chega a menos de um bit desse piso, e argumentamos que um bit é caro demais para o nosso ramo.

A insuficiência do terceiro resultado é o assunto do artigo seguinte. Começamos, porém, por um problema mais modesto: saber onde uma palavra termina.

1. O problema de saber onde a palavra termina

Considere três símbolos, $A$, $B$ e $C$, e o código

Codifiquemos a mensagem $AC$: emitimos 0 e depois 11, obtendo 011. Agora codifiquemos $BA$… não, espere. $B$ é 01 e $A$ é 0, o que dá 010. Tudo bem. Tentemos $ACA$: 0 11 0, ou 0110. E $BC$? 01 11, ou 0111.

O problema aparece na decodificação. Recebendo 011, a destinatária não sabe se o primeiro símbolo é $A$ — porque 0 é uma palavra completa — ou se está no meio de um $B$, cuja palavra é 01. Ela precisa olhar adiante para decidir, e em códigos mais perversos precisa olhar até o fim da mensagem.

Antes de consertar isso, três definições, na ordem em que serão usadas.

A extensão de $\mathcal{C}$ é a função que leva sequências de símbolos em sequências de bits por concatenação: $\mathcal{C}(x_0 x_1 \ldots x_{n-1}) = \mathcal{C}(x_0)\,\mathcal{C}(x_1)\cdots\mathcal{C}(x_{n-1})$. Nenhum separador é emitido — se fosse, ele custaria bits e precisaria entrar na conta.

Um código é unicamente decodificável quando sua extensão é injetiva: duas sequências distintas de símbolos nunca produzem a mesma sequência de bits.

O código acima é unicamente decodificável, aliás. Mas exige lookahead, e essa é a propriedade que queremos eliminar.

Um código é de prefixo, ou instantâneo, quando nenhuma palavra-código é prefixo de outra. Em {0, 01, 11}, a palavra 0 é prefixo de 01, e o código falha no teste. Em {0, 10, 11}, nenhuma é prefixo de nenhuma, e o código passa.

A vantagem é imediata e vale a pena enunciar com cuidado, porque é a razão de a propriedade existir: em um código de prefixo, assim que os bits lidos formam uma palavra-código, essa palavra é o símbolo. Não pode ser o começo de outra, porque nenhuma outra a tem como prefixo. A decodificação é local, sem memória e sem lookahead — daí o nome instantâneo.

Resta a pergunta que ocupa o resto do artigo: quanto custa essa comodidade?

2. A árvore é o código

Todo código de prefixo é uma árvore binária, e a recíproca também vale. Ver isso é ver a metade do artigo.

Construa a árvore em que cada nó tem dois filhos, o esquerdo rotulado 0 e o direito rotulado 1. Cada nó corresponde à cadeia de bits que se lê no caminho da raiz até ele. Um código atribui, a cada símbolo, um nó dessa árvore.

A condição de prefixo tem tradução exata nessa linguagem: a palavra $u$ é prefixo da palavra $v$ se e somente se o nó $u$ é ancestral do nó $v$. Portanto, um código é de prefixo se e somente se nenhuma palavra-código é ancestral de outra — isto é, todas as palavras são folhas de uma mesma árvore, e nenhum nó interno é palavra.

A figura sugere a ideia que vai gerar tudo o mais. Escolher uma folha na profundidade $\ell$ consome uma fração da árvore: todos os descendentes daquele nó ficam proibidos, e eles são exatamente a fração $2^{-\ell}$ das folhas de qualquer nível abaixo. Uma palavra curta é cara em capacidade; uma palavra longa é barata.

No painel esquerdo, os comprimentos $(1,2,3,4,4)$ consomem

a árvore inteira. No painel direito, $(1,2,3,4,5)$ consomem $31/32$, e sobra uma posição de profundidade cinco sem dono — capacidade paga e não usada.

Falta transformar essa contabilidade informal em teorema.

3. Kraft, na direção que se prova em um parágrafo

Teorema (Kraft, direção necessária). Se existe código de prefixo binário com comprimentos $\ell_0, \ldots, \ell_{m-1}$, então

A prova cabe em um parágrafo e usa intervalos, não árvores. A cada palavra-código $w = w_0 w_1 \ldots w_{\ell-1}$ associe o número real $0{,}w$ na base dois, isto é, $\sum_{j} w_j 2^{-(j+1)}$, e o intervalo

de comprimento exatamente $2^{-\ell}$. Um número real cai em $I(w)$ se e somente se sua expansão binária começa por $w$. Logo, se $u$ não é prefixo de $v$ e $v$ não é prefixo de $u$, os intervalos $I(u)$ e $I(v)$ são disjuntos. Em um código de prefixo, todos os $m$ intervalos são dois a dois disjuntos e vivem dentro de $[0,1)$, cujo comprimento é 1. Somando comprimentos:

Vale sublinhar o que essa prova custou: nada. Nenhuma indução, nenhuma construção, nenhum caso a analisar. A condição de prefixo virou disjunção de intervalos, e disjunção de intervalos virou soma de comprimentos.

Apliquemos o teste a seis conjuntos de comprimentos, todos com cinco símbolos.

O caso $(2,2,2,2,2)$ merece dois segundos de atenção, porque a impossibilidade se enxerga sem álgebra nenhuma: existem quatro cadeias de dois bits — 00, 01, 10, 11 — e queremos cinco palavras. Não há como. A desigualdade de Kraft é a generalização dessa observação óbvia para comprimentos que não são todos iguais, e é apenas isso.

4. Kraft na direção difícil, e por que ela importa

A recíproca também vale, e é ela que torna o teorema útil.

Teorema (Kraft, direção suficiente). Se $\ell_0 \le \ell_1 \le \cdots \le \ell_{m-1}$ satisfazem $K(\ell) \le 1$, então existe código de prefixo com esses comprimentos.

A construção é gulosa. Percorra os comprimentos em ordem crescente, mantendo um contador $c$ que começa em zero. Para o símbolo $i$, tome os $\ell_i$ primeiros bits da expansão binária de $c$, use-os como palavra-código, e some $2^{-\ell_i}$ a $c$. A hipótese $K(\ell) \le 1$ garante que $c$ nunca chega a 1, e portanto nunca falta espaço; a ordem crescente garante que nenhuma palavra já emitida é prefixo da nova, porque toda palavra anterior é mais curta e corresponde a um intervalo à esquerda, já ultrapassado pelo contador. É a mesma prova de intervalos da seção anterior, lida de trás para a frente.

Até aqui, tudo o que dissemos vale só para códigos de prefixo. E a leitora tem o direito de desconfiar: talvez exista, entre os códigos unicamente decodificáveis mas não instantâneos — como o {0, 01, 11} da Seção 1 —, algum que consiga comprimentos menores em troca do lookahead. É uma troca plausível: aceitar decodificação mais lenta em troca de mensagens mais curtas.

Não existe. E é este o resultado que faz o teorema valer a pena:

Teorema (McMillan, 1956). Todo código unicamente decodificável satisfaz $K(\ell) \le 1$.

A ideia da prova é bonita o suficiente para ser contada mesmo sem os detalhes. Considere a $n$-ésima potência da soma de Kraft, $K(\ell)^n$. Expandindo o produto, cada termo corresponde a uma sequência de $n$ símbolos, e contribui com $2^{-(\text{comprimento total da codificação})}$. Agrupando por comprimento total $L$, o coeficiente de $2^{-L}$ é o número de sequências de $n$ símbolos cuja codificação tem exatamente $L$ bits. Como o código é unicamente decodificável, essas sequências têm codificações distintas, e não pode haver mais do que $2^L$ delas. Cada grupo contribui, então, com no máximo 1, e como $L$ vai de $n\ell_{\min}$ a $n\ell_{\max}$, obtém-se $K(\ell)^n \le n\,\ell_{\max}$. Se fosse $K(\ell) > 1$, o lado esquerdo cresceria exponencialmente em $n$ e o direito apenas linearmente, o que é impossível para $n$ grande. Logo $K(\ell) \le 1$. Cover e Thomas trazem a versão completa.

Junte os três teoremas e leia a conclusão em voz alta: os comprimentos realizáveis por códigos unicamente decodificáveis são exatamente os realizáveis por códigos de prefixo. Exigir decodificação instantânea não custa um único bit. A comodidade que a Seção 1 pediu é de graça, e não há mais razão para considerar qualquer outro tipo de código.

5. Entropia é o piso

Sabemos quais comprimentos existem. Falta escolher os melhores.

Dada uma distribuição $p = (p_0, \ldots, p_{m-1})$ sobre o alfabeto, o comprimento médio de um código é

e a entropia da fonte, em bits, é

A série Transformers já derivou a entropia pelo lado probabilístico, em A Probabilidade da Linguagem. Aqui ela reaparece do lado da codificação, e a coincidência não é coincidência.

Teorema (codificação de fonte, sem ruído). Para todo código unicamente decodificável, $\bar{L} \ge H(p)$, com igualdade se e somente se $\ell_i = -\log_2 p_i$ para todo $i$.

A prova é uma linha, se a escrevermos na ordem certa. Defina $q_i = 2^{-\ell_i} / K(\ell)$, que é uma distribuição de probabilidade por construção, já que os $q_i$ são positivos e somam 1. Então

O primeiro termo é a divergência de Kullback–Leibler, que é não negativa e nula apenas quando $p = q$. O segundo é $-\log_2 K(\ell) \ge 0$, porque $K(\ell) \le 1$ por Kraft. A soma de dois termos não negativos é não negativa, e é nula só quando ambos o são: $K(\ell) = 1$ e $q_i = p_i$, isto é, $2^{-\ell_i} = p_i$, ou $\ell_i = -\log_2 p_i$. $\blacksquare$

A decomposição merece ser lida com atenção, porque ela diz de onde vem cada bit desperdiçado. Há duas fontes de desperdício, e só duas: usar um código incompleto, com $K(\ell) < 1$, e usar comprimentos que correspondem à distribuição errada. O primeiro desperdício é bobo e sempre evitável; o segundo é a distância entre o que o modelo acredita e o que a fonte faz — exatamente a divergência KL, aparecendo aqui como número de bits extras por símbolo.

Isso também responde, de passagem, à pergunta que ficou pendente no artigo anterior. Entropia cruzada não é uma perda escolhida por conveniência matemática: é o comprimento médio de um código construído para a distribuição $q$ e usado numa fonte que segue $p$. Minimizar entropia cruzada é encurtar o arquivo.

A condição de igualdade tem uma consequência incômoda. Ela exige $\ell_i = -\log_2 p_i$, e $\ell_i$ é inteiro. Logo a igualdade só é possível se toda probabilidade for potência de dois — se a distribuição for diádica. Vejamos o que acontece quando não é.

6. Huffman, e por que ele é ótimo

O algoritmo de Huffman constrói a árvore de baixo para cima. Mantenha uma coleção de nós, um por símbolo, com peso igual à sua probabilidade. Enquanto houver mais de um nó, retire os dois de menor peso, crie um pai cujo peso é a soma, e devolva o pai à coleção. As folhas mais profundas são, por construção, os símbolos menos prováveis.

Uma advertência prática antes dos exemplos: quando dois nós empatam em peso, a escolha é arbitrária, e árvores diferentes resultam. Elas têm o mesmo comprimento médio — o algoritmo continua ótimo — mas os comprimentos individuais podem diferir. Para que as tabelas abaixo sejam reproduzíveis, fixamos a regra de desempate: entre nós de mesmo peso, vence o que contém o símbolo de menor índice. O programa da Seção 7 implementa exatamente essa regra.

6.1 O caso diádico

A coluna $-\log_2 p_i$ é inteira, e o Huffman a reproduz exatamente. A soma de Kraft dá 1, e

Este é o painel esquerdo da figura da Seção 2, agora com nomes e números.

6.2 O caso não diádico

Kraft dá 1 outra vez, mas agora

Olhe a primeira linha. O símbolo $A$ merecia $1{,}3219$ bit e recebeu 2. O símbolo $D$ merecia $3{,}3219$ e recebeu 3 — levou vantagem. No agregado, a fonte perde setenta e oito milésimos de bit por símbolo.

Vale ser preciso sobre a natureza dessa perda, porque é ela que motiva o próximo artigo. A folga não é defeito do algoritmo de Huffman. Huffman é ótimo: nenhum outro código que atribua uma palavra inteira a cada símbolo tem comprimento médio menor. A folga é defeito do formato da solução. Enquanto a resposta for “um número inteiro de bits por símbolo”, e $-\log_2 p_i$ não for inteiro, sobra resto.

6.3 A cota superior

O código de Shannon fecha o cerco. Escolha $\ell_i = \lceil -\log_2 p_i \rceil$. Como $\ell_i \ge -\log_2 p_i$, temos $2^{-\ell_i} \le p_i$, e portanto $K(\ell) \le \sum_i p_i = 1$: os comprimentos são realizáveis. E como $\ell_i < -\log_2 p_i + 1$,

Como Huffman é ótimo, ele é no mínimo tão bom quanto Shannon. Juntando com o piso da Seção 5:

O resultado é bom. A pergunta que resta é se um bit é pouco.

6.4 O laboratório

O painel de cima refaz os dois casos acima e qualquer outro que a leitora quiser: ajuste as contagens e veja a árvore, os comprimentos e a folga se reorganizarem. Vale procurar deliberadamente a folga zero — ela aparece quando, e só quando, todas as contagens são potências de dois com soma potência de dois.

O painel de baixo abandona o Huffman e aceita comprimentos digitados à mão. Experimente $(2,2,2,2,2)$ e observe a barra de capacidade estourar: cinco palavras de dois bits em um espaço que comporta quatro. E experimente $(1,2,3,4,5)$, que é válido mas desperdiça $1/32$ — o laboratório explica por que todo código com $K < 1$ pode ser encurtado, que é o Exercício 9.

7. O programa

O código abaixo constrói o Huffman com desempate determinístico, verifica Kraft em aritmética inteira exata, e imprime as tabelas das seções anteriores. Compilação de referência:

g++ -std=c++23 -O3 -march=native -Wall -Wextra IL02_huffman.cpp -o IL02

Duas decisões de implementação merecem comentário, porque são o tipo de coisa que separa um programa didático de um programa correto.

A primeira: os pesos são contagens inteiras, não probabilidades em ponto flutuante. A distribuição $(2/5, 1/5, 1/5, 1/10, 1/10)$ entra como $(4, 2, 2, 1, 1)$. A razão não é economia: é que somas de inteiros nunca empatam por erro de arredondamento. Com double, dois nós que deveriam ter peso idêntico podem diferir na décima quinta casa, a fila de prioridade escolhe pela diferença espúria, e o mesmo programa produz árvores diferentes em máquinas diferentes. Com inteiros, o empate é um empate, e a regra de desempate declarada decide.

A segunda: a verificação de Kraft é feita em inteiros. Em vez de somar $2^{-\ell_i}$ em ponto flutuante e comparar com 1 — comparação que pode falhar por um ulp justamente no caso mais interessante, o da igualdade —, colocamos tudo sobre o denominador comum $2^{\ell_{\max}}$ e somamos os numeradores $2^{\ell_{\max}-\ell_i}$, que são inteiros. A comparação com 1 vira comparação de dois std::uint64_t, e é exata.

struct Kraft {
    std::uint64_t numerador;
    std::uint64_t denominador;
    [[nodiscard]] bool valida() const { return numerador <= denominador; }
    [[nodiscard]] bool exaure() const { return numerador == denominador; }
};

[[nodiscard]] Kraft kraft(std::span<const unsigned> comprimento) {
    const unsigned lmax = *std::ranges::max_element(comprimento);
    if (lmax >= 63) return Kraft{1, 0};          // denominador zero sinaliza estouro
    const std::uint64_t den = std::uint64_t{1} << lmax;
    std::uint64_t num = 0;
    for (const auto l : comprimento) num += std::uint64_t{1} << (lmax - l);
    return Kraft{num, den};
}

A saída do programa, na íntegra para o caso não diádico:

--- nao diadico  p = (2/5, 1/5, 1/5, 1/10, 1/10) ---
  simbolo  contagem         p    -log2 p   comprimento
     A         4    0,4000     1,3219            2
     B         2    0,2000     2,3219            2
     C         2    0,2000     2,3219            2
     D         1    0,1000     3,3219            3
     E         1    0,1000     3,3219            3
  Kraft            : 8/8  (valida: sim, exaure: sim)
  H(p)             : 2,121928 bits
  L medio          : 2,200000 bits
  folga            : 0,078072 bit por simbolo
  H <= L < H + 1   : sim
  mensagem de 10 simbolos: 22 bits (piso de entropia 21,2193)

O arquivo completo está em lista_ilya/codigo/IL02_huffman.cpp.

8. Um bit de folga é muito ou pouco?

Chegamos ao ponto em que o resultado bonito revela seu preço.

A folga de Huffman é por símbolo. Isso significa que seu peso relativo depende inteiramente de quão pequena é a entropia por símbolo — e em aprendizado de máquina ela é sempre pequena.

Em um texto em português tratado como sequência de caracteres, a entropia condicional ronda dois bits por caractere. Um bit de folga seria cinquenta por cento de desperdício. Em um modelo de linguagem moderno que atinge $1{,}0$ bit por token, seria cem por cento: o arquivo dobraria de tamanho. Um resultado que garante “no máximo o dobro do ótimo” não é um resultado do qual se possa depender.

O caso concreto que a série carrega desde o artigo anterior:

Meio bit jogado fora em onze símbolos. Pouco em termos absolutos, dois por cento e meio em termos relativos, e um desastre se o mesmo percentual se repetir em dez bilhões de tokens.

A saída aparente é bloquear símbolos: codificar pares, ou trios, em vez de símbolos isolados. A cota do código de Shannon aplicada a blocos de tamanho $n$ dá folga menor que $1/n$ bit por símbolo original, e a folga parece se dissolver. Parece.

Blocando a fonte não diádica da Seção 6.2, com símbolos independentes:

Duas coisas nessa tabela desmontam a esperança.

A primeira é que a folga não é monótona em $n$. Ela cai para três milésimos de bit em $n = 3$ e volta a subir para dezoito milésimos em $n = 4$. A cota $1/n$ é uma cota superior, não uma previsão: ela promete que a folga estará abaixo de certo valor, e não que diminuirá a cada passo. Quem planejar um sistema de compressão contando com melhora monótona ao aumentar o bloco vai ter uma tarde ruim.

A segunda é o preço. Para uma fonte de cinco símbolos, blocos de tamanho $n$ exigem um alfabeto de $5^n$ palavras, e a tabela de Huffman precisa guardar todas. Em $n = 6$ já são quinze mil entradas para ganhar sete centésimos de bit. Para um vocabulário de linguagem com $50\,257$ tokens, blocos de dois já dariam dois bilhões e meio de entradas. A blocagem funciona no papel e não sobrevive ao primeiro contato com a memória.

Há uma terceira objeção, mais séria que as duas, e ela não é sobre tamanho. Huffman precisa da tabela inteira antes de emitir o primeiro bit. Um modelo que muda de opinião a cada símbolo — que é a definição de um modelo condicional, e portanto de qualquer modelo interessante — obrigaria a reconstruir a árvore a cada passo. O artigo anterior mostrou que trocar o modelo de ordem zero por um de ordem um valia um fator de sessenta e três. Nenhum ganho de codificação chega perto disso, e um codificador que dificulte a troca de modelo está otimizando a coisa errada.

O próximo artigo troca a pergunta. Em vez de “qual a melhor palavra-código para cada símbolo?”, pergunta “qual o melhor número real para a mensagem inteira?”. A resposta elimina a folga por símbolo, separa o modelo do codificador, e transforma a fórmula do artigo anterior em identidade exata.

A folga de um bit por símbolo é o preço de insistir que cada símbolo tenha sua palavra. A saída não é um código melhor; é parar de atribuir palavras.

9. Exercícios

1. Calcule $K(\ell)$ para $\ell = (1,3,3,3,3)$ e decida se existe código de prefixo com esses comprimentos.

2. Construa o código de Huffman de $p = (1/3, 1/3, 1/6, 1/6)$ e calcule $\bar{L}$, $H(p)$ e a folga.

3. Verifique que os comprimentos $(1,3,4,4,2)$ de ABRACADABRA satisfazem Kraft com igualdade.

4. Desenhe a árvore de $\ell = (1,2,3,4,5)$ e identifique a folha desperdiçada. Que fração da árvore ela representa?

5. Mostre que, para $p$ diádica, o código de Shannon e o de Huffman têm o mesmo comprimento médio.

6. Com três símbolos, o Huffman sempre produz comprimentos $(1,2,2)$. Use esse fato para determinar o supremo da folga sobre todas as distribuições de três símbolos, e diga se ele é atingido.

7. Prove a direção necessária de Kraft pelo argumento de intervalos, sem consultar o texto.

8. Prove que, se $\ell_i = \lceil -\log_2 p_i \rceil$, então $K(\ell) \le 1$ e $\bar{L} < H(p) + 1$.

9. Um código com $K(\ell) < 1$ estritamente é sempre subótimo? Prove ou exiba um contraexemplo.

10. Determine o menor tamanho de bloco que leva a folga da fonte não diádica abaixo de $0{,}01$ bit por símbolo, e o tamanho de alfabeto correspondente. A resposta é o que a cota $1/n$ sugeriria?

10. Soluções

1. $K = \frac12 + 4 \cdot \frac18 = \frac12 + \frac12 = 1$. Existe código de prefixo, e ele exaure a capacidade: uma palavra de um bit e quatro de três.

2. As duas menores probabilidades são $1/6$ e $1/6$; funde-se, gerando um nó de peso $1/3$. Agora há três nós de peso $1/3$. Funde-se dois deles, gerando $2/3$, e por fim funde-se com o restante. O resultado surpreende quem espera comprimentos desiguais:

Com $H(p) = \frac23\log_2 3 + \frac13\log_2 6 = 1{,}918296$, a folga é $0{,}081704$ bit por símbolo. Repare que a árvore é perfeitamente balanceada apesar de a distribuição não ser uniforme — o Huffman não premia diferença de probabilidade quando ela não é suficiente para pagar um nível de árvore.

3. $\frac12 + \frac18 + \frac1{16} + \frac1{16} + \frac14$. Sobre o denominador comum 16: $\frac{8+2+1+1+4}{16} = \frac{16}{16} = 1$. Igualdade.

4. A árvore é o painel direito da figura da Seção 2. As palavras ocupam a folha esquerda de cada nível até a profundidade 4, e na profundidade 5 há duas posições, das quais só uma é usada. A folha desperdiçada representa $2^{-5} = 1/32$ da árvore, que é exatamente $1 - \frac{31}{32}$.

5. Se $p$ é diádica, $p_i = 2^{-k_i}$ para inteiros $k_i$, e $-\log_2 p_i = k_i$ já é inteiro. O código de Shannon usa $\ell_i = \lceil k_i \rceil = k_i$, e $\bar{L} = \sum_i p_i k_i = H(p)$. Pelo teorema da Seção 5, $H(p)$ é um piso, e o Huffman é ótimo, logo $\bar{L}_{\text{Huffman}} = H(p)$ também. Os dois códigos atingem o piso e portanto têm o mesmo comprimento médio, ainda que possam diferir na atribuição de palavras.

6. Com comprimentos $(1,2,2)$ e $p_0 \ge p_1 \ge p_2$,

de modo que a folga é $2 - p_0 - H(p)$. Fazendo $p_0 \to 1$ com $p_1 = p_2 = (1-p_0)/2$, temos $\bar{L} \to 1$ e $H(p) \to 0$:

O supremo é 1 bit, aproximado mas nunca atingido, já que $p_0 = 1$ não é uma distribuição sobre três símbolos com $p_1, p_2 > 0$. Isso mostra que a cota $\bar{L} < H + 1$ é apertada: não existe constante menor que 1 que sirva para toda distribuição.

Note também de onde vem o desperdício: quando um símbolo é quase certo, ele merece quase zero bit, e o menor comprimento disponível é 1. Todo o bit é perda.

7. Está na Seção 3. O núcleo é: palavra de comprimento $\ell$ reserva o intervalo diádico de comprimento $2^{-\ell}$ cujos elementos têm aquela palavra como prefixo binário; a condição de prefixo torna os intervalos disjuntos; intervalos disjuntos dentro de $[0,1)$ têm comprimentos que somam no máximo 1.

8. Do teto vem $\ell_i \ge -\log_2 p_i$, logo $2^{-\ell_i} \le 2^{\log_2 p_i} = p_i$, e somando, $K(\ell) \le \sum_i p_i = 1$. Do teto vem também $\ell_i < -\log_2 p_i + 1$, logo

Conferido numericamente em quatro distribuições sorteadas com seis símbolos: em todas, $K(\ell) = 0{,}75 \le 1$ e $\bar{L} < H(p) + 1$.

9. Sim, sempre subótimo, e a prova é curta. Seja $\ell_{\max}$ o maior comprimento. Todo termo $2^{-\ell_i}$ é múltiplo inteiro de $2^{-\ell_{\max}}$, portanto $K(\ell)$ também é. Se $K(\ell) < 1$, então $K(\ell) \le 1 - 2^{-\ell_{\max}}$. Encurtando em uma unidade o símbolo de comprimento máximo, sua contribuição passa de $2^{-\ell_{\max}}$ para $2^{-\ell_{\max}+1}$, um aumento de exatamente $2^{-\ell_{\max}}$, e a nova soma é

Por Kraft, existe código de prefixo com $\ell’$, e ele tem comprimento médio estritamente menor, já que um $\ell_i$ diminuiu e nenhum aumentou. Verificado em quatro casos:

O terceiro caso mostra que o processo pode precisar ser repetido: $(1,3)$ melhora para $(1,2)$, que ainda tem $K < 1$ e melhora de novo para $(1,1)$.

10. A resposta é $n = 3$, com alfabeto de 125 palavras, que dá folga de $0{,}003405$ bit por símbolo.

E não, não é o que a cota $1/n$ sugeriria. A cota em $n = 3$ promete apenas folga abaixo de $0{,}3333$, e o valor real é cem vezes menor. Pior para a intuição: em $n = 4$ a folga sobe para $0{,}018472$, voltando acima do alvo. A tabela completa está na Seção 8.

A moral é que $1/n$ limita a folga sem descrevê-la. O valor real depende de quão perto as probabilidades do bloco chegam de potências de dois, e essa proximidade oscila de forma irregular conforme $n$ cresce. Projetar um sistema supondo decaimento suave é confundir uma cota com uma curva.

Progresso na lista: este artigo não fecha nenhum item — é pré-requisito. Continuam 0 de 30 itens estudados, 30 pela frente.

11. Acrônimos e Abreviações neste artigo

A seguir está a lista de todos os acrônimos e abreviações identificados no texto, organizados em ordem alfabética com o termo original em inglês e a tradução para o português:

12. Referências

COVER, T. M.; THOMAS, J. A. Elements of Information Theory. 2. ed. Hoboken: Wiley, 2006.

GALLAGER, R. G. Variations on a Theme by Huffman. IEEE Transactions on Information Theory, v. 24, n. 6, p. 668–674, 1978.

HUFFMAN, D. A. A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the IRE, v. 40, n. 9, p. 1098–1101, 1952.

KRAFT, L. G. A Device for Quantizing, Grouping, and Coding Amplitude Modulated Pulses. Dissertação (Mestrado) — Massachusetts Institute of Technology, Cambridge, 1949.

MacKAY, D. J. C. Information Theory, Inference, and Learning Algorithms. Cambridge: Cambridge University Press, 2003.

McMILLAN, B. Two Inequalities Implied by Unique Decipherability. IRE Transactions on Information Theory, v. 2, n. 4, p. 115–116, 1956.

RISSANEN, J. Modeling by Shortest Data Description. Automatica, v. 14, n. 5, p. 465–471, 1978.

SHANNON, C. E. A Mathematical Theory of Communication. Bell System Technical Journal, v. 27, n. 3, p. 379–423, 1948.