aula07_compressao

Prévia do material em texto

CMCC
BC-0504: Natureza da 
Informação
 
Códigos efiientes
Prof. Thiago F. Covões
baseado nos slides do Prof. Fabrício Olivetti e 
Profa. Mirtha Lina
Introdução
• Telégrafo, década de 1830
• Samuel F. B. Morse (1791-1872)
• Um dos principais contribuidores para o desenvolvimento do 
telégrafo e do código Morse.
• Transmissão 
• Ex. Sinais elétricos
Introdução
• Código Morse
• Espaços 
• ausência de corrente
• Pontos 
• corrente de curta duração 
• Traços
• corrente de longa duração
Introdução
• Código “efciente”
• Símbolos mais frequentes
• Códigos “mais curtos”
• Ex.
• Letra “E”
• Bastante frequente na 
língua inglesa.
Códigos efcientes
• Estratégia
• Símbolos mais frequentes
• Códigos “mais curtos”
• Símbolos menos frequentes
• Códigos “mais compridos”
Códigos efcientes
• Estratégia
• Símbolos mais frequentes
• Códigos “mais curtos”
• Símbolos menos frequentes
• Códigos “mais compridos”
• Em outras palavras
• Símbolos com maior probabilidade de ocorrência
• Códigos “mais curtos”
• Símbolos menor probabilidade
• Códigos “mais compridos”
EXEMPLO
 Moeda viciada:
 1: cara 0: coroa
 p(1) = 1/1000
 Pergunta
 Quantos bits são necessários
para transmitir esta informação?
00000100............000000100000.......0001
Em 1 milhão de Em 1 milhão de 
jogadas, espera-jogadas, espera-
se uma média de se uma média de 
1000 caras.1000 caras.
EXEMPLO
 Moeda viciada:
 1: cara 0: coroa
 p(1) = 1/1000
00000100............000000100000.......0001
H
EXEMPLO
 Idéia:
 Em 1 milhão de lançamentos, espera-se obter na média 
algo em torno de 1000 caras...
 Transmitir a posição de cada bit ‘1’...
00000100............000000100000.......0001
EXEMPLO
 Idéia:
 Como identifcar a posição de um 1 
dentre os 1 milhão de lançamentos?
00000100............000000100000.......0001
EXEMPLO
 Idéia:
 Como identifcar a posição de um 1 
dentre 2 lançamentos?
EXEMPLO
 Idéia:
 Como identifcar a posição de um 1 
dentre 2 lançamentos?
 Pergunta: A posição é maior que 1?
k = 2 folhas
Altura
h = 1
SimNão
1 2
EXEMPLO
 Idéia:
 Como identifcar a posição de um 1 
dentre 4 lançamentos?
k = 4 folhas
Altura
h = 2
1 32 4
EXEMPLO
 Idéia:
 Como identifcar a posição de um 1 
dentre 4 lançamentos?
 Pergunta 1: A posição é maior que 2?
SimNão
k = 4 folhas
Altura
h = 2
1 32 4
EXEMPLO
 Idéia:
 Como identifcar a posição de um 1 
dentre 4 lançamentos?
 Pergunta 1: A posição é maior que 2?
 Pergunta 2: A posição é maior que 1?
SimNão
k = 4 folhas
Altura
h = 2
Não
1 32 4
EXEMPLO
 Idéia:
 Como identifcar a posição de um 1 
dentre 4 lançamentos?
 Pergunta 1: A posição é maior que 2?
 Pergunta 2: A posição é maior que 3?
SimNão
k = 4 folhas
Altura
h = 2
1 32 4
Sim
EXEMPLO
 Idéia:
 Para identifcar a posição de um 1 dentre
 2 lançamentos: 1 pergunta
 4 lançamentos: 2 perguntas
EXEMPLO
 Idéia:
 Para identifcar a posição de um 1 dentre
 2 lançamentos: 1 pergunta
 4 lançamentos: 2 perguntas
 8 lançamentos?
k = 8 folhas
Altura
h = 3
1 32 4 5 76 8
EXEMPLO
 Idéia:
 Para identifcar a posição de um 1 dentre
 2 lançamentos: 1 pergunta
 4 lançamentos: 2 perguntas
 8 lançamentos: 3 perguntas
k = 8 folhas
Altura
h = 3
1 32 4 5 76 8
EXEMPLO
 Idéia:
 Para identifcar a posição de um 1 dentre
 2 lançamentos: 1 pergunta
 4 lançamentos: 2 perguntas
 8 lançamentos: 3 perguntas
 1024 lançamentos?
