Codificação de Huffman
Origem: Wikipédia, a enciclopédia livre.
A codificação de Huffman é um método de compressão que usa estatísticas do conjunto de dados a ser comprimido para determinar códigos de tamanho variável. Probabilidade de ocorrência são computadas em todos os possíveis valores na imagem e esses são então ordenados.
O menor código é associado aos dados com maior probabilidade de ocorrer e assim por diante. Desde que o código seja de tamanho variável, a associação de código é feita pela relação da menor probabilidade recursivamente até que uma árvore binária seja gerada com uma raiz de duas probabilidades.
[editar] Algoritmo
Para atribuir aos caracteres mais freqüentes as codificações menores e, como geralmente é usado código binário, constrói-se uma árvore binária a partir dos caracteres de menor valor de probabilidade onde os nós representam a soma da freqüência de ocorrência de todas as letras da subárvore correspondente e cujas folhas representam cada um dos caracteres da mensagem a ser codificada e sua freqüência. A codificação de cada símbolo será representação do caminho da raiz até ao símbolo.
- O alfabeto de entrada deve ser organizado em uma coluna em ordem decrescente de freqüência com sua probabilidade ou o seu número de ocorrência no texto.
- Defina um novo nó unindo dois cuja soma das probabilidades seja a menor possível.
- Calcule a probabilidade deste nó como a soma das probabilidades dos grupos unidos (nós).
- Para um dos nós filho usado para definir o novo nó atribuo o bit 0 e para o outro o bit 1.
- Se restar mais de um grupo (sub-árvores) vá para o passo 2, senão passe para o passo 6.
- Obter o código de cada letra pegando-se a seqüencia de bits atribuída aos grupos, da esquerda para a direita. Como o processo constitui uma estrutura de árvore binária, o código de cada elemento será a seqüência de bits da raiz até a folha que corresponde ao caractere.
O caractere de maior freqüência possui o menor comprimento que é exatamente a meta da compressão estatística. Assim acontece com os demais caracteres, em ordem proporcionalmente crescente do número de bits, conforme a propriedade:
[editar] Propriedade
O tamanho médio dos caracteres (TMC) é dado pelo somatório dos produtos do tamanho de cada caracter (T(c)) pela sua probabilidade de limitações (P(c)).
1
