Arvore de Huffman

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1480 palavras )
  • Download(s) : 0
  • Publicado : 14 de agosto de 2013
Ler documento completo
Amostra do texto
1.INTRODUÇÃO:
Este relatório irá abordar um tipo particular de arvore binária denominada
Arvore de Huffman, usada em codificação de informações. Através de exemplos será
mostrada também a construção da arvore de Huffman.
---------------------------------------------------------------------------------------------------------2.CONCEITOS:
2. 1.Árvores Binárias:
A figura abaixo mostra umimportante tipo de árvore chamada a árvore binária. Em
uma árvore binária cada nó tem no máximo dois filhos (subárvores), e quando há
somente um filho, torna-se necessário distinguir entre filho (subárvore) esquerdo e
direito. Um exemplo de arvore binária se encontra logo abaixo.

Arvore Binária
2.2.Código de Huffman:
Para enviar uma mensagem através de um cabo de transmissão, os caracteres damensagem são enviados um a um, modificados através de alguma tabela de codificação.
Em geral, este código forma um numero binário. Como a velocidade de transmissão é
importante, e interessante tornar a mensagem tão curta quanto possível sem perder a
capacidade de decodificar o texto enviado. Um algoritmo de determinação de códigos
binários de comprimentos variados para caracteres (não e o casoque cada caractere seja
representado com o mesmo numero de bits), baseado na frequência de uso destes
caracteres foi desenvolvido em 1952 por David A. Huffman que era, na época,
estudante de doutorado no MIT. A ideia e associar números binários com menos bits
aos caracteres mais usados num texto. Desta maneira espera se que o numero de bits
economizados para codificar os caracteres queocorrem com maior frequência em um
texto seja mais que o suficiente para cobrir o déficit que ocorrerão ao codificamos os
caracteres que ocorrem raramente com cadeias longas de bits.

Um dos requerimentos deste código é que nenhum código seja prefixo de outro,
caso a decodificação da mensagem seja feita da esquerda para direita.
O algoritmo de Huffman que será implementado para codificar umarquivo
consistira de três fases:


Primeira etapa:
A frequência de cada caractere que ocorre no texto devera ser calculada.



Segunda etapa:

Consiste em construir uma arvore binária baseada na frequência de uso destas
letras de modo que as que aparecem com mais frequência fiquem mais perto da raiz do
que as que aparecem com menos frequência. Este tipo de arvore é denominada arvorebinária de Huffman.
Em cada passo desta fase tem-se teremos uma coleção de arvores binárias, ou
seja, uma “floresta” formada por arvores binárias. As folhas de cada uma destas arvores
correspondem a um conjunto de caracteres que ocorrem no texto. A raiz de cada uma
destas arvores será associado um numero que corresponde à frequência com que os
caracteres associados às folhas desta arvoreocorrem no texto. Escolherem os então as
duas arvores desta floresta com a menor frequência e as transformarem os em uma única
arvore, ligando-as a uma nova raiz cujo valor será dado pela soma dos valores das
frequências das duas sub arvores.


Terceira etapa:

Nesta fase, a arvore de Huffman será usada para codificar e decodificar o texto.
A arvore de Huffamn construída durante a codificaçãoserá usada na decodificação (ela
será armazenada junto com o texto que foi codificado).
---------------------------------------------------------------------------------------------------------3.CONSTRUÇÃO DE UMA ARVORE DE HUFFMAN:
Supondo uma mensagem composta pelos caracteres A, B, C, D, E, R, supondo
também que a frequência de cada letra na mensagem seja respectivamente 22, 9, 10, 12,
16,8.
Caractere
A
B C
D
E
R
Frequência 22 9
10 12 16 8
Como foi exposto anteriormente, o algoritmo de Huffman constrói uma arvore
binária baseada na frequência de uso dessas letras de modo que as letras com maior
frequência (A e E) fiquem localizadas mais perto da raiz do que as que são usadas com
menor frequência (B e R).
A construção dessa arvore é recursiva, a partir da junção dos...
tracking img