Compressão de Dados
Introdução
Compressão de dados é o processo de codificar
um corpo de informações digitais dentro de uma
representação menor, da qual o original pode ser
reconstituído posteriormente
Se a informação pode sempre ser reconstituída
exatamente sem qualquer distorção ou perda de
informação, o processo é denominado “sem
perda”
2
Compressão de Imagens
Para a codificação de imagens a ISO e o
CCITT criaram dois comitês:
Joint Photograph Expert Group (JPEG) que
trata de imagens estáticas
 Motion Picture Expert Group (MPEG) que trata
de imagens em movimento

3
Compressão de Imagens
Os algoritmos JPEG, MPEG, JBIG, MHEG
utilizam a Transformada Direta de Cosseno
(DCT)
JPEG obtém taxas de compressão de 90 a 95
% com pouca ou nenhuma degradação
Caso se aceite uma degradação pouco maior
pode-se atingir taxas de compressão de 98 %.
4
Compressão de Imagens Binárias
O algoritmo JBIG (Joint Bi-level Image
Experts Group) trata de imagens binárias,
tipo FAX
5
Benefícios
Os dois principais benefícios trazidos pela
compressão de dados são :
Capacidade de armazenamento de informações
crescente: o uso de compressão de dados pode
aumentar significativamente a capacidade de
armazenamento do sistema
 Transmissão de dados crescente: informações
digitais podem ser comprimidas antes de serem
transmitidas de um módulo para outro

6
Finalidades
As razões para que se comprimam dados
são:
manutenção de mais dados “on line”;
 redução de tempo necessário à transferência de
dados;
 retardo na aquisição de mais discos;
 redução do número de fitas “back-up”

7
Compressão de Dados com
Perdas e sem Perdas
A compressão de Dados pode ser com perdas e sem perdas
Na Compressão com Perdas o arquivo reconstruído não
coincide com o arquivo original podendo ser utilizada
quando o arquivo for para uso de seres humanos (som e
imagem por exemplo)
Na Compressão sem Perdas o arquivo reconstruído
coincide com o arquivo original podendo ser utilizado por
computadores
As taxas de compressão obtidas por Compressão com
Perdas são muito maiores do que aquelas obtidas por
Compressão sem Perdas
8
Técnicas de compressão de dados sem Perdas
Técnicas pontuais
Supressão de “brancos”
 Supressão de Repetições(“Run Lenght”)

Codificação Estatística
Código de Huffman
 Codificação Aritmética

Codificação por dicionário

Códigos de Lempel-Ziv
9
Supressão de Repetições(“Run Lenght”)
<seqüência de “escape”> <N> <K>
Exemplo :
GOOOOOOOL  G~7OL
10
Código de Huffman
Criação da árvore de Huffman
Codificação
Decodificação
11
Criação da Árvore de Huffman
1.
2.
3.
4.
5.
6.
Determinação da freqüência de ocorrência de cada símbolo;
Criação de uma Fila de Prioridades por freqüência de ocorrência de
cada símbolo, na qual cada nó será uma raiz de árvore binária
contendo um símbolo e a freqüência de ocorrência correspondente;
Retirada da Lista de Prioridades os dois primeiros nós e sua inclusão
como filhos esquerdo e direito de um nó de agregação que não tenha
símbolo mas cuja freqüência de ocorrência seja igual à soma das
freqüências de ocorrência dos símbolos contidos em seus filhos;
Inclusão na Lista de Prioridades do nó de agregação assim criado;
Repetição dos passos 4 e 5 até que a Fila de Prioridades contenha um
só nó, que é a raiz da árvore de Huffman;
Atribuição do código correspondente a cada símbolo identificado
pela trajetória obtida da raiz até a folha da árvore de Huffman que
contém o símbolo.
12
Codificação de Huffman
1. Identificação na tabela de códigos de
Huffman do código correspondente ao
símbolo a codificar;
2. Substituição do símbolo a codificar pelo
código correspondente.
13
Decodificação de Huffman
1. Escolha do primeiro bit do código como bit corrente;
2. Descida um nível na árvore de Huffman de acordo
com o valor do bit corrente (passar ao filho mais velho se o
bit for 0 ou passar ao filho mais novo se o bit for 1) e
atribuição ao bit corrente do próximo bit do “string” de bits
do código a decodificar;
3. No caso de ser atingida uma folha da árvore de
Huffman deve-se fazer a substituição dos bits
correspondentes à trajetória até a folha pelo caractere
contido nessa folha;
4. Repetição dos passos 2 e 3 até que termine o “string”
de bits do código a decodificar.
14
Exemplo de Codificação por Huffman
O exemplo que se segue mostra uma situação hipotética
na qual os símbolos a considerar e respectivas
freqüências são:
Símbolos $ # @ / * - +
Freqüência 3 10 12 15 18 20 22
Nesse exemplo para codificar a seqüência
-@/+* se obteve como resultado 00100110011
15
Símbolos $
Níveis
1 3
#
@
10
1
2
3
1
25
2 12
3
1
25
2 12
3
1
25
2 12
18
20
22
13
12
15
18
20
15
18
20
22
33
20
22
10
15
3
18
10
33
15
42
18
20
58
42
25
33
13
3
22
10
15
20
22
18
10
1
100
2
4
22
10
13
3 12
3
+
15
1
4
-
12
13
3
2
*
13
3
3
/
42
20
58
22
25
12
33
13
15
18
16
Codificação Aritmética
Processo de dois passos sobre os dados
Considera-se a existência de n caracteres, cada
qual com probabilidade pi , 1< = i < = n.
O espaço de mapeamento do código é o espaço
probabilidade que vai de 0 a 1 (0% a 100%)
0
1
pi
pj
pn
17
Codificação Aritmética
Um valor x qualquer dentro deste espaço, identifica o caractere ci , tal que:
i 1
i
j 1
j 1
 pj  x   pj