EXEMPLO
 Idéia:
 Para identifcar a posição de um 1 dentre
 2 lançamentos: 1 pergunta
 4 lançamentos: 2 perguntas
 8 lançamentos: 3 perguntas
 1024 lançamentos?
 Suponha que eu pense em um número entre 1 e 1024.
EXEMPLO
 Idéia:
 Para identifcar a posição de um 1 dentre
 2 lançamentos: 1 pergunta
 4 lançamentos: 2 perguntas
 8 lançamentos: 3 perguntas
 1024 lançamentos?
 Suponha que eu pense em um número entre 1 e 1024.
 É maior que 512?
 1 512 1024
EXEMPLO
 Idéia:
 Para identifcar a posição de um 1 dentre
 2 lançamentos: 1 pergunta
 4 lançamentos: 2 perguntas
 8 lançamentos: 3 perguntas
 1024 lançamentos?
 Suponha que eu pense em um número entre 1 e 1024.
 É maior que 512? Sim.
513 a 1024
EXEMPLO
 Idéia:
 Para identifcar a posição de um 1 dentre
 2 lançamentos: 1 pergunta
 4 lançamentos: 2 perguntas
 8 lançamentos: 3 perguntas
 1024 lançamentos?
 Suponha que eu pense em um número entre 1 e 1024.
 É maior que 512? Sim.
 É maior que 512+256? Não.
513 a 768
EXEMPLO
 Idéia:
 Para identifcar a posição de um 1 dentre
 2 lançamentos: 1 pergunta
 4 lançamentos: 2 perguntas
 8 lançamentos: 3 perguntas
 1024 lançamentos?
 Suponha que eu pense em um número entre 1 e 1024.
 É maior que 512? Sim.
 É maior que 512+256? Não.
 É maior que 512+128? Não. 513 a 640
EXEMPLO
 Idéia:
 Para identifcar a posição de um 1 dentre
 2 lançamentos: 1 pergunta
 4 lançamentos: 2 perguntas
 8 lançamentos: 3 perguntas
 1024 lançamentos?
 Suponha que eu pense em um número entre 1 e 1024.
 É maior que 512? Sim.
 É maior que 512+256? Não.
 É maior que 512+128? Não.
 É maior que 512+64? Não.
 ... Quantas perguntas são necessárias para achar o 513?
EXEMPLO
 Idéia:
 Para identifcar a posição de um 1 dentre
 2 lançamentos: 1 pergunta
 4 lançamentos: 2 perguntas
 8 lançamentos: 3 perguntas
 1024 lançamentos: log 1024 = log(2^10) = 10 perguntas
EXEMPLO
 Idéia:
 Para identifcar a posição de um 1 dentre
 2 lançamentos: 1 pergunta
 4 lançamentos: 2 perguntas
 8 lançamentos: 3 perguntas
 1024 lançamentos: log 1024 = log(2^10) = 10 perguntas
 1 milhão de lançamentos?
EXEMPLO
 Idéia:
 Para identifcar a posição de um 1 dentre
 2 lançamentos: 1 pergunta
 4 lançamentos: 2 perguntas
 8 lançamentos: 3 perguntas
 1024 lançamentos: log 1024 = log(2^10) = 10 perguntas
 1 milhão de lançamentos?
1 milhão ~ 1024 * 1024 = 2^20
EXEMPLO
 Idéia:
 Para identifcar a posição de um 1 dentre
 2 lançamentos: 1 pergunta
 4 lançamentos: 2 perguntas
 8 lançamentos: 3 perguntas
 1024 lançamentos: log 1024 = log(2^10) = 10 perguntas
 1 milhão de lançamentos?
1 milhão ~ 1024 * 1024 = 2^20
=> log(2^20) = 20 perguntas
EXEMPLO
 Idéia:
 Para identifcar a posição de um 1 dentre
 2 lançamentos: 1 bit
 4 lançamentos: 2 bits
 8 lançamentos: 3 bits
 1024 lançamentos: log 1024 = log(2^10) = 10 bits
 1 milhão de lançamentos?
1 milhão ~ 1024 * 1024 = 2^20
=> log(2^20) = 20 bits
EXEMPLO
 Idéia:
 Para identifcar a posição de um 1 
