relatorio

Compressor de dados
Huffman tree

Professor: Dr. Marcus Henrique Soares Mendes

Nome: Thiago Augusto Fernandes de Carvalho ­ 01094
Ranieri Welenkens Moura Gusmão­ 01250

Proposta :
O objetivo do trabalho é implementar um programa em linguagem c para realizar a compressão de dados de arquivos texto utilizando a codificação de Huffman. O programa implementado deve ser capaz de:
Montar a árvore de Huffman para o arquivo texto a ser compactado.
Realizar a compactação do arquivo texto.
Realizar a descompactação do arquivo texto.
Imprimir a taxa de compressão. o (tamanho original – tamanho compactado)/ tamanho original .

O que é 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. Ele foi desenvolvido em
1952 por
David A. Huffman que era, na época, estudante de doutorado no
MIT
, e foi publicado no artigo "A Method for the
Construction of Minimum­Redundancy Codes".
Uma árvore binária completa, chamada de árvore de Huffman é construída recursivamente a partir da junção dos dois símbolos de menor probabilidade, que são então somados em símbolos auxiliares e estes símbolos auxiliares recolocados no conjunto de símbolos. O processo termina quando todos os símbolos foram unidos em símbolos auxiliares, formando uma árvore binária. A árvore é então percorrida, atribuindo­se valores binários de
1 ou
0 para cada aresta , e os códigos são gerados a partir desse percurso.
A codificação de Huffman tem desempenho ótimo quando as probabilidades dos símbolos são potências negativas de dois (

). A codificação gerada tem também a garantia de

ser não ambígua, pois