aula08_compressao_p2-expanded

Prévia do material em texto

Natureza da 
Informação
Prof. Thiago F. Covões
baseado no material do Prof. David Correa 
Códigos Eficientes II
 
Compressão
 Objetivo: converter cadeia de bits 
representando símbolos sucessivos em uma 
cadeia menor para economia em:
 Transmissão
 Armazenamento
 Processamento
 
Compressão
 Objetivo: converter cadeia de bits 
representando símbolos sucessivos em uma 
cadeia menor para economia em:
 Transmissão
 Armazenamento
 Processamento
 Diminui mensagens, mas aumenta 
processamento necessário 
 
Tipos de compressão
 Sem perda ou reversível
 Símbolo original/codificado pode ser reconstruído 
exatamente a partir da versão comprimida
 
Tipos de compressão
 Sem perda ou reversível
 Símbolo original/codificado pode ser reconstruído 
exatamente a partir da versão comprimida
 Usualmente explora redundâncias
 Ex. tem padrões de bits não usados ou tem alguns símbolos 
mais usados que outros
 
Tipos de compressão
 Sem perda ou reversível
 Símbolo original/codificado pode ser reconstruído 
exatamente a partir da versão comprimida
 Usualmente explora redundâncias
 Ex. tem padrões de bits não usados ou tem alguns símbolos 
mais usados que outros
 Com perda ou irreversível
 Símbolo original/codificado não pode ser reconstruído 
exatamente a partir da versão comprimida
 Expansor produz aproximação
 
Tipos de compressão
 Exemplo: mensagem 25.888888888
 Pode ser comprimida sem perda como: 25.[9]8
 “vinte e cinco ponto 9 oitos“
 Cadeia original pode ser perfeitamente recriada
 
Tipos de compressão
 Exemplo: mensagem 25.888888888
 Pode ser comprimida sem perda como: 25.[9]8
 “vinte e cinco ponto 9 oitos“
 Cadeia original pode ser perfeitamente recriada
 Ou comprimida com perda como: 26
 O dado exato é perdido, porém há o benefício de uma 
codificação menor
 
Técnicas de compressão 
sem perda
 Permitem reconstrução exata da mensagem:
 Codificação run-length
 Codificação de tamanho variável
 Dicionário estático
 Dicionário semi-adaptativo
 Dicionário dinâmico
 
Codificação run-length
 Suponha mensagem com sequências longas 
de repetições de símbolos
 
Codificação run-length
 Suponha mensagem com sequências longas 
de repetições de símbolos
 Pode codificar mensagem como lista do símbolo 
e número de vezes que ele ocorre
 Ex.: mensagem “a B B B B B B a a a B B a a a a” 
poderia ser codificada como “a[1] B[6] a[3] B[2] a[4]”
 
Codificação run-length
 Suponha mensagem com sequências longas 
de repetições de símbolos
 Pode codificar mensagem como lista do símbolo 
e número de vezes que ele ocorre
 Ex.: mensagem “a B B B B B B a a a B B a a a a” 
poderia ser codificada como “a[1] B[6] a[3] B[2] a[4]”
 Funciona bem em poucas circunstâncias
 
Codificação run-length
 Exemplos:
 Bandeira da Alemanha
 X pixels pretos, X pixels vermelhos, X pixels amarelos
 
Codificação run-length
 Exemplos:
 Bandeira da Alemanha
 X pixels pretos, X pixels vermelhos, X pixels amarelos
 Fax
 Documento é escaneado em preto e branco
 Longos grupos de pixels brancos ou pretos são transmitidos 
como o número desses pixels
 
Codificação run-length
 Não funciona bem para mensagens sem 
repetições de sequências de um mesmo 
símbolo
 
Codificação run-length
 Não funciona bem para mensagens sem 
repetições de sequências de um mesmo 
símbolo
 Ex.: fotografias, em que pequenas mudanças em 
sombreamento de um pixel a outro requer o uso 
de vários símbolos 
 
Codificação de tamanho 
variável
 Atribuição de códigos menores a símbolos 
mais frequentes
 
Codificação de tamanho 
variável
 Atribuição de códigos menores a símbolos 
mais frequentes
 E códigos maiores para símbolos menos 
frequentes
 
Codificação de tamanho 
variável
 Atribuição de códigos menores a símbolos 
mais frequentes
 E códigos maiores para símbolos menos 
frequentes
 Codificações de Shannon-Fano e Huffman 
(vide última aula)
 
Codificação de tamanho 
variável
 Shannon-Fano e Huffman assumem que a 
distribuição de probabilidades dos símbolos não 
muda ao longo da sequência de emissões
 
Codificação de tamanho 
variável
 Shannon-Fano e Huffman assumem que a 
