Playground de codificação de entropia

Explore como diferentes distribuições de símbolos afetam a entropia de Shannon, compare os limites da codificação de Huffman e aprenda como a entropia rege as funções de perda e a incerteza de vocabulário em modelos de linguagem de IA (LLMs) modernos.

Valores iniciais — Playground de codificação de entropia

Parâmetro de distribuição (λ)	1.5

Altere qualquer controlo acima e os resultados são recalculados.

A carregar a simulação interativa...

Bits inteiros são o que Huffman paga 🖖

A codificação de entropia explora a redundância estatística para representar mensagens com menos bits. O teorema da codificação de fonte de Shannon afirma que o comprimento médio mínimo absoluto de qualquer código sem perdas é a entropia de Shannon: H(X) = −Σ p_i log₂ p_i. A codificação de Huffman é ótima para um dado alfabeto quando os símbolos são codificados individualmente, mas está restrita a palavras-código de comprimento inteiro. Essa restrição de comprimento inteiro significa que o Huffman pode se desviar da entropia teórica em até 0,086 bits/símbolo (e muito mais se algum símbolo tiver p_i ≈ 1). A codificação aritmética (por exemplo, ANS) supera esse limite mapeando toda a sequência em intervalos fracionários.

Conexão com LLMs e IA: Nos modelos de linguagem (LLMs) modernos, a entropia é um conceito central tanto no treinamento quanto na geração. Os LLMs são treinados minimizando a perda de entropia cruzada entre suas previsões de vocabulário e o texto real. Durante a geração (inferência), o LLM produz uma distribuição de probabilidade sobre seu vocabulário para o próximo token. A entropia dessa distribuição mede a incerteza de previsão do modelo: uma distribuição plana (alta entropia) gera texto criativo ou aleatório, enquanto uma distribuição pontuda (baixa entropia) gera texto altamente previsível. Parâmetros de amostragem como a temperatura escalam diretamente essa entropia (temperatura mais baixa reduz a entropia, mais alta a aumenta), enquanto a amostragem nucleus (Top-p) limita dinamicamente a probabilidade cumulativa para cortar as caudas de alta entropia.

Por que símbolos raros custam mais bits 🖖

A verdadeira lição desta ferramenta: o número ideal de bits para um símbolo é a sua surpresa, −log₂ p. Um símbolo que aparece metade das vezes merece 1 bit; um com probabilidade de 1 em 1000, cerca de 10 bits. A entropia é apenas a surpresa média entre todos os símbolos. Por isso as distribuições assimétricas (como as predefinições laplaciana ou exponencial) comprimem bem, enquanto um alfabeto uniforme não — quando tudo é igualmente provável, não há redundância a remover.

Morse: codificação de entropia antes de Shannon 🖖

O código Morse atribuiu o sinal mais curto, um único ponto, ao E, a letra mais frequente do inglês, e sequências longas às raras como Q e Z. Para escolher os comprimentos, dizem que Alfred Vail contou os tipos móveis na caixa de uma tipografia para estimar as frequências das letras. Era codificação de comprimento variável funcionando já na década de 1840 — quase um século antes de Shannon formalizar, em 1948, por que ela funciona.

UMA ETAPA DE UMA CADEIA — O QUE ENTRA, O QUE SAI E O QUE QUEBRA DEPOIS

Onde isto fica no pipeline de codificação

Um codificador de vídeo não é um algoritmo, mas oito etapas numa ordem fixa, e a ordem não é arbitrária: cada etapa existe porque a anterior tornou o seu trabalho possível. Esta ferramenta modela uma delas. A cadeia abaixo liga às outras sete.

Playground de codificação de entropia — empacota os símbolos quantizados em tão poucos bits quanto a sua estatística permite

O que entra: Um fluxo de inteiros quantizados, fortemente enviesado para zero.
O que sai: O bitstream final. Aqui nada é descartado.
O que a etapa seguinte pressupõe: Nada a jusante — esta é a última etapa de codificação. O que ela pressupõe está a montante: que a distribuição de símbolos já foi tornada desigual para ela.
O que dá errado aqui: Nenhum codificador entrópico consegue bater a entropia de Shannon do que lhe é entregue, então o seu teto é fixado inteiramente pelas etapas anteriores. Rodá-lo sobre coeficientes não quantizados encontra pouca redundância, e essa é a razão de o passo com perda vir primeiro e não por último.

