Huffman

*

Universidade Federal Fluminense de
Rio das Ostras

*
A codificação de Huffman é uma técnica de compressão sem perdas de dados 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, visando atribuir aos símbolos de alta frequência no conjunto de dados uma curta sequencia de bits.

Foi desenvolvido
Huffman
que era, de doutorado no MIT.

em 1952 por na época,

David A. estudante Sendo publicado no artigo “A Method for the
Construction
of
Minimum-Redundancy
Codes”.

*
Uma árvore binária completa, chamada de árvore de Huffman é construída recursivamente a partir da junção dos dois símbolos de menor probabilidade, que são então somados em símbolos auxiliares e estes símbolos auxiliares recolocados no conjunto de símbolos. O processo termina quando todos os símbolos foram unidos em símbolos auxiliares, formando uma árvore binária. A árvore é então percorrida, atribuindo-se valores binários de 1 para arestas a direita do nó ou 0 para arestas a esquerda do nó, e os códigos são gerados a partir desse percurso.

*
Vamos usar a palavra: RIO DAS OSTRAS
A palavra é composta por 12 letras.
R=2 I=1 O=2 D=1 A=2 S=3 T=1
Primeiramente calculamos o percentual de ocorrência de cada símbolo e os ordenamos por ordem decrescente de frequência.
S(3)=25,3% R(2)=16,6% O(2)=16,6% A(2)=16,6%
I(1)=8,3% D(1)=8,3% T(1)=8,3%

Selecionamos agora dois elementos de menor frequência que formaram um nó na arvore.
N1

T

D

Feito isso iremos agora somar suas porcentagens, obtendo um novo elemento na lista de símbolos que será reordenada.
S(3)=25,3% R(2)=16,6% O(2)=16,6% A(2)=16,6% N1=16,6%
I(1)=8,3%

Novamente selecionamos os elementos de menor frequência formando um novo nó da arvore.
N1

N2

I

A

T

D

S(3)=25,3% N2=24,9% R(2)=16,6%
O(2)=16,6% N1=16,6%
Reordenamos a lista e repetimos esse
processo