21-06-2014, 01:10 PM
Algoritmo de Huffman
Algoritmo de Huffman.ppt (Size: 212 KB / Downloads: 359)
Código de Huffman
Algoritmo para a compressão de arquivos, principalmente arquivos textos
Atribui códigos menores para símbolos mais freqüentes e códigos maiores para símbolos menos freqüentes
Código é um conjunto de bits
Problema
Dada uma tabela de freqüências como determinar o melhor conjunto de códigos, ou seja, o conjunto que comprimirá mais os símbolos?
Huffman desenvolveu um algoritmo para isso e mostrou que o conjunto de símbolos obtidos é o melhor para conjuntos de dados que têm a freqüência de seus símbolos igual a tabela de freqüência usada
Informações de frequência
Algoritmo de Huffman produz tabela de códigos baseada em informações de freqüência
Dependência do tipo de dado primário
Processo
Cria-se um nó (nó folha) para cada símbolo da tabela de freqüência
Cria-se um vetor que aponta para cada um desses nós
Insere-se também esses nós em uma uma fila de prioridades (os nós menos freqüentes primeiro)
Notem: temos uma árvore E uma fila de prioridades
A árvore nós estamos construindo
A fila de prioridades nós usamos para construir a árvore
O processo termina quando todos os nós da fila de prioridades forem eliminados
Os últimos dois juntam-se e formam a raiz da árvore