Estruturas de Dados - Huffman (Dibio)

Prévia do material em texto

dibio@unb.br
Exemplo: Huffman para 
Compressão de arquivos
● Ou seja, uma mensagem teria que ter (3 bits para 
cada das letras)x(22+9+10+12+16+8)=231 bits
● Código fixo
dibio@unb.br
Exemplo: Huffman para 
Compressão de arquivos
● 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.
dibio@unb.br
Algoritmo de Huffman
● Passo 1:
– Calcular, para cada símbolo diferente da mensagem de 
entrada, o total de ocorrências (frequência) desse 
símbolo.
dibio@unb.br
Algoritmo de Huffman
● Passo 2:
– Criar uma árvore binária com o total de folhas igual ao 
total de símbolos diferentes encontrados na mensagem 
(no exemplo anterior = 5)
dibio@unb.br
Algoritmo de Huffman
dibio@unb.br
Algoritmo de Huffman
dibio@unb.br
Algoritmo de Huffman
dibio@unb.br
dibio@unb.br
Exemplo: Huffman para 
Compressão de arquivos
● Ou seja, a mensagem terá 22x(2bits) + 9x(3bits) 
+10x(3bits) + 12x(3bits) + 16x(2bits) + 8x(3bits)= 
193 bits (comparado com 231?)
dibio@unb.br
Referências
● Tenenbaum, A.; Langsam, Y. & Augenstein, M. 
 Estruturas de Dados usando C, Makron Books, 
 RJ, 1995. (páginas 353-360)
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10