Dando continuidade à elaboração do Algoritmo de Huffman, vamos desenvolver nesta aula o passo 8. Na aula anterior nós criamos nosso arquivo compactado com o algoritmo de huffman por meio da manipulação de bits. Nesta aula vamos ler o arquivo compactado criado na aula anterior. Para isso também será necessário manipulação de bits em C.

Aulas anteriores sobre o Código de Huffman:

1) Código de Huffman
2) Pensando a solução
3) Parte 1: Tabela de frequência
4) Parte 2: Lista ordenada
5) Parte 3: Árvore de huffman
6) Parte 4: Dicionário
7) Parte 5: Codificar
8) Parte 6: Decodificar
9) Parte 7: Arquivo compactado

Aulas anteriores sobre manipulação de bits em C

1. Deslocamento à esquerda e à direita
2. Operação de negação NOT
3. Operador AND ( & )
4. Operação OR ( | )
5. Operação OR Exclusivo

O objetivo nesta aula é ler cada byte escrito em nosso arquivo binário gerado na aula anterior e, para cada bit, caminhar na árvore de huffman, para a esquerda se o bit for 0 e para direita se o bit for 1. A cada bit lido precisamos verificar se chegamos em um nó folha que contêm o caracter representado pela sequência de bits lidos até ali.

A fim de deixar o código mais organizado, podemos criar uma função auxiliar para testar um determinado bit, uma função que recebe um byte (variável do tipo unsigned char), um índice i e verifica se o bit da posição i é um 0 ou um 1. Esta função é apresentada no trecho de código a seguir.

/*
     Função para testar o bit i
*/
unsigned int eh_bit_um(unsigned char byte, int i){
    unsigned char mascara = (1 << i);
    return byte & mascara;
}

Agora, vamos iniciar abrindo nosso arquivo compactado. Como é um arquivo binário e será aberto apenas para leitura, usamos o modo “rb”. Se o arquivo for aberto com sucesso, então precisamos ler todo o conteúdo do arquivo. Como o processamento é feito de byte em byte, podemos ler um byte por vez.

Para cada byte lido, precisamos verificar o valor de cada um dos seus 8 bits. Se for um 0 devemos caminhar para a esquerda na árvore de huffman, partindo da raiz, senão, caminhamos para a direita. A cada movimento precisamos verificar se chegamos em um nó folha. Ao chegar em um nó folha, acessamos seu conteúdo, neste caso apenas imprimirmos na tela, e voltamos para a raiz da árvore a fim de continuar o processo de descompactação.

A lógica descrita acima é apresentada no trecho de código a seguir.

/*
     Função para ler o arquivo compactado e obter o texto original.
*/

void descompactar(No *raiz){
    FILE *arquivo = fopen("compactado.wg", "rb");
    No *aux = raiz;
    unsigned char byte;
    int i;

    if(arquivo){
        // enquanto conseguir ler do arquivo
        while(fread(&byte, sizeof(unsigned char), 1, arquivo)){
            for(i = 7; i >= 0; i--){
                if(eh_bit_um(byte, i))
                    aux = aux->dir;
                else
                    aux = aux->esq;

                if(aux->esq == NULL && aux->dir == NULL){
                    printf("%c", aux->caracter);// imprime o caracter do nó folha
                    aux = raiz; // volta para a raiz da árvore
                }
            }
        }
        fclose(arquivo);
    }
    else
        printf("\nErro ao abrir arquivo em descompactar\n");
}

Na aula seguinte faremos algumas alterações na função main e testaremos nosso algoritmo para comprimir um texto em inglês e outro em português lidos de um arquivo texto.