Entropia explicada

Em 1948, um engenheiro dos Bell Labs, Claude Shannon, fez uma pergunta que ninguém tinha formulado com precisão: quanta informação contém uma mensagem? A sua resposta foi um número, medido em bits, que não depende do que a mensagem significa, mas de quão surpreendente ela é. Esse número, a entropia, fixa os limites de todos os programas de compressão, de todas as ligações de rede e de todos os dispositivos de armazenamento, e explica porque é que alguns textos encolhem até uma fração do seu tamanho enquanto outros não se deixam reduzir de forma nenhuma.

Barras de probabilidades das letras a desvanecer das comuns para as raras, com a curva da entropia a descer à medida que se conhece mais contexto
Barras de probabilidades das letras a desvanecer das comuns para as raras, com a curva da entropia a descer à medida que se conhece mais contexto

Informação é surpresa

A grande ideia de Shannon foi medir a informação pelo quão inesperada é uma mensagem, e não pelo que significa. Se já sabe a resposta, ouvi-la não lhe diz nada; se ela podia ser uma entre mil coisas, diz-lhe muito. Uma mensagem que identifica uma de duas possibilidades igualmente prováveis transporta um bit. Uma de quatro exige dois bits, uma de oito três bits e, em geral, uma de N possibilidades igualmente prováveis exige log₂ N bits. Um símbolo que ocorre com probabilidade p transporta, portanto, −log₂ p bits: quanto mais raro, mais informação dá.

A fórmula de Shannon

A entropia é a informação média por símbolo: H = −Σ p log₂ p, somada sobre todos os símbolos com a respetiva probabilidade p. Para uma moeda equilibrada, H é 1 bit. Para uma moeda que dá cara 90% das vezes, é apenas 0,47 bits, porque o resultado normalmente não surpreende. A entropia é máxima quando todos os símbolos são igualmente prováveis, log₂ n bits para n símbolos, e nula quando um símbolo é certo. Shannon escolheu o nome por conselho de John von Neumann, porque a mesma fórmula aparece na física, onde a entropia mede a desordem.

Claude Shannon, que em 1948, nos Bell Labs, precisou quanta informação uma mensagem contém e a mediu em bits.
Claude Shannon, que em 1948, nos Bell Labs, precisou quanta informação uma mensagem contém e a mediu em bits.

O limite da compressão

O teorema da codificação de fonte de Shannon diz que nenhum código sem perdas pode usar, em média, menos bits por símbolo do que a entropia da fonte, e que os códigos se podem aproximar dela tanto quanto se queira. A codificação de Huffman, inventada por David Huffman em 1952 quando ainda era estudante, dá códigos curtos aos símbolos frequentes e códigos longos aos raros, e fica a menos de um bit por símbolo da entropia; a codificação aritmética aproxima-se ainda mais. A entropia não é, portanto, apenas uma descrição, mas um limite rígido: um ficheiro de bytes aleatórios, com 8 bits de entropia por byte, não pode ser comprimido de forma nenhuma.

David Huffman, fotografado como professor da Universidade da Califórnia em Santa Cruz. Como estudante de pós-graduação no MIT, em 1951 encontrou o seu código ótimo num trabalho para a disciplina de Robert Fano.
David Huffman, fotografado como professor da Universidade da Califórnia em Santa Cruz. Como estudante de pós-graduação no MIT, em 1951 encontrou o seu código ótimo num trabalho para a disciplina de Robert Fano.

Contexto e redundância

As letras de um texto não são independentes. Em inglês, depois de Q vem U, depois de um ponto final vem uma maiúscula, e uma palavra que começa por INFORMA continua quase de certeza com TION. Ter em conta os símbolos anteriores dá a entropia condicional, que é mais baixa do que a entropia dos símbolos contados um a um. A diferença é a redundância: a parte da mensagem que podia ter sido prevista. Programas de compressão como o ZIP, que usa o método deflate, encontram sequências repetidas e substituem-nas por referências curtas, e os compressores modernos preveem cada símbolo a partir do seu contexto.

