Apresentação • Lógica • Resultados • Bibliotecas • Compilação e Execução • Autor
Foi proposto pelo professor Michel Pires da Silva da matéria de Arquitetura e Estruturas de Dados 2 do 4º Período do curso de Engenharia de Computação um trabalho relacionado ao conteudo passado em suas aulas teoricas que são Estrutura de Dados Árvore, onde foi introduzido a codificação de Huffman e a sua implementação. Portanto foi desenvolvido o seguinte desafio:
Elabore uma árvore binária que utilize o código de Huffman para comprimir arquivos. Para tanto, (1) contabilizar a recorrência de cada palavra (RP) no arquivo; (2) normalizar a contabilização entre 0 e 1 utilizando a formula -> RP / (max(RP) - min(RP)); (3) Montar a árvore com as regras apresentadas por Huffman; (4) Troque as palavras pela codificação binária (utilizar booleano para representar 0 e 1); (5) Salve o arquivo em formato binário e observe qual foi o ganho de espaço obtido.
Com isso, foi trabalhada a lógica abaixo, que obteve êxito apresentando uma solução para este trabalho!
Para a solução do problema proposto, foi utilizado a Estrutura de Dados Lista Dinâmica onde a mesma foi utilizada através de um repositório feito pelo professor Michel Pires da Silva sendo ele Lista Dinâmica, onde foram feitas apenas algumas alterações como conversão da linguagem C para C++ e mudanças nas variáveis presente em seu Item onde agora possui duas strings sendo elas word e sequence onde vão armazenar respectivamente uma palavra presente no arquivo e mais a frente do código a sua sequência 'booleana' e uma variável do tipo double onde vai armazenar a quantidade de vezes em que a palavra foi repetida ou sua normalização após o cálculo informado no enunciado.
Primeiramente foi necessário ser feita a leitura de um arquivo do tipo .txt contendo um texto sendo esse o alvo da compactação, onde no programa a função ReadDocument() realiza esse trabalho recebendo como parâmetro uma Lista Dinâmica e uma estrutura de Huffman fazendo a leitura do arquivo document.txt linha por linha, onde a cada linha lida é feita a tokenização de cada palavra e é feito o armazenamento dessas palavras em vector tokens e com isso foi feita a remoção das vogais solitárias para que não houvesse interferência na normalização e codificação das palavras.
A recorrência foi feita checando as palavras de uma a uma, utilizando três estruturas de repetição do tipo FOR onde a primeira vai segurar uma palavra presente no vector tokens , a segunda vai sempre começar a percorrer uma a frente para que não seja feita a verificação de duas mesmas palavras e a última estrutura vai percorrer o vector verified_words, um vector de strings onde a cada verificação das palavras é incrementada a palavra nesse vector,sendo feita a verificação de cada palavra do vector tokens para que seja verificado se não vai haver uma segunda contabilização de determinada palavra, caso seja verificado que não foi realizado a verificação de cada palavra e que foi encontrado uma igual, será incrementado mais um na variável repetition_count para que no fim do segundo FOR seja feita a inserção da palavra e a sua quantidade de repetições na lista passada como parâmetro, fazendo no final a limpeza da variável repetition_count para que haja uma nova contabilização de uma outra palavra.
Para ser feita a normalização da contabilização primeiramente foi necessário encontrar o número máximo e o número mínimo de repetições para que fosse possível normalizar a contabilização entre 0 e 1 utilizando a fórmula
normalization = (aux2->data.repetition_number / (max_repetition - min_repetition));Feito isso, vai ser armazenado o valor encontrado adicionando-o no Item da lista repetition_number de cada palavra em que foi feita a normalização
Já possuindo um lista de palavras com suas determinadas repetições normalizadas de maneira ordenada, foi possibilitada a criação da Árvore de Huffman que inicialmente é composta em seu nó por uma variável do tipo Item que vai ser as variáveis presentes no Item da Lista Dinâmica e ponteiros que apontam para os seguintes posições left(esquerda), right(direita), prox(proximo) como possível a ver na representação abaixo:
Ou seja, a Árvore de Huffman se tratará de uma lista encadeada ordenada e será preenchida através da função FillHuffman() que vai receber como parametro a lista de palavras com suas repetições e a estrutura de Huffman, onde vai preencher a estrutura de Huffman com elementos presentes na lista de maneira ordenada definindo seus nós como NULL, a partir disso vai ser criada a Árvore de Huffman sendo feita pela função HuffmanTree() que constitui de um nó e recebe como parâmetro a estrutura Huffman preenchida, fazendo então de dois novos nó, sendo eles first e second que através de uma estrutura de repetição WHILE, que repete enquanto o tamanho da estrutura é maior que 1, vai retirando os dois primeiros elementos da estrutura (os dois menores elementos) colocando-os respectivamente nos nós criados e assim então criando um terceiro novo nó chamado new_no que vai receber como parte do seu Item word um caracter qualquer e do seu Item repetition_number a soma da normalização dos dois nós removidos, inserindo os dois nós removidos como filho direito e esquerdo deste novo nó e após isso insere novamente na lista, como possível visualizar na representação abaixo:
(OBS: A representação acima é referente a algumas palavras presentes no texto que está no arquivo 'documents.txt' e também de possível visualização em resultados.)
Ao final desta função vai ser retornada o início da estrutura de Huffman ou apenas um nó caso a estrutura possua um número ímpar de elementos.
Até o momento irá existir um nó chamado tree presente no algoritmo em que vai possuir toda a Árvore de Huffman e relacionada ao exemplo anterior vai estar como na representação a seguir:
(OBS: A representação acima é referente a algumas palavras presentes no texto que está no arquivo 'documents.txt' e também de possível visualização em resultados.)
A resolução para a codificação binária das palavras é encontrada na função GenerateSequence() onde recebe como parâmetro toda a Árvore de Huffman construída na função anterior como parâmetro, uma nova Lista Dinâmica criada para armazenar as sequências booleanas com suas respectivas palavras e uma string chamada way, se tratando de uma função recursiva, já vai ser introduzida com uma estrutura de decisão IF onde verifica se chegou em uma folha, ou seja, os filhos esquerdos e direitos daquele nó são NULL e caso se tratar de uma folha vai ser passada a palavra e a sequência booleana em forma de string que foi obtida durante toda a recursão da função para a Lista Dinâmica, caso contrário, significa ainda que possui filhos então é feita duas cópias do caminho gerado até ali, uma cópia continuará para a esquerda e a outra para a direita. Na cópia da esquerda vai ser concatenado um 0 na variável left_way e na cópia da direita vai ser concatenada um 1 na variável right_way e por fim vai ser feita duas chamadas recursivas da função GenerateSequence(), uma para a esquerda com a left_way e outra para a direita com o right_way passados como parâmetros
A última etapa do código consiste em pegar toda a codificação feita na etapa anterior e escrever essa codificação em formato booleano correspondentes às palavras que são encontradas no arquivo de texto inicial, para a solução desse propósito foi criado a função WriteBinaryFile() que recebe como parâmetro uma lista que contém as palavras com suas respectivas sequências booleanas e o vector tokens criado no início do programa eu contém a tokenização do arquivo de texto a ser codificado. Diante disso, a função inicia com duas estruturas de repetição, sendo um FOR e um WHILE onde primeiramente o FOR irá percorrer o vector tokens e o WHILE vai ser necessário para percorrer a lista que a cada posição percorrida vai ser feita a verificação utilizando a estrutura de decisão IF , verificando se cada posição do vecotr tokens corresponde a posição da lista e caso seja correspondente vai ser introduzido um novo FOR para converter a sequência que está na lista em tipo string para tipo bool através de um vector bool que vai armazenando a sequência em formato booleano para no fim escrever posição por posição do vector bool no novo arquivo do tipo .bin, que ao fim vai ser feita a limpeza desse vector para que possa ser utilizado novamente em uma nova palavra encontrada na verificação de igualdade do texto.
• Após toda a lógica acima ter sido implementada no algoritmo foi possível a obtenção da compactação do arquivo 'document.txt' como forma de teste onde o mesmo continha o seguinte texto:
Caros amigos, a infinita diversidade da realidade única nos obriga à análise do demônio de Laplace. Por outro lado, a complexidade dos estudos efetuados cumpre um papel essencial na formulação da fundamentação metafísica das representações. Assim mesmo, a forma geral da proposição significativa deverá confirmar as consequências decorrentes do sistema de conhecimento geral.
Neste sentido, o novo modelo estruturalista aqui preconizado auxilia a preparação e a composição das posturas dos filósofos divergentes com relação às atribuições conceituais. Baseando-se nos ensinamentos de Dewey, a canalização do Ser do Ente garante a contribuição de um grupo importante na determinação das novas teorias propostas. A prática cotidiana prova que a consolidação das estruturas psico-lógicas não sistematiza essa relação, de tal modo que a pulsão funciona funciona como significado da determinação do Ser enquanto Ser.
Onde a partir desse texto foi visualizado que o arquivo '.txt' do mesmo continha um total de 953 bytes e após a compactação realizada pelo algoritmo foi criado um novo arquivo '.bin' chamado 'compact_text.bin' encontrando um tamanho de 761 bytes do mesmo, concluindo que a compactação foi feita com sucesso, tendo um total de 191 bytes compactados.
• Ao ser compilado e executado o programa irá gerar a seguinte mensagem:
Diante disso um arquivo de texto chamado 'sequence.txt' irá ser criado no qual vai informar ao usuário todas as palavras presentes no texto com suas respectivas codificações booleanas, esse arquivo abre a possibilidade do usuário de consultar as codificações encontradas no arquivo binário.
Para o funcionamento do programa, é necessário incluir as seguintes bibliotecas:
#include 'stdbool.h'#include 'stdio.h'#include 'fstream'#include 'iostream'#include 'stdlib.h'#include 'vector'#include 'string'#include 'sstream'#include 'assert.h'
O programa feito de acordo com a proposta possui um arquivo Makefile que realiza todo o procedimento de compilação e execução. Para tanto, temos as seguintes diretrizes de execução:
| Comando | Função |
|---|---|
make clean |
Apaga a última compilação realizada contida na pasta build |
make |
Executa a compilação do programa utilizando o gcc, e o resultado vai para a pasta build |
make run |
Executa o programa da pasta build após a realização da compilação |
Desenvolvido por Pedro Henrique Louback Campos
Aluno do 4° periodo do curso de Engenharia de Computação no CEFET-MG