Dando continuidade à elaboração do Algoritmo de Huffman, vamos desenvolver nesta aula o passo 6. Na aula anterior desenvolvemos o processo de codificação do texto com o Algoritmo de Huffman. Nesta aula vamos desenvolver o processo de decodificação para obter o texto original.
Assim como fizemos na passo anterior, vamos trabalhar com duas strings, uma com o texto codificado e outra para receber o texto decodificado. Como na string com o texto codificado um conjunto de zeros e uns será convertido em apenas um caracter, obviamente o texto decodificado terá uma quantidade menor de caracteres. Então podemos criar a segunda string com o mesmo tamanho da string que possui o texto codificado.
Esta função é composta de uma repetição para percorrer cada caracter do texto codificado até o final da string. Para cada caracter codificado, se for um 0 vamos para a esquerda na árvore de huffman, se for um 1 vamos para a direita. A cada movimento precisamos verificar se chegamos em um nó folha. Ao chegar em uma folha, concatenamos o caracter presente no nó folha ao final da string “decodificado” e voltamos para a raiz da árvore a fim de continuar o processo.
Ao final retornamos a string com o texto decodificado.
/*
Função para decodificar um texto
*/
char* decodificar(unsigned char texto[], No *raiz){
int i = 0;
No *aux = raiz;
char temp[2];
char *decodificado = calloc(strlen(texto), sizeof(char));
while(texto[i] != '\0'){
if(texto[i] == '0')
aux = aux->esq; // caminha para a esquerda
else
aux = aux->dir; // caminha para a direita
// se for um nó folha concatena o caracter e volta para a raiz da árvore
if(aux->esq == NULL && aux->dir == NULL){
temp[0] = aux->caracter;
temp[1] = '\0';
strcat(decodificado, temp);
aux = raiz;
}
i++;
}
return decodificado;
}
Observe que da forma como apresentamos o algoritmo de huffman, na verdade ele não compacta o texto, mas expande, ou seja, a string com o texto codificado será sempre maior que a string original ou decodificada, pois cada caracter será representado por um conjunto variável de zeros e uns.
Para que de fato haja compressão precisamos trabalhar com a manipulação de bits na linguagem C. Assim, um caracter que sempre tem um código composto por 8 bits terá um código variável que normalmente será menor que 8 bits.
Nas aulas seguintes aprenderemos como fazer manipulações de bits na linguagem de programação C.
Código parcial em C para o Algoritmo de Huffman – Parte VI – Decodificar
/*
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]);
}
}
//-------------- parte 5: Codificar ----------------------------
int calcula_tamanho_string(char **dicionario, unsigned char *texto){
int i = 0, tam = 0;
while(texto[i] != '\0'){
tam = tam + strlen(dicionario[texto[i]]);
i++;
}
return tam + 1;
}
char* codificar(char **dicionario, unsigned char *texto){
int i = 0, tam = calcula_tamanho_string(dicionario, texto);
char *codigo = calloc(tam, sizeof(char));
while(texto[i] != '\0'){
strcat(codigo, dicionario[texto[i]]);
i++;
}
return codigo;
}
//-------------- parte 6: Decodificar --------------------------
char* decodificar(unsigned char texto[], No *raiz){
int i = 0;
No *aux = raiz;
char temp[2];
char *decodificado = calloc(strlen(texto), sizeof(char));
while(texto[i] != '\0'){
if(texto[i] == '0')
aux = aux->esq;
else
aux = aux->dir;
if(aux->esq == NULL && aux->dir == NULL){
temp[0] = aux->caracter;
temp[1] = '\0';
strcat(decodificado, temp);
aux = raiz;
}
i++;
}
return decodificado;
}
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 Huffman\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);
//----------- parte 5: Codificar ---------------------------
codificado = codificar(dicionario, texto);
printf("\n\tTexto codificado: %s\n", codificado);
//----------- parte 6: Decodificar -------------------------
decodificado = decodificar(codificado, arvore);
printf("\n\tTexto decodificado: %s\n", decodificado);
return 0;
}