distribuição de probabilidades dos símbolos não 
muda ao longo da sequência de emissões
 Huffman é ótimo nessa situação
 
Codificação de tamanho 
variável
 Shannon-Fano e Huffman assumem que a 
distribuição de probabilidades dos símbolos não 
muda ao longo da sequência de emissões
 Huffman é ótimo nessa situação
 Porém, em muitas situações, a distribuição de 
probabilidades dos símbolos pode depender de 
uma história de emissões
 
Codificação de tamanho 
variável
 Shannon-Fano e Huffman assumem que a 
distribuição de probabilidades dos símbolos não 
muda ao longo da sequência de emissões
 Huffman é ótimo nessa situação
 Porém, em muitas situações, a distribuição de 
probabilidades dos símbolos pode depender de 
uma história de emissões
 Textos em geral
 
Codificação de tamanho 
variável
 Shannon-Fano e Huffman assumem que a 
distribuição de probabilidades dos símbolos não 
muda ao longo da sequência de emissões
 Huffman é ótimo nessa situação
 Porém, em muitas situações, a distribuição de 
probabilidades dos símbolos pode depender de 
uma história de emissões
 Textos em geral
 Exemplo: a distribuição de probabilidades torna-se mais 
concentrada do que o normal nas vogais “a”, “e”, “i”, “o”, após 
a emissão das letras “q” e “u” considerando a língua 
portuguesa (a probabilidade de ser uma consoante é zero 
após “qu”)
 
Dicionário estático
 Apropriado para mensagens de texto
 
Dicionário estático
 Apropriado para mensagens de texto
 Se um código tem padrões não usados, eles 
podem ser atribuídos a sequências que 
ocorrem frequentemente
 
Dicionário estático
 Apropriado para mensagens de texto
 Se um código tem padrões não usados, eles 
podem ser atribuídos a sequências que 
ocorrem frequentemente
 Por exemplo: abreviações
 
Dicionário estático
 Apropriado para mensagens de texto
 Se um código tem padrões não usados, eles 
podem ser atribuídos a sequências que 
ocorrem frequentemente
 Por exemplo: abreviações
 E essas sequências passam a requerer menos 
bits do que a transmissão símbolo a símbolo
 
Dicionário estático
 Apropriado para mensagens de texto
 Se um código tem padrões não usados, eles 
podem ser atribuídos a sequências que 
ocorrem frequentemente
 Por exemplo: abreviações
 E essas sequências passam a requerer menos 
bits do que a transmissão símbolo a símbolo
 Ex.: DEL em ASCII pode ser desnecessário
  atribuir código 127 à palavra “the”
 
Dicionário estático
 Apropriado para mensagens de texto
 Se um código tem padrões não usados, eles 
podem ser atribuídos a sequências que 
ocorrem frequentemente
 Por exemplo: abreviações
 E essas sequências passam a requerer menos 
bits do que a transmissão símbolo a símbolo
 Ex.: DEL em ASCII pode ser desnecessário
  atribuir código 127 à palavra “the”
 Lista de códigos e seus significados é chamada 
livro de códigos ou dicionário
 
Dicionário estático
 Uso de abreviações para comprimir 
mensagens implica necessidade de 
dicionário
 
Dicionário estático
 Uso de abreviações para comprimir 
mensagens implica necessidade de 
dicionário
 E de transmití-lo antes da primeira mensagem
 Deve ser cuidadosamente construído e não pode ser 
alterado com frequência
 
Dicionário estático
 Uso de abreviações para comprimir 
mensagens implica necessidade de 
dicionário
 E de transmití-lo antes da primeira mensagem
 Deve ser cuidadosamente construído e não pode ser 
alterado com frequência
 Bom para conjuntos de mensagens similares
 
Dicionário estático
 Uso de abreviações para comprimir 
mensagens implica necessidade de 
dicionário
 E de transmití-lo antes da primeira mensagem
 Deve ser cuidadosamente construído e não pode ser 
alterado com frequência
 Bompara conjuntos de mensagens similares
 Não adequado para mensagens diversas
 
Dicionário semi-
adaptativo
 Se um novo dicionário pudesse ser definido para 
cada mensagem, a compressão seria maior
 Sequências de símbolos da mensagem em particular 
poderiam ser entradas do dicionário
 
Dicionário semi-
adaptativo
 Se um novo dicionário pudesse ser definido para 
cada mensagem, a compressão seria maior
 Sequências de símbolos da mensagem em particular 
poderiam ser entradas do dicionário
 Problemas:
 Novo dicionário teria que ser transmitido junto à mensagem 
 
Dicionário semi-
adaptativo
 Se um novo dicionário pudesse ser definido para 
cada mensagem, a compressão seria maior
 Sequências de símbolos da mensagem em particular 
