Projeto sobre a Codificação de Huffman

Índice

1. Introdução

2. Metodologia

3. Menu

4. Discussão dos Resultados

5. Compilação e Execução

Introdução

Este projeto consiste no desenvolvimento de uma aplicação em terminal utilizando a linguagem C++. Através de estrutura de dados foi proposto a criação de um método de compressão de dados fazendo uso da codificação de Huffman. A codificação de Huffman é um método de compressão que usa as probabilidades de ocorrência dos símbolos no conjunto de dados a ser comprimido para determinar códigos de tamanho variável para cada símbolo.

Metodologia

Para o uso da codificação, foram utilizadas estruturas em árvore, filas, listas e tabelas hash. Uma fila de prioridade foi criada para lidar com a reordenação da floresta de árvores que estava contida em uma lista de árvores. Abaixo segue as etapas do projeto e seus respectivos códigos.

Etapas do projeto

1. Contabilizar a recorrência de cada palavra no arquivo;

2. Normalizar a contabilização;

3. Montar a árvore com as regras apresentadas por Huffman;

4. Trocar as palavras pela codificação binária;

5. Salvar o arquivo em formato binário;

6. Observar e discutir sobre o ganho ou perda de espaço.

Menu

• Ao executar o programa surgirão as seguintes opções:

  • 1 Imprime a lista de palavras do texto e suas frequências normalizadas.
  • 2 Imprime a árvore de huffman (em lista) com seus valores associados em binário.
  • 3 Cria o arquivo binário test.dat no diretório /src .
  • 9 Finaliza o programa.

• Resultados esperados pela execução das opções:

  • [1] Print word's frequencies.

    (Palavra, Frequencia Normalizada)

    

  • [2] Print Huffman tree.

    (Palavra, Valor Binário)

    

  • [3] Create binary file.

    

  • [9] Exit.

    

Discussão dos Resultados

Através da análise do resultado da compressão foi possível identificar um aumento no tamanho do arquivo. Esse comportamento, contrário ao esperado, se deve devido ao código de Huffman verdadeiro (diferente do proposto) utilizar de caracteres como chaves para a construção da árvore e de seus respectivos valores binários. A quantidade de caracteres é muito inferior a quantidade de palavras possíveis dentro de um texto, fazendo com que os valores binários cresçam de tal maneira (devido a quantidade de palavras e o código não ter prefixos repetidos) que o tamanho do arquivo cresça.

Compilação e 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 g++, e o resultado vai para a pasta build
make run	Executa o programa da pasta build após a realização da compilação