Quanto vale uma surpresa

Como funciona

A moeda. A surpresa de um resultado de probabilidade $p$ é $-{\log }_{2}p$ bits: zero para o certo, um bit para cara numa moeda justa, 3,32 bits para o resultado de 10%. A figura desenha cada resultado como um retângulo de largura $p$ e altura $-{\log }_{2}p$. A área de cada um é $-p{\log }_{2}p$, e a soma das áreas é a entropia de Shannon:

$$H=-\sum _{x}p(x){\log }_{2}p(x).$$

Resultados raros têm retângulos altos e finos; comuns, baixos e largos. Com a moeda justa, os dois retângulos são iguais e $H=1$ bit — o máximo para duas alternativas. Lance a moeda: cada lançamento ocupa um bit na fila, mas a surpresa somada, dividida pelo número de lançamentos, se aproxima de $H$, que pode ser bem menos.

O código. Digite qualquer texto. A simulação conta cada símbolo, calcula a entropia e monta o código de Huffman: junta repetidamente os dois símbolos (ou grupos) mais raros, até sobrar uma árvore; o caminho até cada folha é o código. Símbolos frequentes ficam com códigos curtos; raros, com longos. Nenhum código é começo de outro, então a sequência de bits se decodifica sem separadores. O comprimento médio fica sempre entre $H$ e $H+1$ — e o teorema de Shannon diz que nenhum código sem perda faz melhor que $H$ em média. A frase de exemplo tem 24 símbolos diferentes, 3,96 bits de entropia por caractere e um código de Huffman de 3,99 bits: menos da metade dos 8 bits por caractere de um arquivo comum.

O canal com ruído. “NABLA” vira 40 bits e atravessa um canal que vira cada bit com probabilidade $p$. Sem código, cada erro vira uma letra trocada. Mande cada bit três vezes e decida pela maioria: o erro por bit cai de $p$ para $3p^2-2p^3$ — de 10% para 2,8% — ao custo de mandar três vezes mais. Shannon provou que dá para fazer muito melhor: qualquer taxa abaixo da capacidade $C=1-H(p)$ pode ser transmitida com erro tão pequeno quanto se queira. Com $p$ = 10%, $C\approx 0,53$ bit por uso — bem acima do 1/3 do código de repetição.