Como construir a Tabela de Frequência para o Código de Huffman?

Dando continuidade ao nosso Curso de Programação com a Linguagem C, nesta aula vamos iniciar o desenvolvimento do código de Huffman (Algoritmo de Huffman).

Nesta aula vamos desenvolver a Tabela de Frequência, a primeira etapa do Algoritmo de Huffman.

Como vimos na aula anterior, esta tabela pode ser um vetor de inteiros de tamanho 256, com índices no intervalo entre 0 e 255 abrangendo todos os índices da tabela ASCII. Como precisaremos percorrer esta tabela diversas vezes, vamos iniciar criando uma constante global para armazenar o tamanho da tabela.

/*
     Tamanho da tabela de frequência
*/
#define TAM 256

Agora podemos criar na função main nossa tabela. Lembre-se que iremos trabalhar com caracteres e queremos a acentuação correta, então sempre utilizaremos o modificador unsigned para interpretar qualquer conjunto de bits como um valor sem sinal.

/*
      Criação da tabela de frequência na função main
*/
int main() {

    // texto de exemplo para testar o código
    unsigned char texto[] = "Vamos aprender programação";
    unsigned int tabela_frequencia[TAM];
    
    setlocale(LC_ALL, "Portuguese");

    return 0;
}

Agora que temos a tabela precisamos limpá-la, ou seja, iniciar cada posição com zero. Como iremos contar a frequência de cada caracter em cada posição da tabela precisamos ter certeza que não há lixo de memória para interferir no resultado final. A seguir é apresentado um procedimento para inicializar toda a tabela com zero.

/*
       Procedimento para inicializar a tabela de frequência com zero
*/
void inicializa_tabela_com_zero(unsigned int tab[]){
    int i;
    for(i = 0; i < TAM; i++)
        tab[i] = 0;
}

Agora que a tabela está completamente limpa, precisamos percorrer o texto a ser codificado e contar as ocorrências de cada caracter. Percorrer o texto contando a frequência de cada caracter para depois atualizar a tabela até pode ser feito, mas isso tornará o código mais lento e será necessário percorrer toda a tabela diversas vezes, até obtermos a frequência de todos os caracteres.

Como nossa tabela possui todos os índices da tabela ASCII, podemos contar a frequência de todos os caracteres ao mesmo tempo. Para um caracter X, acessamos a tabela na posição X e incrementamos o valor ali armazenado. Isso pode ser feito com a instrução a seguir:

/*
   Incremento do valor da posição texto[i] da tabela.
*/
tab[texto[i]]++;

Observe que a string texto possui o texto a ser codificado. Assim, cada posição i desse vetor possui algum caracter. A parte “texto[i]” retorna o caracter da posição i. Como este trecho está dentro do par de colchetes de acesso a um vetor, então será retornado não o caracter, mas o código da tabela ASCII que representa aquele caracter, um número entre 0 e 255. Feito isso, basta incrementar o valor daquela posição.

/*
     Procedimento para contar a frequência dos caracteres
*/
void preenche_tab_frequencia(unsigned char texto[], unsigned int tab[]){
    int i = 0;

    while(texto[i] != '\0'){
        tab[texto[i]]++;
        i++;
    }
}

Para ter certeza que tudo está funcionando como o esperado é interessante imprimir na tela nossa tabela de frequência. Isso será feito com a trecho de código a seguir.

/*
    Procedimento para imprimir a tabela de frequência
*/
void imprime_tab_frequencia(unsigned int tab[]){
    int i;

    printf("\tTABELA DE FREQUENCIA\n");
    for(i = 0; i < TAM; i++)
        printf("\t%d = %u = %c\n", i, tab[i], i);
}

Ao executar o trecho de código acima para um texto pequeno, como a frase do nosso exemplo, você vai perceber que muitas posições da tabela estão vazias, com o valor 0 ( zero ). Para melhorar esta impressão, podemos fazer um teste e imprimir apenas as posições maiores que zero, indicando que existe ao menos uma ocorrência daquela caracter.

/*
    Procedimento para imprimir a tabela de frequência
*/
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);
    }
}

Código parcial para o Algoritmo de Huffman – Parte I: Tabela de Frequência

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <locale.h>

/*
              Código escrito por Wagner Gaspar
              Outubro de 2021
*/

// Tamanho da tabela de frequência
#define TAM 256

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

int main() {

    unsigned char texto[] = "Vamos aprender programação";
    unsigned int tabela_frequencia[TAM];

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

    return 0;
}

Início