poderiam ser entradas do dicionário
 Problemas:
 Novo dicionário teria que ser transmitido junto à mensagem 
 Mensagem deve ser analisada antes para descobrir as 
melhores entradas para o dicionário
 Deve ser conhecida antes e armazenada como um todo antes
 
Dicionário semi-
adaptativo
 Se um novo dicionário pudesse ser definido para 
cada mensagem, a compressão seria maior
 Sequências de símbolos da mensagem em particular 
poderiam ser entradas do dicionário
 Problemas:
 Novo dicionário teria que ser transmitido junto à mensagem 
 Mensagem deve ser analisada antes para descobrir as 
melhores entradas para o dicionário
 Deve ser conhecida antes e armazenada como um todo antes
Uso limitado
 
Dicionário dinâmico
 Calculado à medida que a mensagem é 
processada
 
Dicionário dinâmico
 Calculado à medida que a mensagem é 
processada
 Não precisa acompanhar a mensagem
 
Dicionário dinâmico
 Calculado à medida que a mensagem é 
processada
 Não precisa acompanhar a mensagem
 Pode ser usado antes do fim da mensagem 
ser processada
 
Dicionário dinâmico
 Ex. técnica de compressão LZW
 Abraham Lempel, Jacob Ziv, Terry Welch
 Lempel e Ziv: várias técnicas de compressão, LZ77 e 
LZ78
 Modificações de Welch em 1984
 
Dicionário dinâmico
 Welch queria reduzir número de bits enviados à 
cabeça de gravação em discos
 Aumentar capacidade dos discos
 Melhorar velocidade de transmissão de dados
 
Dicionário dinâmico
 Welch queria reduzir número de bits enviados à 
cabeça de gravação em discos
 Aumentar capacidade dos discos
 Melhorar velocidade de transmissão de dados
 Aplicado a arquivos de: 
 Textos: reduz tipicamente a metade do tamanho
 Imagens, com grandes áreas com mesma cor: pode 
reduzir a menos da metade
 GIF usa compressão LZW
 Em fotos com mudanças graduais de cor, compressão é 
muito mais modesta
 
Dicionário dinâmico
 Welch queria reduzir número de bits enviados à 
cabeça de gravação em discos
 Aumentar capacidade dos discos
 Melhorar velocidade de transmissão de dados
 Aplicado a arquivos de: 
 Textos: reduz tipicamente a metade do tamanho
 Imagens, com grandes áreas com mesma cor: pode 
reduzir a menos da metade
 GIF usa compressão LZW
 Em fotos com mudanças graduais de cor, compressão é 
muito mais modesta
Problema: patente até 2004
 
Compressão LZW
 Reversível: não perde informação, decodificador reconstrói 
mensagem original exatamente
 
Compressão LZW
 Reversível: não perde informação, decodificador reconstrói 
mensagem original exatamente
 Dicionário inicial: 8 bits (0 a 255)
 ASCII nos primeiros caracteres
 
Compressão LZW
 Reversível: não perde informação, decodificador reconstrói 
mensagem original exatamente
 Dicionário inicial: 8 bits (0 a 255)
 ASCII nos primeiros caracteres
 Entrada 256: começo da transmissão (limpar dicionário)
 Entrada 257: fim de transmissão ou parada
 
Compressão LZW
 Reversível: não perde informação, decodificador reconstrói 
mensagem original exatamente
 Dicionário inicial: 8 bits (0 a 255)
 ASCII nos primeiros caracteres
 Entrada 256: começo da transmissão (limpar dicionário)
 Entrada 257: fim de transmissão ou parada
 Mensagem codificada = sequência de números
 Códigos representando as entradas no dicionário
 
Compressão LZW
 Dicionário inicialmente contém caracteres 
isolados, mas novas entradas com dois ou 
mais caracteres vão sendo definidas a 
medida que a mensagem é analisada
 
Compressão LZW
 Codificação:
 nova_entrada = novas entradas do dicionário = 
 Manda código de início (256)
 Adiciona a nova_entrada os caracteres, um a um, da 
mensagem sendo comprimida
 Assim que nova_entrada se torna diferente de qualquer outra 
cadeia já no dicionário, coloca-a no dicionário e manda 
código da cadeia sem o último caractere
 Quando mensagem termina, manda código de 
nova_entrada e código de parada (257)
 
Compressão LZW
 Decodificação:
 Se recebe código de início (256), limpa dicionário novo e seta 
nova_entrada' = 
 Para o código seguinte recebido, produz como saída o caractere 
representado pelo código e coloca-o em nova_entrada’
 Para códigos subsequentes recebidos
 Se conhece o código:
 Adiciona o primeiro caractere da cadeia representada pelo código a 
nova_entrada', insere resultado no dicionário e produz como saída a 
cadeia do código recebido
 Coloca em nova_entrada' a cadeia anterior, para começar nova 