Para codificar uma seqüência de caracteres, adota-se o seguinte procedimento:
18
Codificação Aritmética
Determina-se a probabilidade Pi1 de ocorrência do primeiro símbolo
da seqüência
2 - Escolhe-se como novo espaço de probabilidades o intervalo
compreendido entre
1-
i1 1
 pj
j 1
i1
e
 pj
j 1
3 - Determina-se a probabilidade Pi2 de ocorrência do segundo símbolo
da seqüência
4 - Escolhe-se como novo espaço de probabilidades o intervalo
compreendido entre i1-1
i2
i2 1
 pj e  pj
j 1
j 1
5 - E assim sucessivamente
6 - A representação da seqüência é feita por dois valores:
- m ou tamanho da seqüência;
- identificador do intervalo;
19
Passos para a preparação do
emprego da codificação aritmética
1. Determinação da freqüência de ocorrência de
cada símbolo;
 2. Criação de uma tabela de faixas de
freqüências de símbolos classificada em ordem
crescente de freqüência de ocorrência de cada
símbolo.

20
Passos para a codificação aritmética
1.
2.
3.
4.
5.
Identificação do espaço de freqüências
Faixa de freqüências do primeiro símbolo
Coordenada ou código correspondente ao
primeiro símbolo - limite inferior da faixa de
freqüências
Nova faixa de freqüências - produto da faixa
anterior pelo limite inferior da faixa de
freqüências
Coordenada ou código correspondente ao
próximo símbolo que é o limite inferior da faixa
de freqüências desse símbolo;
21
Passos para a codificação aritmética
6. Coordenada ou código correspondente a
seqüência de todos os caracteres que já
foram codificados que é obtida da soma do
código anterior com o produto da amplitude
da faixa de freqüências corrente pelo limite
inferior dessa mesma faixa;
7. Repetição dos passos 4, 5 e 6 até encontrar o
final da palavra a codificar(ou equivalente);
8. Substituição da palavra a codificar pelo
código correspondente acompanhado do
número de símbolos da palavra.
22
Passos para a decodificação aritmética
Enquadramento do código a decodificar dentro
de uma das faixas de freqüências;
2. Enquanto o número de símbolos da palavra a
decodificar (ou equivalente) não for igual a zero
proceder
a
identificação
o
símbolo
correspondente ao limite inferior da faixa de
freqüências, o decremento do número de
símbolos por decodificar, a subtração do código
corrente do limite inferior da faixa de freqüências
e a divisão do valor obtido pela largura da faixa
de freqüências do caractere recém decodificado.
1.
23
Exemplo de Codificação Aritmética
Situação hipotética na qual os símbolos a
considerar e respectivas freqüências são:
Símbolos
a b c d e
Freqüência 10 15 20 25 30
Nesse exemplo para codificar a seqüência
cace se obteve como resultado 0,257800
24
Exemplo de Codificação Aritmética
Alfabeto (símbolos)
símbolo
a
b
c
d
e
início
final
0,000000 0,100000
0,100000 0,250000
0,250000 0,450000
0,450000 0,700000
0,700000 1,000000
Codificação
Caractere alto
baixo
faixa
s.sup
s.inf
alto
baixo
c
1,000000 0,000000 1,000000 0,450000 0,250000 0,450000 0,250000
a
0,450000 0,250000 0,200000 0,100000 0,000000 0,270000 0,250000
c
0,270000 0,250000 0,020000 0,450000 0,250000 0,259000 0,255000
e
0,259000 0,255000 0,004000 1,000000 0,700000 0,259000 0,257800
Decodificação
25
símbolo
a
b
c
d
e
início
final
0,000000 0,100000
0,100000 0,250000
0,250000 0,450000
0,450000 0,700000
0,700000 1,000000
Exemplo de Decodificação Aritmética
Codificação
Alfabeto (símbolos)
Caractere alto
baixo
faixa
s.sup
s.inf
alto
ba
símbolo
início 0,000000
final 1,000000 0,450000 0,250000 0,450000 0
c
1,000000
a
0,000000
0,100000
a
0,450000
0,250000
0,200000 0,100000 0,000000 0,270000 0
b
0,100000 0,250000
c
0,270000
0,250000 0,020000 0,450000 0,250000 0,259000 0
c
0,250000 0,450000
e
0,259000 0,255000 0,004000 1,000000 0,700000 0,259000 0
d
0,450000 0,700000
e
0,700000 1,000000
Decodificação
Codificação
CódigoCaractere
Símbolo
s.sup baixo s.inf faixa faixa s.sup Código
alto
s.inf
alto
0,257800
c 1,000000
0,450000
0,250000
0,200000
0,039000
c
0,000000
1,000000
0,450000
0,250000 0,45000
0,039000
a
0,100000
0,000000
0,100000
0,390000
a
0,450000 0,250000 0,200000 0,100000 0,000000 0,27000
0,390000
c 0,270000
0,450000
0,250000
0,200000
0,700000
c
0,250000
0,020000
0,450000
0,250000 0,25900
0,700000
e 0,259000
1,000000
0,700000
0,300000
0,000000
e
0,255000
0,004000
1,000000
0,700000 0,25900
26
Codificação aritmética
Um algoritmo simplificado para a
codificação aritmética poderia ser como
o que se segue, no qual a estrutura s
possui três atributos relativos a faixa de
freqüências de cada caractere
limite inferior
 limite superior
 escala ou largura da faixa