dentre 1 milhão de lançamentos:
 20 perguntas
 Para codifcar a posição de cada 1:
 20 bits
00000100............000000100000.......0001
EXEMPLO
 Idéia:
 Para identifcar a posição de um 1 
dentre 1 milhão de lançamentos:
 20 perguntas
 Para codifcar a posição de cada 1:
 20 bits
 Para codifcar a posição de 1000 1s
dentre 1 milhão de lançamentos:
 1000 * 20 = 20000 bits
00000100............000000100000.......0001
EXEMPLO
 Idéia:
 Para identifcar a posição de um 1 
dentre 1 milhão de lançamentos:
 20 perguntas
 Para codifcar a posição de cada 1:
 20 bits
 Para codifcar a posição de 1000 1s
dentre 1 milhão de lançamentos:
 1000 * 20 = 20000 bits
 Média: 20000/1milhão = 20/1000 
 = 0,02 bit por lançamento
00000100............000000100000.......0001
H
ENTROPIA DE SHANNON
 Medida da quantidade de incerteza em uma sequência 
de bits
 Quanto maior for a entropia, maior será a 
imprevisibilidade....
 Quanto mais imprevisível é a cadeia de bits, 
menor é a possibilidade de compressão,
ou seja, menor é a redundância.
ENTROPIA DE SHANNON
 Medida da incerteza em uma sequência de bits
 Quanto mais imprevisível é a cadeia de bits, 
menor é a possibilidade de compressão,
ou seja, menor é a redundância.
 Quanto menor a redundância em uma mensagem,
maior é a sua quantidade de informação
(maior incerteza).
ENTROPIA DE SHANNON
 Exemplo da moeda honesta
 Cadeia de bits totalmente imprevisível 
 Sem redundância
 Exemploda moeda viciada
 p = 1/1000 (cara)
 Redundância de 0s (coroas)
EXEMPLO
 Moeda viciada:
 1: cara 0: coroa
 p(1) = 1/1000
 Podemos transmitir esta informação usando
 20000 bits ou
 0,02 bit por lançamento
 Pergunta
 Será que conseguimos uma maneira
ainda mais econômica?
00000100............000000100000.......0001
EXEMPLO
 Idéia:
 Ao invés de codifcar a posição absoluta,
usar a posição relativa.
00010000....00000001000000.......0000100000......01000000.....0
1230 dígitos990 dígitos1121digitos 2346 dígitos
EXEMPLO
 Idéia:
 Ao invés de codifcar a posição absoluta,
usar a posição relativa.
 Em média, a distância de um 1 para outro 1 é de 
aproximadamente 1000 dígitos.
00010000....00000001000000.......0000100000......01000000.....0
1230 dígitos990 dígitos1121digitos 2346 dígitos
EXEMPLO
 Idéia:
 Ao invés de codifcar a posição absoluta,
usar a posição relativa.
 Em média, a distância de um 1 para outro 1 é de 
aproximadamente 1000 dígitos.
 Supondo que a distância máxima seja 4000,
cada posição relativa pode ser codifcada usando
 log 4000 ~ log (4*1024) = log (2^12) = 12 bits
00010000....00000001000000.......0000100000......01000000.....0
1230 dígitos990 dígitos1121digitos 2346 dígitos
EXEMPLO
 Idéia:
 Para codifcar cada posição relativa, usamos
 12 bits
 Para codifcar a posição de 1000 1s
dentre 1 milhão de lançamentos:
 1000 * 12 = 12000 bits
 Média: 12000/1milhão = 12/1000
 = 0,012 bit por lançamento
00010000....00000001000000.......0000100000......01000000.....0
1230 dígitos990 dígitos1121digitos 2346 dígitos
H
EXEMPLO
 Moeda viciada:
 1: cara 0: coroa
 p(1) = 1/1000
 Podemos transmitir esta informação usando
 Posição absoluta:
 20000 bits ou 0,02 bit por lançamento
 Posição relativa:
 12000 bits ou 0,012 bit por lançamento
