April 05
Prof. Ismael H. F. Santos
- ismael@tecgraf.puc-rio.br
26
Codificação de Huffman
Árvore de
Huffman.
A idéia básica para construir esta árvore consiste em
colocar
os tons mais freqüentes perto
da raiz e os tons menos freqüentes mais distantes. O algoritmo de construção da árvore de
Huffman para isto pode ser descrito da
seguinte maneira:
Comece criando uma
tabela dos tons e do número de vezes que eles aparecem na imagem (colunas 1 e 2 da Tabela
).
•
Repita até que a tabela não tenha mais nenhuma linha:
1.Ordene a tabela de forma
decrescente segundo o número de vezes que os tons aparecem na imagem;
2.Combine as duas últimas
linhas da tabela (tons menos freqüentes) em uma única
linha, somando o número de ocorrências dos tons
combinados;
3.Armazene cada combinação
como sendo um nó de uma árvore binária cujos filhosvsão
as linhas combinadas.
•
Numere cada folha da árvore de acordo com o caminho para se chegar da folha até
ele