Quanta informação há no inglês?

Contada letra a letra, com as frequências do inglês, uma letra transporta cerca de 4,1 bits, contra 4,7 para letras escolhidas ao acaso. Em 1951, Shannon foi mais longe: mostrou a várias pessoas o início de um texto e pediu-lhes que adivinhassem a letra seguinte, contando quantas tentativas precisavam. A partir das respostas, estimou que o inglês transporta apenas cerca de 0,6 a 1,3 bits por letra. Por outras palavras, cerca de três quartos do inglês escrito são redundância, e é por isso que um texto com letras em falta normalmente ainda se consegue ler.

Aleatoriedade e palavras-passe

A entropia também mede a imprevisibilidade, e é dela que depende a segurança. Uma chave ou palavra-passe escolhida uniformemente entre N possibilidades tem log₂ N bits de entropia, e um atacante tem de experimentar, em média, cerca de metade delas. Uma palavra-passe aleatória de 12 letras, tiradas das 26 letras minúsculas, tem cerca de 56 bits; uma palavra comum tem muito menos, por mais comprida que seja. Os geradores de números aleatórios são testados verificando que a sua saída tem a entropia completa de uma fonte aleatória, e os sistemas operativos recolhem entropia do ruído de temporização para os inicializar.

Onde a entropia aparece

A entropia decide de quantos bits precisa uma chamada telefónica, uma fotografia ou um fluxo de vídeo, e quão perto um modem ou uma ligação Wi-Fi pode chegar da capacidade do seu canal. Os biólogos usam-na para medir a informação no ADN, onde quatro bases podem transportar no máximo 2 bits cada, e a diversidade de um ecossistema. Na aprendizagem automática, as árvores de decisão escolhem a pergunta que mais reduz a entropia, e a função de perda de entropia cruzada treina a maioria das redes neuronais. Os linguistas comparam línguas pela sua entropia por carácter e por palavra.

Explore

Abra a calculadora de entropia para medir qualquer texto por caracteres, palavras ou bytes. Compare um parágrafo com letras, bits, algarismos e ADN aleatórios, veja a surpresa de cada símbolo, quanta informação o texto contém face ao seu tamanho armazenado, e como os bits por símbolo descem à medida que se conhece mais contexto, ao lado do que o ZIP realmente consegue.

Perguntas frequentes

Porque é que a entropia se mede em bits?

Porque Shannon usou logaritmos de base 2, de modo que uma escolha de sim ou não entre opções iguais conta como uma unidade. Com o logaritmo natural, a unidade é o nat, cerca de 1,44 bits, e com a base 10 é o hartley, cerca de 3,32 bits; são usados por físicos e por alguns estatísticos.

Pode um texto ter mais entropia do que o log₂ do seu alfabeto?

Não. Com n símbolos diferentes, a entropia é no máximo log₂ n bits por símbolo, valor atingido apenas quando todos são igualmente comuns. Qualquer desequilíbrio, e qualquer previsibilidade dada pelo contexto, reduz esse valor.

A entropia da teoria da informação é a mesma da física?

As fórmulas têm a mesma forma: Boltzmann e Gibbs escreveram a entropia física como uma soma sobre as probabilidades dos estados microscópicos de um sistema. O significado está relacionado, já que ambas medem o quanto não se sabe, e os físicos mostraram desde então que apagar um bit de informação tem de libertar uma pequena quantidade de calor.

Porque é que comprimir um ficheiro já comprimido não ajuda?

Um bom compressor remove a maior parte da redundância, por isso a sua saída é quase aleatória, com quase 8 bits de entropia por byte. Não resta nada para remover, e comprimi-lo de novo normalmente torna-o um pouco maior, por causa da sobrecarga do próprio compressor.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Abrir a calculadora de entropia