UFSM-CTISM
Comunicação de Dados
Aula-16
CÓDIGOS DE HUFFMAN
Professor:
Andrei Piccinini Legg
Santa Maria, 2012
CÓDIGOS DE HUFFMAN
Definição:
A codificação de Huffman é uma técnica para a
compressão de dados, amplamente usada e muito efetiva.
Exemplo:
Um arquivo contem 100.000 caracteres. Se sabe que é
composto apenas por 6 caracteres diferentes e a frequência
de aparição de cada um deles é:
Frequência
a
45
b
13
c
12
d
16
e
9
f
5
Como codificar os caracteres para comprimir o espaço
ocupado utilizando um código binário?
Solução 2
Código de comprimento variable, as palavras com maior
frequência possuem o rótulo mais curto. Restrição: nenhum
rótulo pode ser prefixo de outro.(224000 bits)
comprimento variável
a
0
b
101
c
100
d
111
e
1101
f
1100
Solução 2
comprimento variável
a
0
b
101
c
100
d
111
e
1101
f
1100
Esta técnica de codificação se denomina de código
prefixo.
Codificação: Basta concatenar o código de cada um
dos caracteres.
Exemplo :
aabacd ⇒ 0-0-101-0-100-111 ⇒ 001010100111
Decodificação: Fácil porque nenhuma palavra do
código é prefixo do outra. Não existe ambiguidade.
Exemplo :
001010100111 ⇒ aabacd
Solução 2
Uma estrutura em árvore é uma forma de representar o
código prefixo que simplifica o processo de decodificação:
As folhas são os símbolos;
O caminho da raiz até as folhas com o 0 para esquerda
e 1 para direita corresponde ao código para cada folha.
100
1
0
86
14
0
1
58
0
a : 45
0
28
1
b : 13
0
c : 12
14
1
d : 16
0
e:9
Comprimento fixo!
1
f :5
Solução 2
100
1
0
55
a : 45
0
1
25
0
b : 13
30
1
0
1
c : 12
14
d : 16
0
f :5
1
e:9
Comprimento variável!
Algoritmo Greedy
Huffman inventou um algoritmo simples para construir um
código prefixo ótimo.
passo 1
Dada uma distribuição de frequência (probabilidade) para o
aparecimento dos símbolos, coloca-la em ordem crescente:
Frequência
a
42
b
13
c
8
d
15
e
12
f
4
g
6
c
8
g
6
f
4
Colocando em ordem crescente temos:
Frequência
a
42
d
15
b
13
e
12
Algoritmo Greedy
Huffman inventou um algoritmo simples para construir um
código prefixo ótimo.
passo 2
Vamos começar a estruturar nossa arvore partindo dos
últimos dois símbolos (os com menor probabilidade de
transmissão), e reordenar as probabilidades em na ordem
crescente. Esse passo será repetido diversas vezes.
Acompanhem o procedimento.
Algoritmo Greedy
Huffman inventou um algoritmo simples para construir um
código prefixo ótimo.
a : 42
a : 42
d : 15
d : 15
b : 13
b : 13
e : 12
e : 12
c:8
10
1
g:6
f :4
c:8
0
Algoritmo Greedy
Huffman inventou um algoritmo simples para construir um
código prefixo ótimo.
a : 42
a : 42
a : 42
d : 15
d : 15
18
b : 13
b : 13
d : 15
e : 12
e : 12
b : 13
1
c:8
1
g:6
f :4
e : 12
10
0
c:8
0
Algoritmo Greedy
Huffman inventou um algoritmo simples para construir um
código prefixo ótimo.
a : 42
a : 42
a : 42
a : 42
d : 15
d : 15
18
25
b : 13
b : 13
d : 15
18
1
e : 12
e : 12
0
1
c:8
1
f :4
e : 12
10
g:6
0
c:8
0
d : 15
b : 13
Algoritmo Greedy
Huffman inventou um algoritmo simples para construir um
código prefixo ótimo.
a : 42
a : 42
a : 42
a : 42
a : 42
d : 15
d : 15
18
25
33
b : 13
b : 13
d : 15
18
1
25
1
0
e : 12
e : 12
c:8
10
0
1
1
g:6
f :4
0
e : 12
0
c:8
d : 15
b : 13
Algoritmo Greedy
Huffman inventou um algoritmo simples para construir um
código prefixo ótimo.
a : 42
a : 42
a : 42
a : 42
a : 42
d : 15
d : 15
18
25
33
b : 13
b : 13
d : 15
18
e : 12
e : 12
b : 13
c:8
10
58
1
1
0
25
1
0
0
1
1
g:6
f :4
0
e : 12
0
c:8
d : 15
a : 42
Algoritmo Greedy
Huffman inventou um algoritmo simples para construir um
código prefixo ótimo.
a : 42
a : 42
a : 42
a : 42
a : 42
d : 15
d : 15
18
25
33
b : 13
b : 13
d : 15
18
e : 12
e : 12
b : 13
c:8
10
58
1
1
0
25
1
0
0
1
1
g:6
f :4
0
e : 12
0
c:8
d : 15
a : 42
1
0
100