Etapa anterior: Quantização Etapa seguinte: Controle de taxa

Problema resolvido na íntegra

O espaço restante para um algoritmo mais engenhoso do que o de Huffman em 16 símbolos 6 passos
16 símbolos, distribuição de Laplace, entropia de 3,010 bits. Huffman obtém 3,012. Determine quanta margem resta para um algoritmo mais inteligente.
1. A entropia é a surpresa média, em bits, de um símbolo extraído desta distribuição. É uma propriedade exclusiva das probabilidades e não depende de qualquer código.
  
  $H (X) = - i = 1 \sum N p_{i} lo g_{2} p_{i} = 3.010 bits/symbol (N = 16, Laplacian, λ = 1.5)$
2. A alternativa ingénua atribui a cada símbolo o mesmo número de bits, e 16 símbolos necessitam de 4. Esta é a linha de base em relação à qual a poupança é medida.
  
  $L_{fixed} = ⌈ lo g_{2} N ⌉ = ⌈ lo g_{2} 16 ⌉ = 4.0 bits/symbol$
3. Huffman atribui códigos curtos a símbolos frequentes e longos a símbolos raros, sendo a média o comprimento ponderado pelas probabilidades.
  
  $\overset{ˉ}{L} = \sum p_{i} L_{i} = 3.012 bits/symbol$
4. A poupança compara os dois comprimentos de código, não o código com a entropia — razão pela qual é uma afirmação sobre esta alternativa e não sobre o limite.
  
  $savings = \frac{4.0 - 3.012}{4.0} = 24.7%$
5. Agora compare em relação ao limite. O teorema da codificação de fonte de Shannon estabelece que nenhum código de prefixo pode ficar abaixo de H, e Huffman garante um valor inferior a H + 1.
  
  $H \leq \overset{ˉ}{L} < H + 1 (Shannon); \overset{ˉ}{L} - H = 3.012 - 3.010 = 0.002 bits$
6. Exprima a margem restante sob a forma de fração e a questão da otimização responde por si mesma.
  
  $\frac{0.002}{3.010} = 0.07% above the floor$
Resposta

0,002 bits por símbolo, ou 0,07%. O teorema de Shannon delimita qualquer código de prefixo entre H e H + 1. Sendo o de Huffman comprovadamente ótimo nesse grupo, nenhum código de prefixo fará melhor do que 3,012 neste texto. A redução de 24,7% face à codificação de comprimento fixo é real, e os 0,07% restantes traduzem a totalidade do que uma engenharia mais apurada jamais poderia acrescentar. A partir daqui, a compressão só ganha terreno ao alterarmos o modelo em vez do código: caso os símbolos adjacentes se correlacionem, a entropia da distribuição condicional desce abaixo de 3,010. Trata-se de uma grandeza completamente diferente.

$\overset{ˉ}{L} - H = 0.002 bits : Huffman is 0.07% off optimal here$

Referências (1)

Insight block 2 — entropy as average surprise, and the limit Huffman cannot beat: C. E. Shannon, "A Mathematical Theory of Communication." Bell System Technical Journal 27(3), 379–423, 1948.

Pela equipa 42Math · Atualizado 2026-07-29

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Computação →

Problemas de exemplo

Uniforme 8 - Fonte uniforme de 8 símbolos: H=3 bits, ganho de codificação nulo — a entropia é igual ao código de comprimento fixo
Tipo DCT (Laplace) - Laplaciana tipo DCT: H≈2.1 bits, economia de 23% — a maioria dos coeficientes AC de vídeo se concentra perto de zero
Tipo vetor de movimento - Exponencial do tipo vetor de movimento: H≈2.3 bits, economia de 43% sobre o código fixo de 4 bits
Bimodal - Bimodal: dois símbolos dominantes resultam em H≈2.5 bits, ganho significativo de compressão com Huffman