Análise e Desenho de Algoritmos

Exercício 8

1. Construa a árvore de Huffman e a tabela de códigos para o texto seguinte: ``O rato roeu a rolha da garrafa do rei do russia''
2. Codifique o texto de acordo com a sua tabela.
3. Qual a Coeficiente de compressão do texto?

   (Q )
   nota: junto com o texto codificado tem que guardar a árvore de huffman.

4. Qual é a taxa de compressão do texto? ()
5. Para construir a árvore de huffman é necessário construir uma tabela de frequências dos simbolos no texto.

   Faça uma função que leia o texto do stdin e construa a tabela de frequências sabendo que o texto pode conter qualquer simbolo do código ascci.

   Use a seguinte tabela:

   int freq[256];

6. Defina uma função para construir a árvore de huffman a partir da tabela de frequencias (int freq[256];).

   Pode usar o seguinte tipo para representar a árvore de huffman:
   

   struct ab{ int freq;
     char s;
     struct ab *esq; 
     struct ab *dir;
   };
   

   Nota: Cada simbolo com frequência diferente de 0 deve ser introduzido, por exemplo num vector (ex: struct tabela codigos[256];) ordenado (decrescente) pela frequência do simbolo. A sua função deve retirar as árvores com menor frequência e juntá-las numa e inserir a nova árvore na estrura ordenada (ex:vector). Este procedimento deve ser repetido até só existir uma árvore na estrutura. 
7. Defina uma função que dada uma árvore de huffman constrói uma tabela com os códigos dos simbolos do texto. Pode usar a seguinte estrutura para representar a tabela:

   struct tabela{char *codigo;
                 int numbits;};
   
   struct tabela codigos[256];
   

8. Defina uma função que dada uma tabela com os códigos de huffman e uma string com o texto a codificar escreve no stdout o código da string de acordo com a tabela.

   Nota: para fazer um shift para a esquerda basta multiplicar por 2 ou usar o operador <<

   ex:

   unsigned char x=1; /* x=0000 0001  em binário*/
   x=x*2;  ou x = x <<1; /* x=0000 0010  em binário*/
   

   Se a codificação do seu texto não for um multiplo de 8 não se preocupe, apesar de no stdout só poder escrever palavras com um minimo de 8 bits.

9. Defina a uma função que dada uma árvore de huffman a escreve no stdout de forma a que possa ser reconstruída quando for lida por outro programa.