27
Codificação aritmética
Início
baixo  0.0
alto  1.0
Ler de (arquivo=entrada) c
Enquanto ( c  EOF )
 Converter_caractere_em_símbolo(c,s)
faixa  alto - baixo
alto  baixo + faixa * s.superior/s.escala
baixo  baixo + faixa * s.inferior/s.escala
Ler de (arquivo=entrada) c
Fim do Enquanto
Fim do Procedimento
28
Decodificação aritmética
Início
Ler de (arquivo=entrada) código
Enquanto ( c  EOF )
 Converter_código_em_símbolo(código,s)
faixa  s.superior - s.inferior
código  (código - s.inferior)/faixa
 Gravar em (arquivo=saída) s
Ler de (arquivo=entrada) c
Fim do Enquanto
Fim do Procedimento
29
Compressão por Dicionário
Compressão por Dicionário
Ocorre quando, toda vez que uma frase
é repetida , ela é substituída por uma
referência à ocorrência original da frase
A compactação resultante pode ser
significante dependendo da
redundância de informações
Esse tipo de compressão é feita pelos
códigos de Lempel & Ziv
31
Códigos de Lempel-Ziv
Os algoritmos de Lempel-Ziv utilizam
duas áreas de trabalho:
1. dicionário, ou "buffer" histórico, aonde
ficam armazenadas informações
codificadas, em caráter permanente.
2. área da pesquisa, aonde fica o "string" a
comprimir ou descomprimir.
32
Códigos de Lempel-Ziv
O método consiste em identificar, na
seqüência de entrada, na área de pesquisa,
a maior seqüência de símbolos armazenada
no dicionário e substituí-la, na compressão,
por um código. Na descompressão os
códigos da área de pesquisa devem ser
substituídos pelas seqüências de símbolos
correspondentes do dicionário.
Existem dois algoritmos básicos, o LZ1 e o
LZ2 que diferem na estrutura do dicionário.
33
Códigos de Lempel Ziv
Lz1 ou LZ77 com variante LZSS
LZ2 ou LZ78 com variante LZW
 SS
