Codificação de Huffman explicada
Os computadores guardam normalmente cada letra no mesmo número de bits, oito em ASCII simples. É simples, mas desperdiça espaço, porque algumas letras são muito mais comuns do que outras. Em 1951, um estudante descobriu a melhor maneira de dar a cada símbolo um código com o seu próprio comprimento, curto para os símbolos frequentes e longo para os raros, com uma construção tão simples que cabe em poucas linhas. A codificação de Huffman está hoje dentro de quase todos os ficheiros comprimidos, imagens e sons que abre.
Códigos curtos para símbolos comuns
O código Morse já usava a ideia na década de 1830: o E, a letra mais comum em inglês, é um único ponto, enquanto o Q é traço traço ponto traço. Um código assim poupa tempo e espaço sempre que alguns símbolos ocorrem mais vezes do que outros. Mas os comprimentos variáveis levantam um problema que o Morse resolveu com pausas: como se sabe onde acaba um código e começa o seguinte? E que comprimentos deve receber cada símbolo para que o total seja o mais pequeno possível?
Códigos de prefixo
O primeiro problema desaparece se nenhum código for o início de outro. Com os códigos A = 0, B = 10, C = 110 e D = 111, os bits 0101100 só podem ser lidos como A B C A: assim que os bits lidos até ao momento formam um código, esse código está completo. Estes códigos de prefixo correspondem exatamente a árvores binárias com os símbolos nas folhas, em que cada ramo para a esquerda representa 0 e cada ramo para a direita 1. Escolher um código é escolher uma árvore.
A construção de Huffman
Comece com uma folha por símbolo, com o peso do número de vezes que ocorre. Pegue nas duas árvores mais leves e junte-as sob um novo nó cujo peso é a soma dos dois, e repita até restar uma única árvore. É esse o algoritmo inteiro. Os símbolos raros são juntados primeiro e acabam no fundo da árvore, com códigos longos; os comuns são juntados por último e ficam perto do topo, com códigos curtos. Com uma fila de prioridade, demora um tempo proporcional a n log n para n símbolos.
Porque é ótimo
Numa árvore ótima, os dois símbolos mais raros podem sempre ser colocados como irmãos no nível mais profundo: trocá-los com o que lá estiver só pode encurtar o total. Junte-os num único símbolo com o peso combinado e o resto é o mesmo problema com menos um símbolo, por isso o passo guloso nunca afasta a melhor resposta. O número total de bits usados é igual à soma dos pesos de todos os nós internos, que as junções mantêm o mais pequena possível.
Um trabalho em vez de um exame
Em 1951, David Huffman, estudante de pós-graduação no MIT, frequentou a cadeira de teoria da informação de Robert Fano. Fano deu aos alunos uma escolha: fazer o exame final ou escrever um trabalho sobre como encontrar o código binário mais eficiente. Huffman esteve quase a desistir do trabalho, mas depois percebeu que construir a árvore de baixo para cima, em vez de a dividir de cima para baixo como no método de Shannon–Fano, dá sempre o melhor resultado. Publicou-o em 1952; o método do aluno superou o que o seu professor tinha desenvolvido com Claude Shannon.
Perto da entropia
Claude Shannon mostrou que nenhum código pode usar, em média, menos bits por símbolo do que a entropia da fonte. Um código de Huffman atinge exatamente a entropia quando todas as probabilidades são potências de um meio, e nunca fica um bit inteiro por símbolo acima dela. A diferença pesa quando um símbolo é muito comum: um símbolo com 99% de frequência continua a precisar de pelo menos um bit inteiro, embora transporte apenas cerca de 0,015 bits de informação. A codificação aritmética e os sistemas numéricos assimétricos dos compressores mais recentes evitam esse limite.
Códigos de Huffman em todo o lado
A codificação de Huffman raramente é usada sozinha, mas é a última etapa de muitos formatos. O deflate, dentro do ZIP, do gzip e do PNG, primeiro substitui as repetições por referências e depois escreve o resultado com códigos de Huffman. O JPEG usa-os para os números que restam depois da transformação da imagem, o MP3 para os seus dados de áudio e as máquinas de fax para os comprimentos das sequências de preto e branco. Os formatos enviam normalmente um código de Huffman canónico, em que só é preciso guardar os comprimentos dos códigos, porque os próprios códigos podem ser reconstruídos a partir deles.
Explore
Abra o construtor de códigos de Huffman para construir, um passo de cada vez, a árvore de ABRACADABRA, de MISSISSIPPI RIVER, de uma frase sua ou de qualquer outro texto. Veja as duas árvores mais leves juntarem-se a cada passo, clique numa folha para ver o seu código, siga um símbolo ao longo dos bits codificados e compare o total com um código de comprimento fixo, com o UTF-8 e com a entropia.
Perguntas frequentes
Qual é a diferença entre a codificação de Huffman e a de Shannon–Fano?
A codificação de Shannon–Fano constrói a árvore a partir do topo, dividindo os símbolos uma e outra vez em dois grupos de peso quase igual. Muitas vezes é boa, mas nem sempre é ótima. O Huffman constrói a árvore a partir de baixo, juntando as duas árvores mais leves, e dá sempre o código de prefixo mais curto possível.
O descodificador precisa da árvore?
Sim, precisa do mesmo código. Por isso, os ficheiros comprimidos guardam-no, normalmente como uma lista de comprimentos de código para um código canónico, o que ocupa apenas algumas dezenas de bytes. Em textos curtos, essa sobrecarga pode superar a poupança; o construtor conta apenas os bits codificados.
A codificação de Huffman pode tornar um ficheiro maior?
Os símbolos codificados nunca ocupam mais bits do que um código de comprimento fixo para os mesmos símbolos. Mas a tabela de códigos também tem de ser guardada, por isso, para dados muito curtos ou quase aleatórios, o resultado pode ficar ligeiramente maior do que o original.
O que diz a desigualdade de Kraft?
Que existe um código de prefixo com comprimentos de código l₁, l₂, … exatamente quando a soma de 2 elevado a −l sobre todos os símbolos é no máximo 1. Para uma árvore completa, como qualquer árvore de Huffman com pelo menos dois símbolos, a soma é exatamente 1.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Abrir o construtor de códigos de Huffman