Dando continuidade à elaboração do Algoritmo de Huffman, vamos desenvolver nesta aula o passo 4. A partir da Árvore de Huffman construída no passo anterior, vamos elaborar nosso dicionário (tabela de código) para então conseguir codificar o texto de entrada.
Apenas para recordar, nosso dicionário pode ser uma matriz de caracteres. A quantidade de linhas será a quantidade de caracteres possíveis, ou seja, 256, para termos linhas de 0 a 255 para cada código da tabela ASCII. A quantidade de colunas será determinada pela altura da árvore de huffman mais 1. Assim, se a altura da árvore for 6 por exemplo, teremos uma matriz com 7 colunas, suficientes para armazenar em cada linha um código de 6 dígitos e o caracter de fim de string. Esta tabela é representada visualmente na figura a seguir.
Para criar esta tabela precisamos saber a altura da árvore. Assim, esta é a primeira função que vamos desenvolver.
/*
Procedimento para descobrir a altura da árvore
*/
int altura_arvore(No *raiz){
int esq, dir;
if(raiz == NULL)
return -1;
else{
esq = altura_arvore(raiz->esq) + 1;
dir = altura_arvore(raiz->dir) + 1;
if(esq > dir)
return esq;
else
return dir;
}
}
Agora que sabemos a altura da árvore podemos alocar memória para o dicionário. Como o dicionário é uma matriz, essa alocação de memória precisa ser feita em duas etapas. Primeiro alocamos um vetor de ponteiros de tamanho 256 e, sem seguida, para cada posição deste vetor de ponteiros, alocamos outro vetor, que serão as linhas da matriz, cujo tamanho é a altura da árvore mais 1. Esta última alocação de memória é feita com a função calloc, assim não precisamos nos preocupar com lixo de memória.
/*
Função para alocar memória dinamicamente para o dicionário
*/
char** aloca_dicionario(int colunas){
char **dicionario;
int i;
dicionario = malloc(sizeof(char*) * TAM);
for(i = 0; i < TAM; i++)
dicionario[i] = calloc(colunas, sizeof(char));
return dicionario;
}
O próximo passo é preencher o dicionário. Este procedimento é mais delicado, então recomendo que assista a aula ao final desta página com bastante atenção. O objetivo é percorrer toda a árvore de huffman gerando o código para cada caracter existente no texto a ser codificado. Como apenas os nós folhas possuem os caracteres, o código a ser gerado é o caminho a ser percorrido da raiz da árvore até as folhas, contando um 0 ao caminhar para a esquerda e um 1 ao caminhar para a direita, como apresentado na figura a seguir.
Este procedimento deve receber o ponteiro para o dicionário criado na função anterior, a raiz da árvore, uma string chamada caminho e a quantidade de colunas do dicionário. Durante a desenvolvimento ficará mais claro a finalidade de cada um destes parâmetros.
Como cada nó da árvore pode possuir até dois filhos, ao caminho por exemplo da raiz para a esquerda, temos um código em construção que inicia com 0. O filho da esquerda pode ter dois filhos também. Assim, teremos códigos derivados, 00 para a esquerda e 01 para a direita. A string caminho recebida como parâmetro vai armazenar este caminho em construção para cada caminho seguido na árvore.
Quando a raiz recebida for uma folha, significa que já temos no parâmetro caminho o código gerado para o caracter armazenado na respectiva folha da árvore. Neste caso, precisamos apenas copiar este código para a respectiva linha do dicionário.
Se a raiz não for uma folha, significa que temos filhos. Então precisamos fazer duas cópias do caminho gerado até ali, uma cópia continuará para a esquerda e a outra para a direita. Na cópia da esquerda concatenamos um 0 e na cópia da direita concatenamos um 1. Por fim fazemos duas chamadas recursivas, uma para a esquerda com o caminho esquerda e outra para a direita com o caminho direita.
Esta lógica é implementada no trecho de código a seguir.
/*
Procedimento para preencher o dicionário
*/
void gerar_dicionario(char **dicionario, No *raiz, char *caminho, int colunas){
char esquerda[colunas], direita[colunas];
if(raiz->esq == NULL && raiz->dir == NULL)
strcpy(dicionario[raiz->caracter], caminho);
else{
strcpy(esquerda, caminho);
strcpy(direita, caminho);
strcat(esquerda, "0");
strcat(direita, "1");
gerar_dicionario(dicionario, raiz->esq, esquerda, colunas);
gerar_dicionario(dicionario, raiz->dir, direita, colunas);
}
}
Por fim vamos imprimir na tela o dicionário gerado. Assim como fizemos com a tabela de frequência, vamos imprimir apenas os códigos que tiverem tamanho maior que zero e não imprimir as posições vazias.
/*
Procedimento para imprimir o dicionário na tela
*/
void imprime_dicionario(char **dicionario){
int i;
printf("\n\tDicionario:\n");
for(i = 0; i < TAM; i++){
if(strlen(dicionario[i]) > 0)
printf("\t%3d: %s\n", i, dicionario[i]);
}
}
Código parcial para o Algoritmo de Huffman – Parte IV – Dicionário (Tabela de códigos)
/*
Código escrito por Wagner Gaspar
Outubro de 2021
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <locale.h>
#define TAM 256
typedef struct no{
unsigned char caracter;
int frequencia;
struct no *esq, *dir, *proximo;
}No;
typedef struct{
No *inicio;
int tam;
}Lista;
//----------- parte 1: tabela de frequência ----------------------
void inicializa_tabela_com_zero(unsigned int tab[]){
int i;
for(i = 0; i < TAM; i++)
tab[i] = 0;
}
void preenche_tab_frequencia(unsigned char texto[], unsigned int tab[]){
int i = 0;
while(texto[i] != '\0'){
tab[texto[i]]++;
i++;
}
}
void imprime_tab_frequencia(unsigned int tab[]){
int i;
printf("\tTABELA DE FREQUENCIA\n");
for(i = 0; i < TAM; i++){
if(tab[i] > 0)
printf("\t%d = %u = %c\n", i, tab[i], i);
}
}
//----------- parte 2: Lista Encadeada Ordenada ----------------------
void criar_lista(Lista *lista){
lista->inicio = NULL;
lista->tam = 0;
}
void inserir_ordenado(Lista *lista, No *no){
No *aux;
// a lista está vazia?
if(lista->inicio == NULL){
lista->inicio = no;
//lista->tam++;
}
// tem frequência menor que o início da lista
else if(no->frequencia < lista->inicio->frequencia){
no->proximo = lista->inicio;
lista->inicio = no;
//lista->tam++;
}
else{
aux = lista->inicio;
while(aux->proximo && aux->proximo->frequencia <= no->frequencia)
aux = aux->proximo;
no->proximo = aux->proximo;
aux->proximo = no;
//lista->tam++;
}
lista->tam++;
}
void preencher_lista(unsigned int tab[], Lista *lista){
int i;
No *novo;
for(i = 0; i < TAM; i++){
if(tab[i] > 0){
novo = malloc(sizeof(No));
if(novo){
novo->caracter = i;
novo->frequencia = tab[i];
novo->dir = NULL;
novo->esq = NULL;
novo->proximo = NULL;
inserir_ordenado(lista, novo);
}
else{
printf("\tERRO ao alocar memoria em preencher_lista!\n");
break;
}
}
}
}
void imprimir_lista(Lista *lista){
No *aux = lista->inicio;
printf("\n\tLista ordenada: Tamanho: %d\n", lista->tam);
while(aux){
printf("\tCaracter: %c Frequência: %d\n", aux->caracter, aux->frequencia);
aux = aux->proximo;
}
}
//------------- parte 3: Montar a Árvore de Huffman ----------------------
No* remove_no_inicio(Lista *lista){
No *aux = NULL;
if(lista->inicio){
aux = lista->inicio;
lista->inicio = aux->proximo;
aux->proximo = NULL;
lista->tam--;
}
return aux;
}
No* montar_arvore(Lista *lista){
No *primeiro, *segundo, *novo;
while(lista->tam > 1){
primeiro = remove_no_inicio(lista);
segundo = remove_no_inicio(lista);
novo = malloc(sizeof(No));
if(novo){
novo->caracter = '+';
novo->frequencia = primeiro->frequencia + segundo->frequencia;
novo->esq = primeiro;
novo->dir = segundo;
novo->proximo = NULL;
inserir_ordenado(lista, novo);
}
else{
printf("\n\tERRO ao alocar memoria em montar_arvore!\n");
break;
}
}
return lista->inicio;
}
void imprimir_arvore(No *raiz, int tam){
if(raiz->esq == NULL && raiz->dir == NULL)
printf("\tFolha: %c\tAltura: %d\n", raiz->caracter, tam);
else{
imprimir_arvore(raiz->esq, tam + 1);
imprimir_arvore(raiz->dir, tam + 1);
}
}
//-------------- parte 4: Montar o dicionário ---------------------
int altura_arvore(No *raiz){
int esq, dir;
if(raiz == NULL)
return -1;
else{
esq = altura_arvore(raiz->esq) + 1;
dir = altura_arvore(raiz->dir) + 1;
if(esq > dir)
return esq;
else
return dir;
}
}
char** aloca_dicionario(int colunas){
char **dicionario;
int i;
dicionario = malloc(sizeof(char*) * TAM);
for(i = 0; i < TAM; i++)
dicionario[i] = calloc(colunas, sizeof(char));
return dicionario;
}
void gerar_dicionario(char **dicionario, No *raiz, char *caminho, int colunas){
char esquerda[colunas], direita[colunas];
if(raiz->esq == NULL && raiz->dir == NULL)
strcpy(dicionario[raiz->caracter], caminho);
else{
strcpy(esquerda, caminho);
strcpy(direita, caminho);
strcat(esquerda, "0");
strcat(direita, "1");
gerar_dicionario(dicionario, raiz->esq, esquerda, colunas);
gerar_dicionario(dicionario, raiz->dir, direita, colunas);
}
}
void imprime_dicionario(char **dicionario){
int i;
printf("\n\tDicionario:\n");
for(i = 0; i < TAM; i++){
if(strlen(dicionario[i]) > 0)
printf("\t%3d: %s\n", i, dicionario[i]);
}
}
int main() {
unsigned char texto[] = "Vamos aprender programação";
unsigned int tabela_frequencia[TAM];
Lista lista;
No *arvore;
int colunas;
char **dicionario;
char *codificado, *decodificado;
setlocale(LC_ALL, "Portuguese");
//----------- parte 1: tabela de frequência ---------------
inicializa_tabela_com_zero(tabela_frequencia);
preenche_tab_frequencia(texto, tabela_frequencia);
imprime_tab_frequencia(tabela_frequencia);
//----------- parte 2: Lista Encadeada Ordenada -----------
criar_lista(&lista);
preencher_lista(tabela_frequencia, &lista);
imprimir_lista(&lista);
//----------- parte 3: Montar a Árvore de Huffman ---------
arvore = montar_arvore(&lista);
printf("\n\tÁrvore de Huffam\n");
imprimir_arvore(arvore, 0);
//----------- parte 4: Montar o dicionário ----------------
colunas = altura_arvore(arvore) + 1;
dicionario = aloca_dicionario(colunas);
gerar_dicionario(dicionario, arvore, "", colunas);
imprime_dicionario(dicionario);
return 0;
}
