Arvore de Huffman

1480 palavras 6 páginas
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 um importante 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 da mensagem 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 caso que 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 que ocorrem 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 um

Relacionados

  • Algoritmo de Compressão
    2264 palavras | 10 páginas
  • COMPACTA O SEM PERDA PELO M TODO DE HUFFMAN ASSOCIADO TRANSFORMADA DE WAVELET 0f482e2f 7d77 4de9 9e1e ca4110e5d693
    11070 palavras | 45 páginas
  • Codigo Deflate LZ77
    3871 palavras | 16 páginas
  • codifica o de huffman
    1987 palavras | 8 páginas
  • relatorio
    418 palavras | 2 páginas
  • Projeto
    1997 palavras | 8 páginas
  • Compactacao e compressao
    2040 palavras | 9 páginas
  • Algoritmo de huffman
    431 palavras | 2 páginas
  • codigos de huffman
    936 palavras | 4 páginas
  • Straight Line Distance
    1611 palavras | 7 páginas