Huffman

Disponível somente no TrabalhosFeitos
  • Páginas : 4 (893 palavras )
  • Download(s) : 0
  • Publicado : 16 de julho de 2013
Ler documento completo
Amostra do texto
*


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 noconjunto
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 debits.

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-RedundancyCodes”.

*
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ímbolosauxiliares 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 apalavra: 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 defrequê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

Feitoisso 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%

Novamenteselecionamos 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...
tracking img