Desenvolva um algoritmo para ler uma expressão informada pelo usuário e gerar a sequência de bits que a representa através da técnica de compressão de dados de Huffman.

Desenvolva um algoritmo para ler uma expressão informada pelo usuário e gerar a sequência de bits que a representa através da técnica de compressão de dados de Huffman.

Desenvolva um algoritmo para ler uma expressão informada pelo usuário e gerar a sequência de bits que a representa através da técnica de compressão de dados de Huffman. Para tal, considere o seguinte:
        1. criar uma lista encadeada que armazena o caractere e sua frequência na expressão.
        2. Ordene a lista de forma crescente ou decrescente a partir da frequência do caractere.
        3. Crie os nós da árvore de Huffman a partir dos dados da lista.
        4. Gere a sequência de bits que representa a expressão e certifique-se que é correta utilizando o processo de descompactação.

  1. /*
  2.         Desenvolva um algoritmo para ler uma expressão informada pelo usuário e gerar a sequência de bits que a representa através da técnica de compressão de dados de Huffman. Para tal, considere o seguinte:
  3.         1. criar uma lista encadeada que armazena o caractere e sua frequência na expressão.
  4.         2. Ordene a lista de forma crescente ou decrescente a partir da frequência do caractere.
  5.         3. Crie os nós da árvore de Huffman a partir dos dados da lista.
  6.         4. Gere a sequência de bits que representa a expressão e certifique-se que é correta utilizando o processo de descompactação.
  7. */
  8.  
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11. #include <math.h>
  12. #include <string.h>
  13.  
  14. //----------------------------------------------------------------------------
  15. typedef struct arvore_huffman {
  16.         struct arvore_huffman *esquerda, *direita;
  17.         int frequencia;
  18.         char c;
  19. } *raiz;
  20.  
  21. struct arvore_huffman frase_completa[256] = { {0} }; // char 2ˆ8 -> valores sao 128*2 = 256
  22. raiz total_fila[255];
  23. raiz *fila_letras = total_fila - 1;
  24. int num_raizes = 0;
  25. int final_final_letras = 1;
  26. char *codigo_fila_letras[128] = {0}; // codigo 0 ou 1 para cada fila_letras
  27. char buffer[1024]; // Tipo Char => 1 byte = (8bits) --> 128*8 = 1024 b
  28. //----------------------------------------------------------------------------
  29.  
  30. //----------------------------------------------------------------------------
  31. raiz nova_raiz(int frequencia, char c, raiz esq, raiz dir){
  32.         raiz n = frase_completa + num_raizes++;
  33.         if (frequencia){
  34.                 n->c = c;
  35.                 n->frequencia = frequencia;
  36.         }else {
  37.                 n->esquerda = esq;
  38.                 n->direita = dir;
  39.                 n->frequencia = esq->frequencia + dir->frequencia;
  40.         }
  41.         return n;
  42. }
  43. //----------------------------------------------------------------------------
  44.  
  45. /* Na ordem decrescente para uma fila de fila_letrass */
  46. void fila_letras_inserir(raiz n){
  47.         int j, i = final_final_letras++;
  48.         while ((j = i / 2)) {
  49.                 if (fila_letras[j]->frequencia <= n->frequencia)
  50.                         break;
  51.                 fila_letras[i] = fila_letras[j];
  52.                 i = j;
  53.         }
  54.         fila_letras[i] = n;
  55. }
  56. //----------------------------------------------------------------------------
  57. raiz remover_fila_letras(){
  58.         int i, l;
  59.         raiz n = fila_letras[i = 1];
  60.  
  61.         if (final_final_letras < 2)
  62.                 return 0;
  63.         final_final_letras--;
  64.         while ((l = i * 2) < final_final_letras) {
  65.                 if (l + 1 < final_final_letras && fila_letras[l + 1]->frequencia < fila_letras[l]->frequencia) l++;
  66.                 fila_letras[i] = fila_letras[l], i = l;
  67.         }
  68.         fila_letras[i] = fila_letras[final_final_letras];
  69.         return n;
  70. }
  71. //----------------------------------------------------------------------------
  72. /* caminhar pelos nos da arvore completando os valores com  0 e 1 */
  73. void construir_peso(raiz n, char *s, int len){
  74.         static char *saida = buffer;
  75.         if (n->c) {
  76.                 s[len] = 0;
  77.                 strcpy(saida, s);
  78.                 codigo_fila_letras[n->c] = saida;
  79.                 saida += len + 1;
  80.                 return;
  81.         }
  82.         s[len] = '0'; construir_peso(n->esquerda,  s, len + 1);
  83.         s[len] = '1'; construir_peso(n->direita, s, len + 1);
  84. }
  85. //----------------------------------------------------------------------------
  86. void construir_arvore(const char *s){
  87.  
  88.         int i, frequencia[128] = {0};
  89.         char c[16];
  90.  
  91.         while (*s) // percorre todas as possicoes
  92.                 frequencia[(int)*s++]++; // anda nas possicoes da string e atribui o indice da string pro vetor e soma mais 1
  93.  
  94.         for (i = 0; i < 128; i++){ // procura dentro do vetor
  95.                 if (frequencia[i]) // As possicoes do vetor
  96.                         fila_letras_inserir(nova_raiz(frequencia[i], i, 0, 0)); // insere somente nas possicoes q tem frequencia maior que 1
  97.         }
  98.         while (final_final_letras > 2)
  99.                 fila_letras_inserir(nova_raiz(0, 0, remover_fila_letras(), remover_fila_letras()));
  100.  
  101.         construir_peso(fila_letras[1], c, 0);
  102. }
  103. //----------------------------------------------------------------------------
  104.  
  105. void comprimir(const char *s, char *saida){
  106.         while (*s) {
  107.                 strcpy(saida, codigo_fila_letras[*s]);
  108.                 saida += strlen(codigo_fila_letras[*s++]);
  109.         }
  110. }
  111. //----------------------------------------------------------------------------
  112. void descomprimir(const char *s, raiz t){
  113.         raiz n = t;
  114.         while (*s) {
  115.                 if (*s++ == '0')
  116.                         n = n->esquerda;
  117.                 else
  118.                         n = n->direita;
  119.                 if (n->c){
  120.                         putchar(n->c);
  121.                         n = t;
  122.                 }
  123.         }
  124.         putchar('\n');
  125. }
  126. //----------------------------------------------------------------------------
  127. int main(void){
  128.         int i;
  129.         const char *frase = "Mario Kart", buffer[1024];
  130.  
  131.         construir_arvore(frase);
  132.         printf("\n Tabela de Pesos:\n ");
  133.         for (i = 0; i < 128; i++)
  134.                 if (codigo_fila_letras[i])
  135.                         printf("'%c':%s\n", i, codigo_fila_letras[i]);
  136.  
  137.         comprimir(frase, buffer);
  138.         printf("\n Frase Comprimida : %s  \n", buffer);
  139.  
  140.         printf(" Frase Descomprimida : ");
  141.         descomprimir(buffer, fila_letras[1]);
  142.         printf("\n");
  143.         return 0;
  144. }
  145. //----------------------------------------------------------------------------


Learn More :

Learn More Multiple Choice Question :