Algoritmo de huffman

UNIVERSIDADE ESTADUAL DE PONTA GROSSA SETOR DE CIÊNCIAS AGRÁRIAS E DE TECNOLOGIA DEPARTAMENTO DE INFORMÁTICA

MÁRCIO AUGUSTO CAMPOS POMPERMAIER

ALGORITMO DE HUFFMAN

Ponta Grossa 2012

MÁRCIO AUGUSTO CAMPOS POMPERMAIER

ALGORITMO DE HUFFMAN

Trabalho do Algoritmo de Huffman (compreensão de textos), apresentado a disciplina de Análise de Algoritmos a Professoar Doutora Tatiana Montes Celinski.

Ponta Grossa 2012

ALGORITMO DE HUFFMAN

Uma das melhores técnicas de compressão conhecidas é a de Huffman. Para uma dada distribuição de probabilidades gera um código livre de prefixo e redundância mínima, além de produzir uma sequência de bits aleatórios. Utiliza códigos de tamanho variável para representar os símbolos do texto, que podem ser caracteres ou cadeias de caracteres (digramas, trigramas, n-gramas ou palavras). A ideia básica do algoritmo é atribuir códigos de bits menores para os símbolos mais frequentes no texto, e códigos mais longos para os mais raros. O algoritmo de Huffman original baseia-se no método guloso e constrói um código ótimo com esforço computacional O(n.logn). Existem novas versões que constroem o código de Huffman com esforço computacional O(n), mas e necessário que as frequências já estejam ordenadas. Como o problema de ordenação tem cota inferior Ω(n.logn), isto é, não existe um algoritmo que consiga ordenar as frequências com esforço computacional menor, o esforço computacional para construir o código de Huffman é Θ(n.logn). Ou seja, Huffman funciona em uma lista de pesos através da construção de uma

árvore binária estendida com comprimento do caminho mínimo ponderado externo e passa por encontrar as duas menores um nó interno de peso s, e , visto como nós externos, e substituindo-os por

. O procedimento é repetido gradualmente até que o nó de

raiz é alcançado. Um nó individual externo pode, então, ser codificado por uma sequência binária de 0s (por ramificações da esquerda) e 1s (para o ramo direito).

O