Instituto Federal do Espirito Santo
Danilo Nascimento, Gabriel Henrique, John Wisley e
Wagner Dias
Código de Huffeman
Serra
2011
Código de Hoffeman
Seminário sobre Código de Hoffeman:História,
características e aplicações para a turma
de Matemática Discreta do IFES.
Prof Dr Leandro Colambi Rosendo
Serra
2011
Sumário
1 - INTRODUÇÃO
2 - CONSTRUÇÃO
3 - EXERCICIOS
4 - REFERÊNCIAS
00
00
00
00
INTRODUÇÃO
Este trabalho fala sobre a Codificação de Huffman. Um método de compressão
que se baseia no total de ocorrência de cada símbolo. O método foi
desenvolvido em 1952 por David A Huffman, que no momento, fazia seu
doutorado no MIT (Instituto de Tecnologia de Massachusetts). Seu trabalho foi
publicado no artigo "A Method for the Construction of Minimum-Redundancy
Codes.
CONSTRUÇÃO
A árvore binaria de Huffman é construída por um algoritmo recursivo que faz a
junção dos dois símbolos de menor frequência, que são então somados em
símbolos auxiliares e estes recolocados no conjunto de símbolos.
O processo de construção termina quando todas as frequências de símbolos
foram somadas, formando uma arvore binaria. Depois que a árvore foi
concluída ela é percorrida e é atribuído um valor binário (de 0 ou 1) para cada
aresta, levando em conta o sentido(direita ou esquerda) de cada aresta.
Os símbolos serão inseridos apenas nas folhas desta árvore juntos da sua
frequência de aparecimento nos dados. Os nós são usados para armazenar as
somas das frequências de galhos inferiores e folhas da arvore. A raiz dessa
arvore possui a soma de todas as frequências.
Exercícios
1- Dados os códigos:
Caracter:
a e
i
o
u
Codificação: 00 01 10 110 111
Decodifique as seqüências:
a. 11011011101
b. 1000110111
c. 010101
2- Prove que a arvore de Huffman tem tamanho fixo 2n -1
3- Prove que para o algoritimo de Huffman ser ótimo as frequencias dos caracteres tem que
ser potencias negativas de dois. Ex: 2^-1 2^-2 ...
Referencias
 Fundamentos Matemticos para A Cincia da
Computao (Judith L Gersting, 3ed)
 http://pt.wikipedia.org/wiki/Codificação_de_Huffma
n
 www.lcad.icmc.usp.br/~jbatista/scc203/mat/huffma
n.ppt