Código de Huffman
Código de comprimento fixo
Poupado
Entropia

Símbolo Ocorrências Código Bits Bits no total

Mais informações sobre a codificação de Huffman

Construtor de códigos de Huffman

Porque é que uma letra comum como o a há de ocupar tantos bits como uma rara como o k? A codificação de Huffman dá códigos curtos aos símbolos frequentes e códigos longos aos raros, e fá-lo da melhor maneira possível. Escreva um texto ou escolha um exemplo e construa a sua árvore de Huffman um passo de cada vez: as duas árvores mais leves juntam-se sob um novo nó, uma e outra vez, até restar uma única árvore. Depois, cada caminho a partir do topo forma um código, e pode seguir cada símbolo ao longo dos bits codificados. Escreva um texto ou escolha um exemplo. Cada símbolo começa como uma folha com a sua contagem. Avance passo a passo na construção: cada passo junta as duas árvores mais leves sob um novo nó com a soma dos seus pesos, até restar uma única árvore. Depois, o caminho do topo até uma folha dá o seu código, 0 para a esquerda e 1 para a direita. Clique numa folha, numa linha ou num troço dos bits para seguir um símbolo, e compare o total com um código de comprimento fixo e com a entropia.

Como funciona

  1. Escreva ou cole um texto, ou escolha um exemplo como ABRACADABRA ou MISSISSIPPI RIVER.
  2. Avance na construção com Passo seguinte, ou carregue em Reproduzir: cada passo junta as duas árvores mais leves sob um nó com a soma dos seus pesos.
  3. Quando a árvore estiver completa, clique numa folha, numa linha da tabela ou num troço dos bits para seguir um símbolo, e compare os totais nos painéis.

Como a árvore é construída

Conte quantas vezes ocorre cada símbolo e faça de cada um uma árvore com uma única folha, com o peso da sua contagem. Depois repita um passo simples: pegue nas duas árvores com os pesos mais pequenos e pendure-as sob um novo nó cujo peso é a soma dos dois. Cada passo deixa menos uma árvore, por isso, ao fim de n − 1 passos para n símbolos, resta uma única árvore. Os símbolos raros foram juntados primeiro e ficam lá em baixo; os comuns foram juntados tarde e ficam perto do topo.

Ler os códigos

Desça a partir do topo: um passo para a esquerda acrescenta um 0, um passo para a direita um 1. O caminho até uma folha é o código desse símbolo. Como os símbolos só estão nas folhas, nenhum código é o início de outro, por isso uma sequência de bits pode ser descodificada sem separadores: siga os bits pela árvore abaixo e, sempre que chegar a uma folha, escreva o seu símbolo e recomece no topo. Para ABRACADABRA, o Huffman precisa de 23 bits, contra 33 para um código fixo de 3 bits por letra.

Perguntas frequentes

Porque é que o código de Huffman é o melhor possível?

De todos os códigos que dão a cada símbolo a sua própria sequência de bits inteiros, nenhum tem um total mais curto para as contagens dadas. A demonstração segue a construção: num código ótimo, os dois símbolos mais raros podem sempre ser postos como irmãos no nível mais profundo, e juntá-los deixa um problema mais pequeno do mesmo tipo. O número total de bits é igual à soma dos pesos de todos os nós internos da árvore.

O que é um código de prefixo?

Um código em que nenhuma palavra de código é o início de outra, como 0, 10, 110 e 111. Essa propriedade permite a um descodificador ler um fluxo de bits sem separadores, porque sabe sempre onde acaba uma palavra de código. Todo o código de Huffman é um código de prefixo: os símbolos estão apenas nas folhas da árvore.

A árvore de Huffman é única?

Não exatamente: quando duas árvores têm o mesmo peso, qualquer uma pode ser escolhida primeiro, e a esquerda e a direita podem ser trocadas. Escolhas diferentes dão códigos diferentes, mas sempre o mesmo número total de bits. O construtor resolve os empates sempre da mesma maneira, por isso um texto dá sempre a mesma árvore.

Quão perto da entropia chega o Huffman?

O comprimento médio dos códigos é pelo menos igual à entropia e fica menos de um bit acima dela. É igual à entropia quando todas as probabilidades são potências de um meio, como no exemplo das contagens que se reduzem a metade. A codificação aritmética e os codificadores de intervalo modernos evitam o limite dos bits inteiros e aproximam-se ainda mais.

O meu texto é enviado para algum lado?

Não. A árvore e os códigos são calculados no seu navegador, e o seu texto fica no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor