Teoria da Informação

Um post com um título de teoria da informação pode falar de muitas coisas interessantes, mas este é sobre matemática. Vou tentar ser o menos aborrecido possível!

Que quantidade de informação tem uma frase? Muita? Pouca? Pode-se medir?

Os matemáticos dizem que sim e apesar das minhas resistências iniciais, depois de algumas explicações fiquei a concordar que sim – pode ser medido.

Dizem os matemáticos que a quantidade de informação mede-se em bits e podemos calculá-la em função da probabilidade de ocorrência.

A formula é… É neste momento que eu perco todos os leitores... Seja persistente… Faça-me um favor salte o parágrafo que se segue e continue no seguinte.

Se P for a probabilidade de um facto ocorrer. A quantidade de informação (medida em bits) necessária para transmitir essa informação é dada pelo produto de -P com o logaritmo de base 2 de P.

Tornando a coisa simples, temos a seguinte tabela que para cada probabilidade de ocorrência tem a quantidade de informação correspondente.

0% - 0,00 bits
10% - 0,33 bits
20% - 0,46 bits
30% - 0,52 bits
40% - 0,53 bits
50% - 0,50 bits
60% - 0,44 bits
70% - 0,36 bits
80% - 0,26 bits
90% - 0,14 bits
100% - 0,00 bits



A estes dados corresponde o seguinte gráfico:





O que é que isto significa? Para que é que isto serve?

Imaginem que uma pessoa pergunta à outra: “Já jantaste?”

Se as únicas hipóteses de resposta forem “Sim” e “Não” e se quer uma, quer outra tiverem a mesma probabilidade de ocorrer (50% / 50%). Então para transmitir a resposta sobre um canal de comunicação existe uma medida, que se chama entropia, e que mede o grau de incerteza. A quantidade de informação necessária para transmitir esta resposta é 0,5 bits para a primeira alternativa e outro tanto para a segunda alternativa, logo precisamos de 1 bit.

Se, no entanto, uma pessoa perguntar “Já jantaste?”, mas ambos quer o emissor, quer o receptor souberem que a probabilidade de a resposta ser sim é de 90% e a probabilidade de a resposta ser não é de apenas 10%, então, aplicando o mesmo raciocínio a entropia desta resposta é de apenas 0,47 bits (0,14+0,33).

Complicando um pouco… se existissem 4 alternativas de resposta:
A - sim
B - não
C - já comi qualquer coisa, mas não me considero jantado
D - comi qualquer coisa, mas não me apetece mais nada

E se todas as quatro alternativas tivessem uma probabilidade de 25%, então seria necessários 2 bits para transmitir a resposta (0,5+0,5+0,5+0,5).

Num outro exemplo, se as probabilidades fossem as seguintes:

A – 40%
B – 30%
C – 20%
D – 10%

Então a quantidade de informação necessária para transmitir a mensagem é 1,85 bits (0,53+0,52+0,46+0,33).

Como se pode ver quer no exemplo com 2 alternativas de resposta, quer no de 4 alternativas de resposta, quanto mais sabemos sobre o que será a resposta menor a quantidade de informação que é necessário transmitir. Pelo contrário, se todas as respostas tiverem a mesma probabilidade, então estamos no pior caso e necessitamos de mais bits.

Se ainda está a ler este post, dou-lhe os meus parabéns!

O que provavelmente ainda não percebeu é para que é que isto serve.

Já alguma vez ouviu falar em compressão de dados? Aqueles ficheiros zip que fazem com que um ficheiro ocupe menos espaço sem perder a informação? Como é que acha que se faz isso? Com os conhecimento da teoria da informação…

Vejamos um exemplo prático de compressão de dados.

Suponhamos a seguinte sequência de letras: ABRACADABRA.

Se estivermos a enviar esta mensagem pela Internet sem qualquer compressão utilizamos 8 bits para cada letra. São 8 bits porque convencionou-se uma tabela com 256 (2^8) caracteres e para cada combinação dos 8 bits corresponde uma letra ou símbolo pré-convencionada (chama-se tabela ASCII).

Logo, enviar os 11 caracteres da mensagem ABRACADABRA são necessários 88 bits (11x8).
Mas se o emissor e o receptor souberem mais coisas então é possível comprimir esta informação.
Por exemplo, se soubermos que apenas são utilizadas as letras A B R C e D então, como existem apenas 5 alternativas, podemos utilizar apenas 3 bits para dizer que letra se segue. Assim, já só necessitamos de 33 bits para transmitir a mesma mensagem, em vez dos 88 bits iniciais.

Mas podemos saber mais coisas… Se repararmos bem na mensagem ABRACADABRA podemos saber que depois de um A pode surgir um B, um C, um D ou o fim da mensagem. Mas que depois de um B vem sempre um R. E que depois de um R vem sempre um A.
Se soubermos isto tudo, então apenas precisamos de enviar a mensagem dividida em apenas 4 alternativas: ABR AC AD e A (fim da mensagem).

ABR AC AD ABR A (fim da mensagem)

Para simplificar, se as 4 alternativas tiverem a mesma probabilidade, como no exemplo acima, então necessitamos de 0,5 bits por cada um destes blocos, logo 2,5 bits no total (5x0,5), em vez dos 88 bits iniciais.

Obviamente que estou a simplificar em demasia o que faz na realidade um compressor de dados. O compressor procura padrões de repetição, zonas com determinadas densidades de ocorrências e com base nessas “descobertas” tem de não só codificar a mensagem, como enviar de forma compacta a informação dos padrões que encontrou.

Se conseguiu ler este post até ao fim dou-lhe os meus parabéns.
Faça um comentário para que fique registada a façanha… :-