Diogo Cata Preta

feeds

Algoritmos Gulosos (Códigos de Huffman)

Vou postar aqui algumas solu√ß√Ķes do capitulo 16 do livro “Algoritmos – Teoria e Pr√°tica” do Thomas H. Cormem. Acabei de fazer uma prova de Analise de Algor√≠tmos na faculdade, e na prepara√ß√£o para a prova resolvi estes exerc√≠cios. Portanto, vou ajudar aqueles que ir√£o precisar destes no futuro.

Quest√£o 16.3-2 – Enunciado: O que √© um c√≥digo de Huffman √≥timo para o conjunto de freq√ľ√™ncias a seguir, baseado nos primeiros 8 n√ļmeros de Fibonacci?
a:1 b:1 c:2 d:3 e:5 f:8 g:13 h:21
Voc√™ pode generalizar sua resposta para encontrar o c√≥digo √≥timo quando as freq√ľ√™ncias forem os n primeiros n√ļmeros de Fibonacci?

RESPOSTA: Seguindo o Algoritmo de Huffman, chega-se à construção da seguinte árvore:

analise de Algorítmos

Percorrendo essa √°rvore a partir da raiz √© poss√≠vel saber qual o c√≥digo bin√°rio √≥timo para cada letra, de acordo com sua freq√ľ√™ncia:

h – 0
g – 10
f – 110
e – 1110
d – 11110
c – 111110
b – 1111110
a – 1111111
0 Рcaminho esquerdo da árvore (nesta implementação)
1 Рcaminho direito da árvore (nesta implementação)

Algoritmo de Huffman

Huffman(C)
1 n := |C|
2 Q := C
3 for i:=1 to n-1 do
4 alocar um nó z
5 esquerda[z] := x := EXTRACT-MIN(Q)
6 direita[z] := y := EXTRACT-MIN(Q)
7 f[z] := f[x] + f[y]
8 INSERT(Q,z)
9 return EXTrACT-MIN(Q) // Retornar a raiz da √°rvore.

Comentários

Leave a Reply