# data[].attributes.body
Em 1951, David A. Huffman e seus colegas da disciplina Teoria da Informação no MIT se depararam com a escolha entre escrever uma monografia ou fazer um exame final como parte de seu curso. Seu professor, Robert M. Fano, lhes atribuiu a tarefa de encontrar a codificação binária mais eficiente. Huffman, inicialmente incapaz de provar que qualquer código que ele havia desenvolvido era o mais eficiente, estava prestes a começar a se preparar para o exame final.

No entanto, em um momento de insight, Huffman teve a ideia de utilizar uma abordagem baseada em uma árvore binária que levaria em consideração as frequências relativas dos caracteres. Isso permitiria a ele demonstrar a eficiência de sua codificação de maneira convincente.

Graças a essa ideia inovadora, Huffman foi capaz de criar um código binário mais eficiente do que aquele desenvolvido por seu próprio professor, que era um renomado especialista em Teoria da Informação e tinha colaborado com o pioneiro dessa área, Claude Shannon. A abordagem de Huffman envolveu a construção da árvore de codificação binária de baixo para cima, ao contrário do método top-down usado na Codificação de Shannon-Fano.

Essa realização de Huffman representou um avanço significativo na área da compressão de dados e contribuiu para o desenvolvimento de técnicas de codificação eficientes que são amplamente usadas até hoje.

Em anexo temos o artigo: A Method for the Construction of Minimum-Redundancy Codes, desenvolvido por David A. Huffman, em 1952.

# data[].attributes.body
Para realizar a busca na árvore de Huffman, é possível realizar a busca em profundidade na árvore da forma a seguir.

# data[].attributes.body
Código de Huffman está morto? (Ano não disponível)

# data[].attributes.body
Um código em cadeia eficiente com codificação Huffman - 2004

# data[].attributes.attachment_caption
 Construção de árvores representativas de códigos binários tendo início com n = |A| árvores triviais.

# data[].attributes.body
Note que o algoritmo pode ser facilmente implementado em tempo Θ(n 2 ) no pior caso: existem Θ(n) chamadas recursivas pois essa é a quantidade total de uniões que faremos, e uma chamada pode levar tempo Θ(n) para encontrar os dois símbolos de menor frequência (procurando-os de maneira simples dentre todos os disponíveis). Uma forma de melhorar esse tempo é usando uma estrutura de dados apropriada. Note que a operação que mais leva tempo é a de encontrar os dois símbolos de menor frequência. Assim, podemos usar a estrutura heap, que fornece remoção do elemento de maior prioridade (no caso, o de menor frequência) em tempo O(log n) sobre um conjunto de n elementos. Ela também fornece inserção em tempo O(log n), o que precisa ser feito quando o novo símbolo é criado e sua frequência definida como a soma das frequências dos símbolos anteriores. Assim, o tempo total do algoritmo melhora para Θ(n log n) no pior caso.

# data[].attributes.body
Apresentação que aborda uma visão geral do assunto:
- Conceitos
- Métricas
- Terminologia
- Implementação

# data[].attributes.attachment_caption
Implementação da Árvore de Huffman em Python

# data[].attributes.body
Vídeo criado para exemplificar passo-a-passo como funciona a compressão de texto com a árvore de Huffman através da compressão da palavra "abacate".

# data[].attributes.attachment_link.title
Simples compressão de textos com árvores de Huffman - Passo a passo.

# data[].attributes.body
A aplicação mais comum da árvore de Huffman: Compressão de textos

# data[].attributes.attachment_link.title
How Computers Compress Text: Huffman Coding and Huffman Trees

# data[].attributes.headline
Implementação no Colab junto com a explicação do código

# data[].attributes.subject
Implementação no Colab junto com a explicação do código

# data[].attributes.body
Vídeo-aula que explica:

O que é e como funciona uma Trie, assunto importante para entender a árvore de Huffman.

O que é e como funciona o Algoritmo de Huffman.

# data[].attributes.body
Gif que ilustra o funcionamento do algoritmo de Huffman.

# data[].attributes.headline
International Conference on Innovative Computing Technology

# data[].attributes.subject
International Conference on Innovative Computing Technology

# data[].attributes.body
Comparação de desempenho da codificação Huffman eCodificação Dupla Huffman - 2016

# data[].attributes.body
Outra aplicação comum da árvore de Huffman baseado em um estudo da Universidade de Stanford no ano de 2009: Compressão de áudio

# data[].attributes.body
No processo de inserção na árvore, o passo é feito no processo de "encoding", onde cada letra da palavra em questão é inserida em um dicionário que corresponde a um valor inteiro com a frequência da letra na palavra.