00000100............000000100000.......0001
Códigos efcientes
• Existem diversas técnicas para a criação de 
códigos efcientes baseando-se nas probabilidades 
de cada símbolo
• Vamos ver duas hoje: código de Shannon-Fano e Hufman
• Ambas assumem um canal sem memória e independência 
entre símbolos
• Antes, vamos defnir o que é um código e 
propriedades relevantes
Códigos
• Dados:
• S={s1,…, sN}: conjunto de símbolos
• C = {d1, …, dD}: conjunto de caracteres de código 1 < D 
< N
• Um código é uma função injetora c : S → C*
• Se si ≠ sj então c(si) ≠ c(sj) 
• Cada c(s) é chamado de palavra de código
Códigos
• Dados:
• S={s1,…, sN}: conjunto de símbolos
• C = {d1, …, dD}: conjunto de caracteres de código 1 < D 
< N
• Queremos um código uniiamente deiodifiável 
(UD)
• Quaisquer duas sequências fnitas e diferentes de 
símbolos da fonte têm palavras de código diferentes
Códigos
• Dados:
• S={s1,…, sN}: conjunto de símbolos
• C = {d1, …, dD}: conjunto de caracteres de código 1 < D 
< N
• Queremos um código instantâneo ou livre de 
prefios (LP)
• Nenhuma palavra de código é prefxo de outra. Permite a 
decodifcação sem demora
Códigos
• Exemplos:
s
1
s
2
s
3
s
4
c
1
00 01 10 11 Tamanho fixo
c
2
10 110 1110 11110
c
3
10 110 110 1110 Não é código
c
4
0 010 01 10 Não é UD
c
5
0 01 001 000000001 Não é LP
c
6
0 100 101 11
c
7
01 011 0111 01111 UD mas não LP
Comparando códigos sobre os 
mesmos dados
• Comprimento médio
H (c)=∑
s∈S
p(s)|c (s)|
Shannon-Fano
• Shannon-Fano
• Shannon 1949
• Fano propôs o mesmo algoritmo simultaneamente
Shannon-Fano
• Algoritmo de Shannon-Fano
• (1) Ordenar os símbolos pela probabilidade de ocorrência 
(decrescente).
• (2) Particionar os símbolos em dois subconjuntos com 
probabilidades aproximadamente iguais.
• (3) Repita o passo 2 para cada subconjunto até que cada 
subconjunto tenha apenas um único símbolo.
Shannon-Fano
• Algoritmo de Shannon-Fano
• Ex.
• Considere um conjunto com 4 símbolos com as seguintes 
probabilidades.
Símbolos s1 s2 s3 S4
Probabilidades 1/2 1/4 1/8 1/8
Shannon-Fano
• Algoritmo de Shannon-Fano
• Ex.
• Considere um conjunto com 4 símbolos com as seguintes 
probabilidades.
Símbolos s1 s2 s3 S4
Probabilidades 1/2 1/4 1/8 1/8
(1) Ordenar os símbolos pela probabilidade de ocorrência. 
Shannon-Fano
• Algoritmo de Shannon-Fano
• Ex.
• Considere um conjunto com 4 símbolos com as seguintes 
probabilidades.
Símbolos s1 s2 s3 S4
Probabilidades 1/2 1/4 1/8 1/8
(1) Ordenar os símbolos pela probabilidade de ocorrência.
(2) Particionar os símbolos em dois subconjuntos com 
probabilidades aproximadamente iguais.
Shannon-Fano
• Algoritmo de Shannon-Fano
• Ex.
• Considere um conjunto com 4 símbolos com as seguintes 
probabilidades.
Símbolos s1 s2 s3 S4
Probabilidades 1/2 1/4 1/8 1/8
(1) Ordenar os símbolos pela probabilidade de ocorrência.
(2) Particionar os símbolos em dois subconjuntos com 
probabilidades aproximadamente iguais.
Shannon-Fano
• Algoritmo de Shannon-Fano
• Ex.
• Considere um conjunto com 4 símbolos com as seguintes 
probabilidades.
Símbolos s1 s2 s3 S4
Probabilidades 1/2 1/4 1/8 1/8
(1) Ordenar os símbolos pela probabilidade de ocorrência.
(2) Particionar os símbolos em dois subconjuntos com 
probabilidades aproximadamente iguais.
(3) Repita o passo 2 para cada subconjunto até que cada 
subconjunto tenha apenas um único símbolo.
Shannon-Fano
• Algoritmo de Shannon-Fano
• Ex.
• Considere um conjunto com 4 símbolos com as seguintes 
probabilidades.
Símbolos s1 s2 s3 S4
Probabilidades 1/2 1/4 1/8 1/8
(1) Ordenar os símbolos pela probabilidade de ocorrência.
(2) Particionar os símbolos em dois subconjuntos com 
probabilidades aproximadamente iguais.
(3) Repita o passo 2 para cada subconjunto até que cada 
subconjunto tenha apenas um único símbolo.
Shannon-Fano
• Algoritmo de Shannon-Fano
• Ex.
• Considere um conjunto com 4 símbolos com as seguintes 
probabilidades.
Símbolos s1 s2 s3 S4
Probabilidades 1/2 1/4 1/8 1/8
 .
