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; }