entrada do dicionário
 Senão:
 Repete em nova_entrada' primeiro caractere do código recebido 
anteriormente, insere resultado no dicionário e produz como saída a 
cadeia do código recebido
 Quando o código de parada (257) é recebido, nada precisa ser feito
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
Entrada: caracte-
res com 8 bits
(código ASCII)
Transmissão: ca-
racteres com 9 bits
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
1) Nova_entrada = 
2) Manda 
código de início
3) Recebendo 
código de início, 
limpa dicionário e faz 
nova_entrada’ =  
4) Nova_entrada = i
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
1) Nova_entrada = i t
(não tem no dicionário) 
 2) Insere no dicionário
3) Manda 
código de 
nova_entrada, 
sem o caractere 
final  i
5) Produz como saída 
o caractere do código 
recebido  i
6) Nova_entrada’ = i
4) nova_entrada=t
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
1) Nova_entrada = t
(tem no dicionário)
2) Nova_entrada = t t
(não tem) 
 3) Insere no dicionário
4) Manda 
código de 
nova_entrada, 
sem o caractere 
final  t
6) Nova_entrada’ = i t
7) Insere 
nova_entrada’ no 
dicionário
8) Produz saída = 
cadeia do código 
recebido  t
5) nova_entrada=t
9) nova_entrada’=t
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
1) Nova_entrada= t
(tem no dicionário)
2) Nova_entrada = t y
(não tem) 
 3) Insere no dicionário
4) Manda 
código de 
nova_entrada, 
sem o caractere 
final  t
5) nova_entrada=y
6) Nova_entrada’ = t t
7) Insere 
nova_entrada’ no 
dicionário
8) Produz saída = 
cadeia do código 
recebido  t
9) nova_entrada’=t
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
1) Nova_entrada = y
(tem no dicionário)
2) Nova_entrada = 
y space (não tem) 
 3) Insere no dicionário
4) Manda 
código de 
nova_entrada, 
sem o caractere 
final  y
5) nova_entrada=space
6) Nova_entrada’ = t y
7) Insere 
nova_entrada’ no 
dicionário
8) Produz saída = 
cadeia do código 
recebido  y
9) nova_entrada’=y
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
1) Nova_entrada = space
(tem no dicionário)
2) Nova_entrada = 
space b (não tem) 
 3) Insere no dicionário
4) Manda 
código de 
nova_entrada, 
sem o caractere 
final  space
5) nova_entrada=b
6) Nova_entrada’ = y 
space
7) Insere 
nova_entrada’ no 
dicionário
8) Produz saída = 
cadeia do código 
recebido  space
9) nova_entrada’=space
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
1) Nova_entrada = b
(tem no dicionário)
2) Nova_entrada = 
b i (não tem) 
 3) Insere no dicionário
4) Manda 
código de 
nova_entrada, 
sem o caractere 
final  b
5) nova_entrada=i
6) Nova_entrada’ = 
space b
7) Insere 
nova_entrada’ no 
dicionário
8) Produz saída = 
cadeia do código 
recebido  b
9) nova_entrada’=b
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
1) Nova_entrada = i
(tem no dicionário)
2) Nova_entrada = 
i t (tem)
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
1) Nova_entrada = i t
(tem no dicionário)
2) Nova_entrada = 
i t t (não tem) 
 3) Insere no dicionário
4) Manda 
código de 
nova_entrada, 
sem o caractere 
final  i t
5) nova_entrada=t
6) Nova_entrada’ = b i
7) Insere nova_entrada’ 
no dicionário
8) Produz saída = cadeia 
do código recebido  i t
9) nova_entrada’=i t
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
1) Nova_entrada = t
(tem no dicionário)
2) Nova_entrada = 
t y (tem) 
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
1) Nova_entrada = t y
(tem no dicionário)
2) Nova_entrada = 
t y space (não tem)
 3) Insere no dicionário 
4) Manda 
código de 
nova_entrada, 
sem o caractere 
final  t y
5) nova_entrada=space
6) Nova_entrada’ = i t t
7) Insere nova_entrada’ 
no dicionário
8) Produz saída = cadeia 
do código recebido  t y
9) nova_entrada’=t y
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
1) Nova_entrada = space
(tem no dicionário)
2) Nova_entrada = 
space b (tem) 
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
1) Nova_entrada = space 
b (tem no dicionário)
2) Nova_entrada = 
space b i (não tem)
 3) Insere no dicionário 
4) Manda 
código de 
nova_entrada, 
sem o caractere 
final  space b
5) nova_entrada=i
6) Nova_entrada’ = t y spa
7) Insere nova_entrada’ 
no dicionário
8) Saída = cadeia do 
código recebido  spa b
9) nova_entrada’=spa b
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
• Nova_entrada = i 
(tem no dicionário)
2) Nova_entrada = 
i t (tem)
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
• Nova_entrada = i t
(tem no dicionário)
2) Nova_entrada = 
i t space (não tem)
 3) Insere no dicionário
