/*
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.
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
//----------------------------------------------------------------------------
typedef struct arvore_huffman {
struct arvore_huffman *esquerda, *direita;
int frequencia;
char c;
} *raiz;
struct arvore_huffman frase_completa[256] = { {0} }; // char 2ˆ8 -> valores sao 128*2 = 256
raiz total_fila[255];
raiz *fila_letras = total_fila - 1;
int num_raizes = 0;
int final_final_letras = 1;
char *codigo_fila_letras[128] = {0}; // codigo 0 ou 1 para cada fila_letras
char buffer[1024]; // Tipo Char => 1 byte = (8bits) --> 128*8 = 1024 b
//----------------------------------------------------------------------------
//----------------------------------------------------------------------------
raiz nova_raiz(int frequencia, char c, raiz esq, raiz dir){
raiz n = frase_completa + num_raizes++;
if (frequencia){
n->c = c;
n->frequencia = frequencia;
}else {
n->esquerda = esq;
n->direita = dir;
n->frequencia = esq->frequencia + dir->frequencia;
}
return n;
}
//----------------------------------------------------------------------------
/* Na ordem decrescente para uma fila de fila_letrass */
void fila_letras_inserir(raiz n){
int j, i = final_final_letras++;
while ((j = i / 2)) {
if (fila_letras[j]->frequencia <= n->frequencia)
break;
fila_letras[i] = fila_letras[j];
i = j;
}
fila_letras[i] = n;
}
//----------------------------------------------------------------------------
raiz remover_fila_letras(){
int i, l;
raiz n = fila_letras[i = 1];
if (final_final_letras < 2)
return 0;
final_final_letras--;
while ((l = i * 2) < final_final_letras) {
if (l + 1 < final_final_letras && fila_letras[l + 1]->frequencia < fila_letras[l]->frequencia) l++;
fila_letras[i] = fila_letras[l], i = l;
}
fila_letras[i] = fila_letras[final_final_letras];
return n;
}
//----------------------------------------------------------------------------
/* caminhar pelos nos da arvore completando os valores com 0 e 1 */
void construir_peso(raiz n, char *s, int len){
static char *saida = buffer;
if (n->c) {
s[len] = 0;
strcpy(saida, s);
codigo_fila_letras[n->c] = saida;
saida += len + 1;
return;
}
s[len] = '0'; construir_peso(n->esquerda, s, len + 1);
s[len] = '1'; construir_peso(n->direita, s, len + 1);
}
//----------------------------------------------------------------------------
void construir_arvore(const char *s){
int i, frequencia[128] = {0};
char c[16];
while (*s) // percorre todas as possicoes
frequencia[(int)*s++]++; // anda nas possicoes da string e atribui o indice da string pro vetor e soma mais 1
for (i = 0; i < 128; i++){ // procura dentro do vetor
if (frequencia[i]) // As possicoes do vetor
fila_letras_inserir(nova_raiz(frequencia[i], i, 0, 0)); // insere somente nas possicoes q tem frequencia maior que 1
}
while (final_final_letras > 2)
fila_letras_inserir(nova_raiz(0, 0, remover_fila_letras(), remover_fila_letras()));
construir_peso(fila_letras[1], c, 0);
}
//----------------------------------------------------------------------------
void comprimir(const char *s, char *saida){
while (*s) {
strcpy(saida, codigo_fila_letras[*s]);
saida += strlen(codigo_fila_letras[*s++]);
}
}
//----------------------------------------------------------------------------
void descomprimir(const char *s, raiz t){
raiz n = t;
while (*s) {
if (*s++ == '0')
n = n->esquerda;
else
n = n->direita;
if (n->c){
putchar(n->c);
n = t;
}
}
putchar('\n');
}
//----------------------------------------------------------------------------
int main(void){
int i;
const char *frase = "Mario Kart", buffer[1024];
construir_arvore(frase);
printf("\n Tabela de Pesos:\n ");
for (i = 0; i < 128; i++)
if (codigo_fila_letras[i])
printf("'%c':%s\n", i, codigo_fila_letras[i]);
comprimir(frase, buffer);
printf("\n Frase Comprimida : %s \n", buffer);
printf(" Frase Descomprimida : ");
descomprimir(buffer, fila_letras[1]);
printf("\n");
return 0;
}
//----------------------------------------------------------------------------
