Um belo dia, você, que é radio-astrônomo e não tem nada melhor para fazer, está escutando as estrelas. Após alguns ruídos estranhos, você recebe a seguinte mensagem (em hexadecimal, que os E.T.s também conhecem computador):

B3...........6E...........34...........94...........4C...........44...........64...........D8...........55

C2...........43...........44...........62...........1E...........8C...........04...........32...........B1

72...........D3...........15...........A1...........41...........05...........58...........53...........02

8D...........9D...........0F...........D0...........C9...........B3...........28...........54

Assustado, você verifica para onde está apontada a sua antena e vê que ela está na direção de veja (ou Canopus, tanto faz).

De alguma maneira, chega-lhe o conhecimento de que serão válidos os primeiros 278 bits de mensagem, sendo o resto bits de preenchimento, ou “bit-stuffing”, como os veganos os chamam.

Depois de quebrar a cabeça, você chega à conclusão que os veganos usuram os códigos de Huffman, já que existe um teorema (a matemática é universal) que prova ser este método o que garante o mínimo espaço ocupado por uma mensagem, ou seja ele é o universalmente mais econômico.

PS: Para saber sobre Huffman, leia o capítulo correspondente do livro de James Martin sobre bando de dados, ou de Gilbert Held sobre compressão de dados.

Para decodificar a mensagem, você precisa saber qual a freqüência relativa das letras em veja. Não se sabe como, você consegue uma amostra representativa. Ei-la

Neste bloco de 300 caracteres (o branco, por comodidade é um ^) existem 24 brancos, 23 letras “A”, 22 letras “O”,... 1 letra “Z”. Não há empates.

Saiba ainda que os veganos usam as seguintes convenções:

a) durante a construção da árvore, a maior freqüência fica à esquerda.

b) se houver empate entre uma folha e um nó intermediário, este fica à esquerda

c- o ramo esquerdo vale 0, e o direito vale 1

Você tem tudo o que precisa, então, mãos à obra:

1 – Converta a mensagem recebida para binário.

2 – A partir do bloco de 300 caracteres, crie a tabela de freqüências.

3 – Ordene-a em critérios ascendente.

4 – Construa a árvore: comece pelas 2 menores freqüências, juntando-as em um único nó, que será incluído na tabela, com a freqüência de seus filhos somada. Não esqueça de riscar na tabela o que for sendo usado. DICA 1: a árvore terá 24 folhas e 23 nós parciais. DICA 2: Para conferir a árvore, ante de começar aqui vão alguns códigos: A = 0010, X= 00000000, B= 01000 e C é 1011.

5 – Percorra a árvore, guiando-se pela mensagem. Cada vez que chegar a uma folha, escreva o caráter encontrado, e retorne à raiz.

Ao final, veremos que em Vega, William Shakespeare é apreciado, pois na mensagem temos o nome de uma tragédia do bardo inglês, seguido de 3 branco , e seguido por uma frase extraída dessa tragédia.

No próximo número teremos a árvore, o modo de construção da árvore e a resposta.