4) Manda 
código de 
nova_entrada, 
sem o caractere 
final  i t
5) nova_entrada=space
6) Nova_entrada’ = spa b i
7) Insere nova_entrada’ 
no dicionário
8) Saída = cadeia do 
código recebido  i t
9) nova_entrada’=i t
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
• Nova_entrada = space
(tem no dicionário)
2) Nova_entrada = 
space b (tem)
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
• Nova_entrada = space 
b (tem)
2) Nova_entrada = 
space b i (tem)
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
• Nova_entrada = space 
b i (tem)
2) Nova_entrada = 
space b i n (não tem)
 3) Insere no dicionário 4) Manda código 
de 
nova_entrada, 
sem o caractere 
final  space b i
5) nova_entrada=n
6) Nova_entrada’= i t spa
7) Insere nova_entrada’ 
no dicionário
8) Saída = cadeia do 
código recebido  spa b i
9) nova_entrada’=spa b i
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
• Nova_entrada = n 
(tem)
2) Acabou mensagem 3) Manda código 
de 
nova_entrada  
n
4) Manda 
parada
6) Nova_entrada’ = spa b i 
n
7) Insere nova_entrada’ 
no dicionário
8) Saída = cadeia do 
código recebido  n
9) Recebe parada
 
 Exemplo 1: mensagem “itty bitty bit bin”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
 
 Exemplo 2: mensagem “aaaaaa”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
97 a - - 256 (início) - - -
1) Nova_entrada = 
2) Manda 
código de início
3) Recebendo 
código de início, 
limpa dicionário e faz 
nova_entrada’ =  
4) Nova_entrada = a
 
 Exemplo 2: mensagem “aaaaaa”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
 97 a - - 256 (início) - - -
 97 a 258 aa 97 (a) - - a
1) Nova_entrada = aa
(não tem no dicionário) 
 2) Insere no dicionário
3) Manda 
código de 
nova_entrada, 
sem o caractere 
final  a
5) Produz como saída 
o caractere do código 
recebido  a
6) Nova_entrada’ = a
4) nova_entrada=a 
(último caractere 
recebido)
 
 Exemplo 2: mensagem “aaaaaa”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
97 a - - 256 (início) - - -
97 a 258 aa 97 (a) - - 
a
97 a - - - - - - 
-
1) Nova_entrada = a
(tem no dicionário)
2) Nova_entrada = aa
(tem) 
 
 Exemplo 2: mensagem “aaaaaa”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
97 a - - 256 (início) - - -
97 a 258 aa 97 (a) - - a
97 a - - - - - - -
97 a 259 aaa 258 (aa) 258 aa aa
1) Nova_entrada = aa
(tem no dicionário)
2) Nova_entrada = aaa
(não tem) 
 3) Insere no dicionário
4) Manda 
código de 
nova_entrada, 
sem o caractere 
final  aa
6) Não conhece código 
258  repete 1o 
caractere de cód. anter. 
em Nova_entrada’ = aa
7) Insere nova_entrada’ 
no dicionário
8) Produz saída = cadeia 
do código recebido  aa
5) nova_entrada=a (último 
caractere recebido) 9) nova_entrada’=aa
 
 Exemplo 2: mensagem “aaaaaa”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
97 a - - 256 (início) - - -
97 a 258 aa 97 (a) - - a
97 a - - - - - - -
97 a 259 aaa 258 (aa) 258 aa aa
97 a - - - - - - - 
 
1) Nova_entrada = a
(tem no dicionário)
2) Nova_entrada = aa
(tem) 
 
 Exemplo 2: mensagem “aaaaaa”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
 97 a - - 256 (início) - - -
97 a 258 aa 97 (a) - - a
97 a - - - - - - -
97 a 259 aaa 258 (aa) 258 aa aa
97 a - - - - - - - 
97 a - - - - - - - 
 
1) Nova_entrada = aa
(tem no dicionário)
2) Nova_entrada = aaa
(tem) 
 
 Exemplo 2: mensagem “aaaaaa”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
97 a - - 256 (início) - - -
97 a 258 aa 97 (a) - - a
97 a - - - - - - -
97 a 259 aaa 258 (aa) 258 aa aa
97 a - - - - - - - 
97 a - - - - - - - 
- - - - 259 (aaa) 259 aaa aaa
- - - - 257 (parada) - - - 
1) Nova_entrada = aaa
(tem no dicionário)
2) Recebeu parada4) Manda 
código de 
nova_entrada, 
seguido por 
parada
6) Não conhece código 259 
 repete 1o carac. de cód. 