de Storer-Szymanski (1982)
 W de Welch (1984)
34
Esquema de LZ1 ou LZ77
35
LZ77 e LZSS
Uma variante do LZ77 é a chamada
LZSS
O dicionário, no processo LZSS,
armazena as frases na janela de texto
como simples blocos contíguos de texto
Este processo cria uma estrutura
adicional na árvore de busca
36
Esquema de LZ2 ou LZ78
37
LZ78 e LZW
O dicionário passa a ser um "array" bidimensional
As linhas do "array" têm comprimento (número de
colunas ) variável
As primeiras linhas contêm cada qual apenas um
símbolo do alfabeto
As linhas subseqüentes contem dígrafos, trígrafos,
etc.
À medida que as seqüências vão aparecendo no
texto de entrada vão sendo dicionarizadas, ou seja
transformadas em linhas do "array“
A palavra código é a maior linha do "array" dicionário
cujo conteúdo coincide com a seqüência a ser
comprimida
38
Codificação LZW
Início
velho_string ¬ b /* caractere "branco" */
Ler de (arquivo=entrada) c
Enquanto ( c <> EOF )
novo_string ¬ velho_string + c
/* concatenação de velho_string e c */
Se (novo_string Î dicionário)
então velho_string ¬ novo_string
senão código ¬ dicionário (velho_string)
Gravar em (arquivo=saída) código
Adicionar-ao_dicionário(novo_string)
velho_string ¬ c
Fim do Se
Ler de (arquivo=entrada) c
Fim do Enquanto
código ¬ dicionário (velho_string)
Gravar em (arquivo=saída) código
Fim do Procedimento
39
Decodificação LZW
Início
Ler de (arquivo=entrada) velho_string
Gravar em (arquivo=saída) velho_string
Ler de (arquivo=entrada) novo_código
Enquanto ( novo_código <> EOF )
novo_string ¬ dicionário (novo_código)
Gravar em (arquivo=saída) novo_string
Adicionar_caractere_a_string
(velho_string, novo_string[0])
Adicionar_ao_dicionário(velho_string)
velho_string ¬ novo_string
Ler de (arquivo=entrada) novo_código
Fim do Enquanto
Fim do Procedimento
40
Exemplo de LZW
Como exemplo do processo de
codificação LZW será codificado o texto
"errei erro errado" e a seguir o
resultado será submetido ao processo
de decodificação
41
Codificação
Entrada
e
r
r
e
i
b
e
r
r
o
b
e
r
r
a
d
o
EOF
velho_string
b
e
r
r
e
i
b
be
r
rr
o
b
novo_string  ao dicionário
be
não
er
não
rr
não
re
não
ei
não
ib
não
be
sim
ber
não
rr
sim
rro
não
ob
não
be
sim
be
ber
r
a
d
o
ber
berr
ra
ad
do
sim
não
não
não
não
código
32 (b)
101 (e)
114 (r)
114 (r)
101 (e)
105 (i)
256
dicionário
256 be
257 er
258 rr
259 re
260 ei
261 ib
262 ber
258 263 rro
111 (o) 264 ob
262
114 (r)
97 (a)
100 (d)
111 (o)
265 berr
266 ra
267 ad
268 do
velho_string
e
r
r
e
i
b
be
r
rr
o
b
be
ber
r
a
d
o
42
Decodificação
Entrada
101 (e)
114 (r)
114 (r)
101 (e)
105 (i)
256
258
111 (o)
262
114 (r)
97 (a)
100 (d)
111 (o)
EOF
velho_string
b
e
r
r
e
i
be
rr
o
ber
r
a
d
novo_string
e
r
r
e
i
be
rr
o
ber
r
a
d
o
velho_string
be
er
rr
re
ei
ib
ber
rro
ob
berr
ra
ad
do
dicionário
256 be
257 er
258 rr
259 re
260 ei
261 ib
262 ber
263 rro
264 ob
265 berr
266 ra
267 ad
268 do
velho_string
e
r
r
e
i
be
rr
o
ber
r
a
d
o
43