Disponível somente no TrabalhosFeitos 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...
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...
Ler documento completo
Por favor, assinar para o acesso.
