Codificação de Huffman
A codificação de Huffman é um método de compressão que usa as probabilidades de ocorrência dos símbolos no conjunto de dados a ser comprimido para determinar códigos de tamanho variável para cada símbolo. Ele foi desenvolvido em 1952 por David A. Huffman que era, na época, estudante de doutorado no MIT, e foi publicado no artigo "A Method for the Construction of Minimum-Redundancy Codes".
Em 1951, a David A. Huffman e seus colegas da disciplina Teoria da Informação, no MIT, foram dadas a opção de fazer uma monografia ou um exame final. Seu professor, Robert M. Fano, designou um trabalho com a tarefa de se encontrar a codificação binária mais eficiente. Huffman, sem conseguir demonstrar que qualquer código que havia feito era o mais eficiente, estava à beira de começar a estudar para o exame final, até que teve a ideia de usar uma árvore binária utilizando frequências relativas para fazer a demonstração que precisava. Com isso, Huffman conseguiu fazer um código mais eficiente que seu professor, que trabalhava em Teoria da Informação com o próprio pioneiro dessa área do conhecimento, Claude Shannon. Construindo a árvore de codificação binária na metodologia bottom-up ao invés do top-down que a Codificação de Shannon-Fano utiliza.
Para atribuir aos caracteres mais frequentes os códigos binários de menor comprimento, constrói-se uma árvore binária baseada nas probabilidades de ocorrência de cada símbolo. Nesta árvore as folhas representam os símbolos presentes nos dados, associados com suas respectivas probabilidades de ocorrência. Os nós intermediários representam a soma das probabilidades de ocorrência de todos os símbolos presentes em suas ramificações e a raiz representa a soma da probabilidade de todos os símbolos no conjunto de dados. O processo se inicia pela junção dos dois símbolos de menor probabilidade, que são então unidos em um nó ao qual é atribuída a soma de suas probabilidades. Este novo nó é então tratado como se fosse uma folha da árvore, isto é, um dos símbolos do alfabeto, e comparado com os demais de acordo com sua probabilidade. O processo se repete até que todos os símbolos estejam unidos sob o nó raiz.
Compressão
Para ilustrar o funcionamento do método, vamos comprimir a sequência de caracteres AAAAAABBBBBCCCCDDDEEF. Se usarmos a forma padrão onde o tamanho da representação de cada caractere é fixo, a menor codificação que podemos utilizar para representá-la em binário é de três bits por caractere. Assim temos a seguinte codificação: Gerando assim a os bits 000000000000000000001001001001001010010010010011011011100100101 para representar nossa sequência original. Isso dá 63 bits de comprimento. Para usar o código Huffman e comprimir esta sequência precisamos primeiro montar uma árvore de Huffman seguindo os passos descritos acima. O primeiro passo é contar as ocorrências de cada símbolo na cadeia a ser comprimida. Com isso temos:
Descompressão
Generalizando, o processo de descompressão é simplesmente uma questão de se traduzir a palavra-código de volta para os caracteres. Isso é geralmente realizado percorrendo a árvore do código de nó em nó, conforme a orientação dada por cada bit lido da palavra-código, até encontrar-se uma folha. Ou seja, o processo resume-se a voltar, por meio do caminho na árvore, para a folha associada ao símbolo original.
A codificação de Huffman é amplamente utilizada em aplicações de compressão, que vão de GZIP, PKZIP, BZIP2 a formatos de imagens como JPEG e PNG. Isso ocorre pela codificação ser simples, rápida e, principalmente, não ter patente. Consequentemente, não se pagam royalties para utilização comercial de aplicações que empregam este método.
Otimização
Embora o algoritmo de Huffman seja ótimo para codificação símbolo a símbolo com uma distribuição de probabilidade conhecida, este não é ótimo quando a relação símbolo a símbolo não é mais necessariamente válida - ou quando a probabilidade por símbolo é desconhecida. Além disso, para determinados casos em que os símbolos não são independentes e com uma frequência relativa distribuída por símbolo, a codificação pode não ser ótima. Contudo, as limitações da codificação de Huffman não devem ser exageradas. Existem diversas variações deste código original, em que adaptações são feitas para grupos de casos em que não se obtinha um contexto de probabilidade favorável. Exemplos de tais variações do código incluem código n-ésimo de Huffman, Huffman adaptativo, codificação Huffman de mínima variância, Huffman canônico, dentre outros.