ant. em nova_entrada’ = aaa
7) Insere nova_entrada’ no 
dicionário
8) Produz saída = cadeia do 
código recebido  aaa
 
 Exemplo 2: mensagem “aaaaaa”
 Codificação Transmissão Decodificação
 Entrada nova_entrada nova_entrada Saída
 dicionário dicionário
97 a - - 256 (início) - - -
97 a 258 aa 97 (a) - - a
97 a - - - - - - -
97 a 259 aaa 258 (aa) 258 aa aa
97 a - - - - - - - 
97 a - - - - - - - 
- - - - 259 (aaa) 259 aaa aaa
- - - - 257 (parada) - - - 
 
Compressão LZW
 Codificador e decodificador criam dicionário a 
medida que processamento é feito
 Dicionário não precisa ser transmitido explicitamente
 Codificador lida com o texto em um único passo
 
Compressão LZW
 Codificador e decodificador criam dicionário a 
medida que processamento é feito
 Dicionário não precisa ser transmitido explicitamente
 Codificador lida com o texto em um único passo
 O número de bits transmitido é reduzido?
 Exemplo 1:
 Manda 18 caracteres de 8 bits (144 bits) em 14 transmissões 
de 9 bits (126 bits)
 Redução de 12,5%
 
Compressão LZW
 Codificador e decodificador criam dicionário a medida 
que processamento é feito
 Dicionário não precisa ser transmitido explicitamente
 Codificador lida com o texto em um único passo
 O número de bits transmitido é reduzido?
 Exemplo 1:
 Manda 18 caracteres de 8 bits (144 bits) em 14 transmissões 
de 9 bits (126 bits)
 Redução de 12,5%
 Exemplo 2:
 Manda 6 caracteres de 8 bits (48 bits) em 5 transmissões de 9 
bits (45 bits)
 Redução de 6,25%
 
Discussão: compressão 
sem perda
 É usada em várias aplicações
 Ex.: formato zip do Unix, formato GIF
 
Discussão: compressão 
sem perda
 É usada em várias aplicações
 Ex.: formato zip do Unix, formato GIF
 É usada em casos em que é importante que os dados originais e 
descomprimidos sejam idênticos (ou desvios nos dados originais 
podem ser prejudiciais)
 Ex.: programas executáveis, programa fonte, texto, registros de 
banco, artigos, etc.
 
Discussão: compressão 
sem perda
 É usada em várias aplicações
 Ex.: formato zip do Unix, formato GIF
 É usada em casos em que é importante que os dados originais e 
descomprimidos sejam idênticos (ou desvios nos dados originais 
podem ser prejudiciais)
 Ex.: programas executáveis, programa fonte, texto, registros de 
banco, artigos, etc.
 Não há algoritmo sem perda eficiente para todos os tipos de 
dados possíveis
 
Discussão: compressão 
sem perda
 É usada em várias aplicações
 Ex.: formato zip do Unix, formato GIF
 É usada em casos em que é importante que os dados originais e 
descomprimidos sejam idênticos (ou desvios nos dados originais 
podem ser prejudiciais)
 Ex.: programas executáveis, programa fonte, texto, registros de 
banco, artigos, etc.
 Não há algoritmo sem perda eficiente para todos os tipos de 
dados possíveis
 Sequências de dados completamente aleatórias não podem ser 
comprimidas
 
Compressão com perda
 Compressão em que alguma informação da 
mensagem original é perdida
 
Compressão com perda
 Compressão em que alguma informação da 
mensagem original é perdida
 Sequências originais não podem ser geradas 
novamente a partir da sequência comprimida
 
Compressão com perda
 Compressão em que alguma informação da 
mensagem original é perdida
 Sequências originais não podem ser geradas 
novamente a partir da sequência comprimida
 Não necessariamente implica que a qualidade do 
resultado é reduzida
 Ex. Ruído aleatório é frequente em imagens e som
 Algumas perdas em imagens e som também são 
imperceptíveis para o humano
 Ex. Perda de frequências bastante altas
 
Compressão com perda
 Para dados visuais ou auditivos, alguma 
perda de qualidade pode ser tolerada
 
Compressão com perda
 Para dados visuais ou auditivos, alguma 
perda de qualidade pode ser tolerada
 Sem perder a natureza essencial dos dados
 Levando em consideração limitações do sistema 
sensorial humano
 
Compressão com perda
 Para dados visuais ou auditivos, alguma 
perda de qualidade pode ser tolerada
 Sem perder a natureza essencial dos dados
 Levando em consideração limitações do sistema 
sensorial humano
 Compressão com perda é usada 
frequentemente na Internet
 
