Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Algoritmo de Huffman

Trabalho apresentado à disciplina de Teoria dos Grafos, solicitado pela professora Christine Vieira, do curso de Ciência da Computação da Universidade do Extremo Sul Catarinense - UNESC.
by

Juliana Braz

on 26 June 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Algoritmo de Huffman

Desafio lançado em um trabalho de pós-graduação em engenharia elétrica, no ano de 1951;

Desenvolvido por David Huffman durante a pós-graduação em engenharia elétrica;
Como surgiu?
ALGORITMO DE HUFFMAN
Encontrar o método mais eficiente de representar números, letras e outros símbolos usando um código binário.

Que faz com que a informação fique comprimida para transmissão através de uma rede de computadores ou para armazenamento na memória.
O problema
Huffman tentou encontrar uma maneira de comprimir os caracteres mais utilizados em outro código que não se repita.
A criação de Huffman
É realizado pela formação de uma árvore de codificação, no qual a probabilidade de que um número, letra ou outro carácter ocorra é designado como uma folha de uma árvore.
O processo
1. Verifica o texto a ser comprimido e conta as ocorrências de todos os caracteres.

2. Classifica e cria prioridades para os caracteres, baseados no número de ocorrências no texto.



O algoritmo
3. Constrói a árvore de Huffman com base em lista de prioridades, que foi estabelecida nos passos anteriores.

4. Realiza o percurso da árvore para determinar todos os caracteres.

5. Verifica novamente o texto e cria um novo arquivo utilizando o código de
Huffman.
Frase:
arara azul
Exemplo
Trabalho apresentado à disciplina de Teoria dos Grafos, solicitado pela professora Christine Vieira, do curso de Ciência da Computação da Universidade do Extremo Sul Catarinense - UNESC.
Acadêmicos:
Caroline Salib Canto
Felipe Borges Tomaz
Helder Rocha da Silva
Juliana Chaves Braz da Silva

Tabela de frequências
Figura: Árvore final
Referências
Disponível em: <http://www.huffmancoding.com/my-uncle/huffman-algorithm>. Acesso em 26 jun. 2014.
Codificação
Tabela de codificação
Codificação final:
0011110011110000110010111000
Árvore da frase:
Arara Azul
Criação da árvore
Figura: Esquema de criação da árvore
Full transcript