David Huffman foi um estudante de computação que se dispôs a se debruçar sobre o problema de codificação de caracteres em binários. Após vários meses de estudo, tentativa e erros ele chegou no que hoje conhecemos como árvores de Huffman.

O funcionamento das árvores de Huffman são ao mesmo tempo simples e eficiente. A ideia do algoritmo é quanto menos vezes um símbolo aparece, mais distante ele irá ficar da raiz da árvore, e logicamente quanto mais vezes ele aparece, mais próximo ele estará perto da raiz.

Outro passo essencial para que a árvore possa se bifurcar quando necessário é que todo símbolo seja uma folha, e nunca um nodo da árvore. Vamos começar com a cadeia de caracteres "AACBAAABAC". O Primeiro passo é, conferir o número de vezes que cada símbolo aparece. Nesse caso: A -> 6 , B & C -> 2.

Sabendo disso, já temos que a letra que irá ficar mais próxima da raiz. Como temos apenas três letras fica fácil de montar a árvore. Nos exemplos, irei representar no nodo o número de caracteres restante, mais para ficar mais claro podemos usar os símbolos que estão a partir daquele ramo. Esse foi o primeiro passo para construirmos a árvore, mas ainda precisamos construir a representação binária a partir da árvore, o que é tão simples quanto o passo anterior, a única coisa à fazer é definir se o caminho será representado por um ou por zero em cada bifurcação, e então quando chegarmos em uma folha juntamos todos os bits do caminho até chegarmos no ponto desejado e assim teremos a representação binária para um determinado símbolo. Neste exemplo temos a representação da letra B. Considerando que para as bifurcações escolhemos primeiramente um à esquerda e zero à direita e no ramo seguinte o contrário. Para chegar na representação do "B" tudo que precisamos fazer é sair da raiz e percorrer a árvore até o B juntando todos símbolos binários que se encontram no mesmo caminho (nesse caso primeiro o zero o depois o um), assim descobrimos a representação de B como sendo 01. Aplicando esta mesma regra para as outras letras, chegamos a árvore completa. Para melhor fixação do algoritmo também deixarei uma árvore com dois erros, se você encontrar deixe a resposta nos comentários. Não haverá prêmio além da satisfação de ter encontrado e uma leve massagem no ego. : ) Aqui o link para o árvore correta.

Fontes:

• Huffmann Tree Generator
• Huffmann Encoding trees
• A quick tutorial a generate o Huffmann tree