Compressão com perda
 Usada também em: 
 Câmeras digitais
 Para aumentar capacidade de armazenamento
 DVDs
 Compressão de vídeo com MPEG-2 Video Codec
 Audio
 Métodos de físico-acústica são usados para remover 
componentes não audíveis ou pouco audíveis
 
Compressão com perda
 Vantagem sobre compressão sem perda é que 
muitas vezes compressão com perda produz 
arquivos/mensagens bem menores
 Ainda mantendo requisitos da aplicação
 Em imagens: dobro ou mais de compressão do que sem 
perda
 
Compressão com perda
 Vantagem sobre compressão sem perda é que 
muitas vezes compressão com perda produz 
arquivos/mensagens bem menores
 Ainda mantendo requisitos da aplicação
 Em imagens: dobro ou mais de compressão do que sem 
perda
 
Compressão com perda
 Importante que qualidade “degrade” em 
aspectos menos perceptíveis ao humano
 
Compressão com perda
 Importante que qualidade “degrade” em 
aspectos menos perceptíveis ao humano
 Ex. descartar pixels aleatórios é provavelmente 
mais prejudicial do que descartar alguma 
informação de cor
 
Compressão com perda
 Importante que qualidade “degrade” em 
aspectos menos perceptíveis ao humano
 Ex. descartar pixels aleatórios é provavelmente 
mais prejudicial do que descartar alguma 
informação de cor
 Portanto, maioria das técnicas de compressão 
com perda são dependentes do tipo de mídia
 
Técnicas de compressão 
com perda
 Algumas técnicas gerais:
 Quantização escalar
 Quantização vetorial
 Transformadas
 
Quantização escalar
 Reduzir conjunto de mensagens possíveis S 
a um conjunto menor S’
 
Quantização escalar
 Reduzir conjunto de mensagens possíveis S 
a um conjunto menor S’
 Mapeando cada elemento de S em um elemento 
em S’
 Ex. dividir inteiros de 8 bits por 4 (descartar dois 
menores bits)
 Ex. se há letras maiúsculas e minúsculas, transformar 
todas maiúsculas em minúsculas
 
Quantização escalar
 Reduzir conjunto de mensagens possíveis S 
a um conjunto menor S’
 Mapeando cada elemento de S em um elemento 
em S’
 Ex. dividir inteiros de 8 bits por 4 (descartar dois 
menores bits)
 Ex. se há letras maiúsculas e minúsculas, transformar 
todas maiúsculas em minúsculas
 Mapeamento é de muitos-para-um
  irreversível (com perda)
 
Quantização escalar
 Uniforme: mapeamento é linear
 Ex. dividir inteiros de 8 bits por 4
 
Quantização escalar
 Uniforme: mapeamento é linear
 Ex. dividir inteiros de 8 bits por 4
 Não uniforme: mapeamento não linear
 Em geral melhor que a uniforme 
 Ex. olho é mais sensível a valores baixos de vermelho 
do que altos
 Tornar regiões com valoresbaixos menores que regiões 
com valores maiores
 
Quantização escalar
 Uniforme: mapeamento é linear
 Ex. dividir inteiros de 8 bits por 4
 Não uniforme: mapeamento não linear
 Em geral melhor que a uniforme 
 Ex. olho é mais sensível a valores baixos de vermelho 
do que altos
 Tornar regiões com valores baixos menores que regiões 
com valores maiores
 Outra alternativa: basear mapeamento na probabilidade 
de diferentes entradas 
 
Quantização escalar
 Ex. quantizando imagem de 8 bits por canal 
RGB em 6bits, 5bits, 4bits, 3bits, 2bits, e 1 bit 
8 bits
http://www.ic.unicamp.br/~cpg/material-didatico/mo442/200101/matlab/entregues/grupo1/lab1/exercicio_3/index.html
 
Quantização vetorial
 Quantização escalar permite mapeamento 
individual de cada cor em uma imagem 
colorida em um conjunto menor de valores 
 
Quantização vetorial
 Quantização escalar permite mapeamento 
individual de cada cor em uma imagem 
colorida em um conjunto menor de valores 
 Na prática, pode ser mais efetivo mapear regiões 
tridimensionais do espaço de cores
 
Quantização vetorial
 Quantização escalar permite mapeamento 
individual de cada cor em uma imagem 
colorida em um conjunto menor de valores 
 Na prática, pode ser mais efetivo mapear regiões 
tridimensionais do espaço de cores
 Quantização vetorial: mapear espaço 
multidimensional em conjunto menor de 
mensagens S’
 
Quantização vetorial
 Tipicamente: 
 Seleção de conjuntos representativos do espaço 
de entrada; 
 
Quantização vetorial
 Tipicamente: 
 Seleção de conjuntos representativos do espaço 
de entrada; 
 Mapeamento de todos os outros pontos para o 
representante mais próximo
 