Construir Construir 
“árvore binária““árvore binária“
de 0s e 1s.de 0s e 1s.
Shannon-Fano
• Algoritmo de Shannon-Fano
• Ex.
• Considere um conjunto com 4 símbolos com as seguintes 
probabilidades.
Símbolos s1 s2 s3 S4
Probabilidades 1/2 1/4 1/8 1/8
 .
 / \
 s1 0 1 (s2, s3, s4) Construir Construir 
“árvore “árvore 
binária“binária“
de 0s e 1s.de 0s e 1s.
Shannon-Fano
• Algoritmo de Shannon-Fano
• Ex.
• Considere um conjunto com 4 símbolos com as seguintes 
probabilidades.
Símbolos s1 s2 s3 S4
Probabilidades 1/2 1/4 1/8 1/8
 .
 / \
 s1 0 1 (s2, s3, s4) Construir Construir 
“árvore “árvore 
binária“binária“
de 0s e 1s.de 0s e 1s.
Shannon-Fano
• Algoritmo de Shannon-Fano
• Ex.
• Considere um conjunto com 4 símbolos com as seguintes 
probabilidades.
Símbolos s1 s2 s3 S4
Probabilidades 1/2 1/4 1/8 1/8
 .
 / \
 s1 0 1 (s2, s3, s4)
 / \
 s2 0 1 (s3, s4)
Construir Construir 
“árvore “árvore 
binária“binária“
de 0s e 1s.de 0s e 1s.
Shannon-Fano
• Algoritmo de Shannon-Fano
• Ex.
• Considere um conjunto com 4 símbolos com as seguintes 
probabilidades.
Símbolos s1 s2 s3 S4
Probabilidades 1/2 1/4 1/8 1/8
 .
 / \
 s1 0 1 (s2, s3, s4)
 / \
 s2 0 1 (s3, s4)
Construir Construir 
“árvore “árvore 
binária“binária“
de 0s e 1s.de 0s e 1s.
Shannon-Fano
• Algoritmo de Shannon-Fano
• Ex.
• Considere um conjunto com 4 símbolos com as seguintes 
probabilidades.
Símbolos s1 s2 s3 S4
Probabilidades 1/2 1/4 1/8 1/8
 .
 / \
 s1 0 1 (s2, s3, s4)
 / \
 s2 0 1 (s3, s4)
 / \
 s3 0 1 s4
Construir Construir 
“árvore “árvore 
binária“binária“
de 0s e 1s.de 0s e 1s.
Shannon-Fano
• Algoritmo de Shannon-Fano
• Ex.
• Considere um conjunto com 4 símbolos com as seguintes 
probabilidades.
Símbolos s1 s2 s3 S4
Probabilidades 1/2 1/4 1/8 1/8
 .
 / \
 s1 0 1 (s2, s3, s4)
 / \
 s2 0 1 (s3, s4)
 / \
 s3 0 1 s4
s1: 0
Shannon-Fano
• Algoritmo de Shannon-Fano
• Ex.
• Considereum conjunto com 4 símbolos com as seguintes 
probabilidades.
Símbolos s1 s2 s3 S4
Probabilidades 1/2 1/4 1/8 1/8
 .
 / \
 s1 0 1 (s2, s3, s4)
 / \
 s2 0 1 (s3, s4)
 / \
 s3 0 1 s4
s1: 0
s2: 10
Shannon-Fano
• Algoritmo de Shannon-Fano
• Ex.
• Considere um conjunto com 4 símbolos com as seguintes 
probabilidades.
Símbolos s1 s2 s3 S4
Probabilidades 1/2 1/4 1/8 1/8
 .
 / \
 s1 0 1 (s2, s3, s4)
 / \
 s2 0 1 (s3, s4)
 / \
 s3 0 1 s4
s1: 0
s2: 10
s3: 110
Shannon-Fano
• Algoritmo de Shannon-Fano
• Ex.
• Considere um conjunto com 4 símbolos com as seguintes 
probabilidades.
Símbolos s1 s2 s3 S4
Probabilidades 1/2 1/4 1/8 1/8
 .
 / \
 s1 0 1 (s2, s3, s4)
 / \
 s2 0 1 (s3, s4)
 / \
 s3 0 1 s4
