Dando continuidade à elaboração do Algoritmo de Huffman, vamos desenvolver nesta aula o passo 7. No passo 6 eu disse que para criar realmente um arquivo compactado com o algoritmo de huffman seria necessário trabalhar com manipulação de bits em C. Pois bem, depois de aprender como manipular bits nas últimas aulas, vamos agora criar nosso arquivo compactado.
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
Aulas sobre manipulação de bits em C
1) Deslocamento à esquerda e à direita
2) Operação de negação NOT
3) Operação AND ( & )
4) Operação OR ( | )
5) Operação OR Exclusivo
Na parte 5 foi gerada uma string de zeros e uns representando o texto codificado. Vamos continuar a partir desse ponto. Se escrevermos a string resultante em um arquivo, estaremos expandindo o texto e não comprimindo, uma vez que estaremos trocando cada caracter (que ocupa 8 bits) por uma sequência variável de zeros e uns (onde cada 0 e cada 1 ocupa 8 bits).
Assim, o objetivo agora é separar essa string em sequências de 8 dígitos e, por meio das operações bit a bit, montar um byte (8 bits) exatamente igual ao conjunto de 8 dígitos.
Vamos desenvolver um procedimento para realizar esta operação. Este procedimento precisa receber a string a ser convertida em bits que por fim serão escritos em um arquivo binário.
Neste exemplo vamos gerar um arquivo compactado chamado “compactado.wg“. Lembre-se que você pode dar o nome que você desejar a seu arquivo, incluindo a extensão. Para escrever em um arquivo precisamos primeiro criar esse arquivo, como feito no trecho de código a seguir. Abrimos um arquivo chamado “compactado.wg” no modo “wb“, um arquivo binário ( b ) para escrita ( w ).
Agora que temos o arquivo, precisamos percorrer a string até o final separando partes de tamanho 8 (1 byte possui 8 bits) a serem escritas no arquivo. Para isso usamos uma variável do tipo unsigned char chamada byte inicializada com o valor zero ( 0 ). Se o caracter da string for um zero, não precisamos fazer nada, como a variável byte foi inicializada com zero, todos os 8 bits são zero.
Contudo, se o caracter da string for um 1, então precisamos setar para 1 o bit daquela posição na variável byte. A variável j é utilizada para marcar a posição do bit avaliado, variando de 7 até 0. O bit 7 é o bit mais significativo à esquerda e o bit 0 é o bit menos significativo à direita. Para setar o bit da posição j para 1, criamos uma máscara inicializada com 1, fazemos um deslocamento para a esquerda de j posições e, por fim, realizamos a operação OR ( ou ) entre as variáveis byte e mascara.
Esta lógica descrita é implementada no trecho de código a seguir.
/*
-------------- parte 7: Compactar --------------------------
*/
void compactar(unsigned char str[]){
FILE *arquivo = fopen("compactado.wg", "wb");
int i = 0, j = 7;
unsigned char mascara, byte = 0; // 00000000
if(arquivo){
while(str[i] != '\0'){
mascara = 1;
if(str[i] == '1'){
mascara = mascara << j;
byte = byte | mascara;
}
j--;
if(j < 0){ // tem um byte formado
fwrite(&byte, sizeof(unsigned char), 1, arquivo);
byte = 0;
j = 7;
}
i++;
}
if(j != 7) // tem um byte em formação
fwrite(&byte, sizeof(unsigned char), 1, arquivo);
fclose(arquivo);
}
else
printf("\nErro ao abrir/criar arquivo em compactar\n");
}
Como a variável j representa a posição dos bits em um byte, de 7 a 0, quando j se tornar negativo significa que já temos um conjunto de 8 bits, 1 byte, pronto para ser escrito no arquivo. Então escrevemos o conteúdo da variável byte no arquivo aberto e iniciamos o processo de conversão novamente, inicializando a variável byte novamente com zero e a variável j com 7.
Quando a repetição terminar, indicando que atingimos o fim da string, precisamos verificar o valor da variável j, pois muito provavelmente haverá um byte em formação. Assim, se o valor de j for diferente de 7 significa que há alguns bits na variável byte e seu conteúdo precisa ser escrito no arquivo também.
Por fim, não esqueça de fechar seu arquivo.
Agora, basta acrescentar o procedimento desenvolvido acima no código apresentado nas aulas anterior e chama-lo na função main, como apresentado a seguir.
/*
Função main para o executar o algoritmo de huffman
*/
int main() {
//unsigned char texto[] = "Vamos aprender programação";
unsigned char *texto;
unsigned int tabela_frequencia[TAM];
Lista lista;
No *arvore;
int colunas, tam;
char **dicionario;
char *codificado, *decodificado;
SetConsoleOutputCP(65001);
tam = descobrir_tamanho();
printf("\nQuantidade: %d\n", tam);
texto = calloc(tam + 2, sizeof(unsigned char));
ler_texto(texto);
//printf("\nTEXTO:\n%s\n", texto);
//----------- 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\tArvore 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);
//----------- parte 6: Decodificar -------------------------
decodificado = decodificar(codificado, arvore);
//printf("\n\tTexto decodificado: %s\n", decodificado);
//----------- parte 7: Compactar ----------------------------
compactar(codificado);
return 0;
}
Na próxima aula faremos o processo inverso, lendo nosso arquivo compactado e decodificando o texto.