Quantização vetorial
 Tipicamente: 
 Seleção de conjuntos representativos do espaço 
de entrada; 
 Mapeamento de todos os outros pontos para o 
representante mais próximo
 Representante pode ser: 
 Fixo 
 Determinado para cada arquivo/mensagem
 E ser enviado como parte da sequência
 
Quantização vetorial
 Como escolher representantes?
 Tipicamente: algoritmos de agrupamento
 Encontra grupos de pontos nos dados
 Um representante é escolhido para cada grupo 
 
Quantização vetorial
Sem compressão Após quantização vetorial
http://www.steckles.com/compression.html
 
Transformadas
 Transformar entrada em forma diferente
 Para melhor compressão
 Perda de alguns termos sem muita perda 
qualitativa na saída
 
Transformadas
 Transformar entrada em forma diferente
 Para melhor compressão
 Perda de alguns termos sem muita perda 
qualitativa na saída
 Algumas transformadas comuns: seno, cosseno, 
polinômios, harmônicas esféricas, funções 
Bessel, wavelets
 
Transformadas
 Propriedades para compressão:
 Descorrelacionar os dados
 
Transformadas
 Propriedades para compressão:
 Descorrelacionar os dados
 Vários coeficientes de transformada pequenos
 Passíveis de serem descartados
 
Transformadas
 Propriedades para compressão:
 Descorrelacionar os dados
 Vários coeficientes de transformada pequenos
 Passíveis de serem descartados
 Para percepção, alguns termos são mais 
importantes do que outros
 Menos importantes: também passíveis de descartar
 
Transformada Discreta de 
Cossenos (DCT) em imagens
 Separa imagem em partes de frequências 
diferentes
 
Transformada Discreta de 
Cossenos (DCT) em imagens
 Separa imagem em partes de frequências 
diferentes
 Frequências menos importantes podem ser 
descartadas
 Quantização
 As mais importantes são usadas para recuperar a 
imagem na descompressão
 
Transformada Discreta de 
Cossenos (DCT) em imagens
 Separa imagem em partes de frequências 
diferentes
 Frequências menos importantes podem ser 
descartadas
 Quantização
 As mais importantes são usadas para recuperar a 
imagem na descompressão
 JPEG usa DCT como base
 
Transformada Discreta de 
Cossenos (DCT) em imagens
 Separa imagem em partes de frequências 
diferentes
 Frequências menos importantes podem ser 
descartadas
 Quantização
 As mais importantes são usadas para recuperar a 
imagem na descompressão
 JPEG usa DCT como base
 Reduz drasticamente a quantidade de espaço 
ocupado pela imagem
 
Ex. DCT em imagem
original Qualidade 50
Qualidade 20 Qualidade 10
http://www.dip.ee.uct.ac.za/~nicolls/lectures/eee401f/projects/dct.pdf
 
Compressão
 De forma geral, não existe uma técnica 
melhor para todas as situações
	Slide 1
	page2 (1)
	page2 (2)
	page3 (1)
	page3 (2)
	page3 (3)
	page4 (1)
	page4 (2)
	Slide 9
	page6 (1)
	page6 (2)
	page6 (3)
	page7 (1)
	page7 (2)
	page8 (1)
	page8 (2)
	page9 (1)
	page9 (2)
	page9 (3)
	page10 (1)
	page10 (2)
	page10 (3)
	page10 (4)
	page10 (5)
	page11 (1)
	page11 (2)
	page11 (3)
	page11 (4)
	page11 (5)
	page11 (6)
	page12 (1)
	page12 (2)
	page12 (3)
	page12 (4)
	page13 (1)
	page13 (2)
	page13 (3)
	page13 (4)
	page14 (1)
	page14 (2)
	page14 (3)
	Slide 42
	page16 (1)
	page16 (2)
	page16 (3)
	page17 (1)
	page17 (2)
	page17 (3)
	page17 (4)
	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
	page50 (1)
	page50 (2)
	page50 (3)
	page51 (1)
	page51 (2)
	page51 (3)
	page51 (4)
	page52 (1)
	page52 (2)
	page52 (3)
	page53 (1)
	page53 (2)
	page53 (3)
	Slide 95
	page55 (1)
	page55 (2)
	page56 (1)
	page56 (2)
	page56 (3)
	Slide 101
	page58 (1)
	page58 (2)
	page58 (3)
	page59 (1)
	page59 (2)
	page59 (3)
	Slide 108
	page61 (1)
	page61 (2)
	page61 (3)
	page62 (1)
	page62 (2)
	page62 (3)
	Slide 115
	Slide 116
	page65 (1)
	page65 (2)
	page66 (1)
	page66 (2)
	page66 (3)
	page67 (1)
	page67 (2)
	page67 (3)
	page67 (4)
	Slide 126
	Slide 127