O Algoritmo de Huffman

Resumo. Este método de compressão é um dos mais utilizados na atualidade para comprimir diversos arquivos. A sua designação deriva de David Huffman, que desenvolveu o método como projeto da disciplina Teoria da Informação em 1950 enquanto aluno do doutorado no MIT e publicou as suas conclusões no ano de 1952 em um artigo. O algoritmo de Huffman é baseado na categoria de Codificação de Entropia – a informação é encarada como uma sequência de símbolos genéricos, menosprezando a semântica dos mesmos -, sendo um modo de codificação sem perdas – o código resultante é totalmente reversível, ou seja, a sua descodificação resulta num fluxo de dados exatamente igual ao fluxo de dados de origem.

Abstract. This method of compression is one of the most used today to compress several files. His designation stems from David Huffman, who developed the method as a project of Information Theory in 1950 as a Ph.D. student at MIT and published his findings in the year 1952 in an article. The Huffman algorithm is based on the category of Entropy Encoding - information is regarded as a generic symbol sequence, belittling its semantics - being a lossless encoding mode - the resulting code is fully reversible, its decoding results in a data stream exactly equal to the source data stream.

1. DEFINIÇÃO

O algoritmo de Huffman, segundo Feofiloff (2017), é um algoritmo que comprime fluxos de bits: ele retorna uma representação comprimida de um fluxo recebido. Assim, ele costuma ser utilizado para compressão de arquivos, como, por exemplo, extensões MP3, JPEG, PNG, RAR, entre outras.

O fluxo que entra é lido de 8 em 8 bits, cada uma dessas sequências representando um caractere em número binário. Essas sequências são então convertidas em uma cadeia menor de bits. O algoritmo cria códigos curtos para os caracteres mais frequentes e códigos maiores para caracteres menos frequentes. O algoritmo de Huffman não é utilizado apenas para caracteres, apesar de ser mais usado desta forma.

As duas principais etapas na codificação de Huffman são a construção de uma árvore de Huffman com o input dos caracteres originais e a travessia desta árvore binária para a atribuição de códigos para cada caractere.

O input, além de um array de caracteres em seus códigos originais, recebe também a frequência na qual estes caracteres aparecem. O output vai ser a árvore Huffman pronta. As folhas da árvore são os caracteres. A raiz tem valor de 1. Os nós internos são os valores da porcentagem de frequência. O pai de uma folha é a porcentagem de frequência daquele caractere. O pai deste nó de porcentagem é a adição da porcentagem dos irmãos. Cada nível da árvore vai adicionando porcentagens até chegar a 1 (raiz). Para a raiz, em vez do número 1, pode também ser usado o número total de caracteres, e o número de aparições de cada caractere em vez de porcentagens.

Para formar essa estrutura, então, primeiro é necessário uma fila de prioridade com cada caractere e sua frequência. São selecionados os dois caracteres menos frequentes. Eles geram um nó pai cujo valor é a adição da frequência dos dois filhos. Esse processo é repetido para os dois próximos caracteres menos frequentes. Assim, os dois pais dos quatro caracteres tem as suas frequências também adicionadas, gerando um novo nó. Desta forma, é possível ver que