Algoritmo de huffman

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (431 palavras )
  • Download(s) : 0
  • Publicado : 20 de março de 2013
Ler documento completo
Amostra do texto
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 MontesCelinski.

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 prefixoe 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. Oalgoritmo 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çocomputacional 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 comcomprimento 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 é repetidogradualmente 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...
tracking img