s1: 0
s2: 10
s3: 110
s4: 111
Exercício
Considere a seguinte mensagem:
• A VACA FOI PRO BREJO
• Os símbolos: A, B, C, E, F, I, J, O, P, R, V (vamos 
desconsiderar o espaço).
• (a) Calcular as frequências (número de ocorrências) para 
cada símbolo.
• (b) Calcular os códigos de tamanho variável para cada 
letra, usando o algoritmo de Shannon-Fano.
A VACA FOI PRO BREJO
(a) Frequência dos símbolos:
Ordenados:
A B C E F I J O P R V
3 1 1 1 1 1 1 3 1 2 1
A O R B C E F I J P V
3 3 2 1 1 1 1 1 1 1 1
A VACA FOI PRO BREJO
(b) Árvore Shannon-Fano
A O R B C E F I J P V
3 3 2 1 1 1 1 1 1 1 1
A O R B C E F I J P V
0 1
A VACA FOI PRO BREJO
(b) Árvore Shannon-Fano
A O R B C E F I J P V
3 3 2 1 1 1 1 1 1 1 1
A O R B C E F I J P V
0 1
A VACA FOI PRO BREJO
(b) Árvore Shannon-Fano
A O R B C E F I J P V
3 3 2 1 1 1 1 1 1 1 1
0
1
A O R B C E F I J P V
0 1 0 1
A VACA FOI PRO BREJO
(b) Árvore Shannon-Fano
0
1
A
0 1 0 1
O R B C E F I J P V
0 0 0 111
A VACA FOI PRO BREJO
(b) Árvore Shannon-Fano
0
1
A
0 1 0 1
O R
C F I P
0 0 0 111
B
0 1
E
0 1
J V
0 1 0 1
A VACA FOI PRO BREJO
0
1
A
0 1 0 1
O R
C F I P
0 0 0 111
B
0 1
E
0 1
J V
0 1 0 1
A B C E F I J O P R V
00 1000 1001 1010 1011 1100 1101 010 1110 011 1111
A VACA FOI PRO BREJO
00 1111 00 1001 00 1011 010 1100 1110 011 010 
1000 011 1010 1101 010
= 53 bits
Sem compressão, 4 bits por letra = 64 bits
A B C E F I J O P R V
00 1000 1001 1010 1011 1100 1101 010 1110 011 1111
Código de Hufman
• Código de Hufman
• David Albert Hufman (1925-1999)
• Desenvolvido durante seu doutorado no MIT e publicado no 
artigo de 1952:
• "A Method for the Construction of Minimum-Redundancy Codes".
Código de Hufman
• Algoritmo de Hufman
• (1) Ordenar os símbolos pela probabilidade de ocorrência 
(crescente).
• (2) Mesclar os dois símbolos com menores probabilidades 
em uma subárvore, somando as probabilidades.
• (3) Reordene a lista e repita o passo (2) até existir apenas 
uma árvore.
Código de Hufman
Considere um conjunto com 4 símbolos com as 
seguintes probabilidades.
(1) ordene em ordem crescente
Símbolos s1 s2 s3 S4
Probabilidades 1/2 1/4 1/8 1/8
Código de Hufman
Considere um conjunto com 4 símbolos com as 
seguintes probabilidades.
(2) mescle as duas probabilidades menores e some 
os valores
Símbolos s4 s3 s2 s1
Probabilidades 1/8 1/8 1/4 1/2
s4 s3
1/4
0 1
Código de Hufman
Considere um conjunto com 4 símbolos com as 
seguintes probabilidades.
(3) reordene em ordem crescente
Símbolos s4 e s3 s2 s1
Probabilidades 1/4 1/4 1/2
Código de Hufman
Considere um conjunto com 4 símbolos com as 
seguintes probabilidades.
(2) mescle as duas probabilidades menores e some 
os valores
Símbolos s4 e s3 s2 s1
Probabilidades 1/4 1/4 1/2
s4 s3
1/
4
s2
1/2
Código de Hufman
Considere um conjunto com 4 símbolos com as 
seguintes probabilidades.
(3) reordene em ordem crescente
Símbolos (s4 e s3) 
e s2
s1
Probabilidades 1/2 1/2
Código de Hufman
Considere um conjunto com 4 símbolos com as 
seguintes probabilidades.
(2) mescle as duas probabilidades menores e some 
os valores
Símbolos (s4 e s3) 
e s2
s1
Probabilidades 1/2 1/2
s4 s3
1/
4
s2
1/2
s1
1
0 1
0
1
0
1
Código de Hufman
Códigos por símbolo:
s4 s3
1/
4
s2
1/2
s1
1
0 1
0
1
0
1
Símbolos s1 s2 s3 S4
Código 1 01 001 000
Exercício
Considere a seguinte mensagem:
• A VACA FOI PRO BREJO
• Os símbolos: A, B, C, E, F, I, J, O, P, R, V (vamos 
desconsiderar o espaço).
• (a) Calcular as frequências (número de ocorrências) para 
cada símbolo.
• (b) Calcular os códigos de tamanho variável para cada 
letra, usando o algoritmo de Hufman.
A VACA FOI PRO BREJO
(a) Frequência dos símbolos:
Ordenados:
A B C E F I J O P R V
3 1 1 1 1 1 1 3 1 2 1
B C E F I J P V R A O
1 1 1 1 1 1 1 1 2 3 3
A VACA FOI PRO BREJO
(b) Mesclagem
B
0 1
B C E F I J P V R A O
1 1 1 1 1 1 1 1 2 3 3
C
A VACA FOI PRO BREJO
(c) Reordenar
B
0 1
E F I J P V (BC) R A O
1 1 1 1 1 1 2 2 3 3
C
A VACA FOI PRO BREJO
(b) Mesclagem
B
0 1
E F I J P V (BC) R A O
1 1 1 1 1 1 2 2 3 3
C E
0 1
F
A VACA FOI PRO BREJO
(c) Reordenando
B
0 1
I J P V (BC) (EF) R A O
1 1 1 1 2 2 2 3 3
C E
0 1
F
A VACA FOI PRO BREJO
(b) Mesclagem
B
0 1
I J P V (BC) (EF) R A O
1 1 1 1 2 2 2 3 3
C E
0 1
F I
0 1
J
A VACA FOI PRO BREJO
(c) Reordenando
B
0 1
P V (BC) (EF) (IJ) R A O
1 1 2 2 2 2 3 3
C E
0 1
F I
0 1
J
A VACA FOI PRO BREJO
(b) Mesclagem
B
0 1
P V (BC) (EF) (IJ) R A O
1 1 2 2 2 2 3 3
C E
0 1
F I
0 1
J P
0 1
V
A VACA FOI PRO BREJO
(c) Reordenando
B
0 1
(BC) (EF) (IJ) (PV) R A O
2 2 2 2 2 3 3
C E
0 1
F I
0 1
J P
0 1
V
A VACA FOI PRO BREJO
(b) Mesclagem
B
0 1
(BC) (EF) (IJ) (PV) R A O
2 2 2 2 2 3 3
C E
0 1
F I
0 1
J P
0 1
V
0 1
A VACA FOI PRO BREJO
(c) Reordenando
B
0 1
(IJ) (PV) R A O ((BC)(EF))
2 2 2 3 3 4
C E
0 1
F I
0 1
J P
0 1
V
0 1
A VACA FOI PRO BREJO
(b) Mesclagem
B
0 1
(IJ) (PV) R A O ((BC)(EF))
2 2 2 3 3 4
C E
0 1
F I
0 1
J P
0 1
V
0 1 0 1
A VACA FOI PRO BREJO
(c) Reordenando
B
0 1
R A O ((BC)(EF)) ((IJ)(PV))
2 3 3 4 4
C E
0 1
F I
0 1
J P
0 1
V
0 1 0 1
A VACA FOI PRO BREJO
(b) Mesclagem
B
0 1
R A O ((BC)(EF)) ((IJ)(PV))
2 3 3 4 4
C E
0 1
F I
0 1
J P
0 1
V
0 1 0 1
R
0 1
A
A VACA FOI PRO BREJO
(c) Reordenando
B
0 1
O ((BC)(EF)) ((IJ)(PV)) (RA)
3 4 4 5
C E
0 1
F I
0 1
J P
0 1
V
0 1 0 1
R
0 1
A
A VACA FOI PRO BREJO
(b) Mesclando
B
0 1
O ((BC)(EF)) ((IJ)(PV)) (RA)
3 4 4 5
C E
0 1
F I
0 1
J P
0 1
V
0 1 0 1
R
0 1
A
O
0 1
A VACA FOI PRO BREJO
(c) Reordenando
B
0 1
((IJ)(PV)) (RA) (((BC)(EF))
O)
4 5 7
C E
0 1
F I
0 1
J P
0 1
V
0 1 0 1
R
0 1
A
O
0 1
A VACA FOI PRO BREJO
(b) Mesclando
B
0 1
((IJ)(PV)) (RA) (((BC)(EF))
O)
4 5 7
C E
0 1
F
I
0 1
J P
0 1
V0 1
0 1
R
0 1
A
O
0 1
0 1
A VACA FOI PRO BREJO
(c) Reordenando
B
0 1
(((BC)(EF))O) (((IJ)(PV))(RA))
7 9
C E
0 1
F
I
0 1
J P
0 1
V0 1
0 1
R
0 1
A
O
0 1
0 1
A VACA FOI PRO BREJO
Mesclagem Final!
B
0 1
C E
0 1
F
I
0 1
J P
0 1
V
0 1
0 1
R
0 1
A
O
0 1
0 1
0
1
A VACA FOI PRO BREJO
B
0 1
C E
0 1
F
I
0 1
J P
0 1
V
0 1
0 1
R
0 1
A
O
0 1
0 1
0
1
A B C E F I J O P R V
111 0100 0101 0110 0111 1000 1001 00 1010 110 1011
A VACA FOI PRO BREJO
111 1011 111 0101 111 0111 00 1000 1010 110 00 
0100 110 0110 1001 00
= 53 bits
Sem compressão, 4 bits por letra = 64 bits
A B C E F I J O P R V
111 0100 0101 0110 0111 1000 1001 00 1010 110 1011
Conclusão
Hufman = 53 bits
Shannon-Fano = 53 bits
● Código de Shannon-Fano é sub-ótimo enquanto 
que Hufman é ótimo
● Estamos assumindo canal sem memória e independência 
entre símbolos
● Em textos, por exemplo, isso não é verdade
● Nestes casos existem outras alternativas
Exercício
● Usando os códigos de Shannon-Fano e de Hufman 
codifque o seguinte conjunto de símbolos:
● S = {a,b,c,d,e,f,g,h}
● Probabilidades (na ordem dos símbolos): {0.15, 0.14, 0.3, 
0.1, 0.12, 0.08, 0.06, 0.05}
● Uma palavra da fontefoi codifcada usando um 
desses códigos. O código obtido foi 
111100001011010110010. Que código foi usado e 
qual foi a palavra original?
Exercício – Solução Shannon
Exercício – Solução Hufman
Bibliografa
• T. L. Floyd. Digital Fundamentals. 9th Edition. Pearson 
Prentice Hall. 2006.
• E. Chiu, J. Lin, B. Mcferron, N. Petigara, S. Seshasai. 
Mathematiial Theory of Claude Shannon: A study 
of the style and ionteit of his work up to the 
genesis of information theory. 
http://mit.edu/6.933/www/Fall2001/Shannon1.pdf 
• Monica Borda. Fundamentals in Information Theory 
and Coding. Springer. 2011.
• T. H. Comen, C. E. Leiserson, R. L. Rivest, C. Stein. 
Introduition to Algorithms. The MIT Press. 3rd Edition. 
2009.
Bibliografa
• Monica Borda. Fundamentals in Information Theory 
and Coding. Springer. 2011.
• T. H. Comen, C. E. Leiserson, R. L. Rivest, C. Stein. 
Introduition to Algorithms. The MIT Press. 3rd Edition. 
2009.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65
	Slide 66
	Slide 67
	Slide 68
	Slide 69
	Slide 70
	Slide 71
	Slide 72
	Slide 73
	Slide 74
	Slide 75
	Slide 76
	Slide 77
	Slide 78
	Slide 79
	Slide 80
	Slide 81
	Slide 82
	Slide 83
	Slide 84
	Slide 85
	Slide 86
	Slide 87
	Slide 88
	Slide 89
	Slide 90
	Slide 91
	Slide 92
	Slide 93
	Slide 94
	Slide 95
	Slide 96
	Slide 97
	Slide 98
	Slide 99
	Slide 100
	Slide 101
	Slide 102
	Slide 103
	Slide 104
	Slide 105
	Slide 106
	Slide 107
	Slide 108
	Slide 109
	Slide 110
	Slide 111
	Slide 112
	Slide 113
	Slide 114