Dando continuidade à elaboração do Algoritmo de Huffman, vamos desenvolver nesta aula o passo 5. Agora que já temos a tabela de códigos, nosso dicionário, podemos codificar, comprimir, o nosso texto. Então, vamos ver nesta aula como percorrer uma string codificando cada caracter.
Há diversas formas de realizar este processo. Para tornar o conteúdo mais didático faremos uso de duas strings (dois vetores de caracteres), uma contendo o texto a ser codificado e outra que irá conter o texto codificado (uma sequência de zeros e uns).
Como não sabemos o tamanho do texto codificado, precisamos descobrir esse tamanho para então criar este vetor dinamicamente. Para isso podemo escrever uma função que irá acumular o somatório do tamanho do código de cada caracter do texto a ser codificado. Este tamanho pode ser encontrado na tabela de códigos (dicionário) desenvolvido na aula 284. O trecho de código a seguir implementa esta funcionalidade, retornando o tamanho que terá o texto codificado.
/*
Função para calcular e retornar o tamanho do texto codificado
*/
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;
}
Agora que sabemos o tamanho que terá o texto codificado, podemos criar uma função para fazer a codificação do texto. Esta função recebe o dicionário e o texto a ser codificado, descobre o tamanho do texto codificado com a função anterior e aloca dinamicamente memória para guardar o texto codificado. Para a alocação de memória é utilizada a função calloc uma vez que, além de alocar memória, ela também limpa a região de memória alocada.
O processo de codificação consiste em uma repetição, percorrendo a string a ser codificada até o final. Para cada caracter, precisamos acessar o dicionário, buscar seu código e concatenar ao final da string codificada. O trecho de código abaixo implementa esta lógica.
/*
Função que codifica o texto. O retorno é o endereço da string codificada
*/
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;
}
Código parcial para o Algoritmo de Huffman – Parte V – Codificar
/*
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 FREQUÊNCIA\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;
}
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);
//----------- parte 5: Codificar ---------------------------
codificado = codificar(dicionario, texto);
printf("\n\tTexto codificado: %s\n", codificado);
return 0;
}
