Universidade Federal do Pará
Centro de Ciência Exatas e Naturais
Departamento de Informática
Disciplina: Estrutura de Dados II
Professor: Antonio Coimbra Sampaio
Compressão e Compactação
de Dados
Alunos:
Abnatal Junior
Frederico Reis
9908800201
9908802001
Por que comprimir ?
• Redução do espaço físico utilizado
• Agilização da transmissão de dados
Redução do espaço físico utilizado:
Mais comumente utilizada em bancos de
dados, que incorporando a compressão no
projeto de seus registros permite um
significativo ganho em termos de
ocupação em discos e velocidade de
acesso.
Agilizar a transmissão de dados:
• Alterando a taxa de transferência
• Permitindo o aumento do número de
terminais em uma rede
Tipos de compressão
• Compressão lógica
• Compressão física
Compressão lógica
Refere-se ao projeto de representação
otimizada de dados.
Ex: Projeto de um banco de dados
utilizando sequências de bits para
representação de campos de dados.
Compressão física
Realizada sobre dados existentes, a
partir dos quais é verificada a repetição
de caracteres para efetivar a redução
do número de elementos de dados.
Tipos de compressão física
1. Orientada a caracter- indica o
caracter (ou conjunto de
caracteres) repetido através da
substituição por um caracter
especial;
2. Estatística- indica a frequência de
repetição de caracteres e
representa isso através de
sequências de bits
Compressão orientada a caracter
Seleção de caracteres indicadores:
• Run-length
• Run-length estendido
• Inserção e deleção
Codificação run-length
Exemplo: AAAAAAA
Codificador
AAAAAAA run-length
Ce7A
Codificação run-length estendido
Utilizado para número de repetições
maior que 256 e há caracteres
delimitadores no início e no fim da
sequência de codificação.
Exemplo:
SO R A 980 SI
•
•
•
•
•
SO- Shift Out
R- Run length
A- Caracter repetido
980-Nº de repetições do caracter
SI- Shift In
Codificação por inserção e deleção
Utilização de um caracter convencional
quando não for possível a colocação de
caracteres especiais.
Exemplo: K6A
Técnicas de compressão
orientada a caracter:
•
•
•
•
•
•
•
Supressão de caracteres nulos
Mapeamento de bit
Comprimento de fileira
Compactação de meio byte
Codificação diatômica
Substituição de padrões
Codificação relativa
Comprimento de fileira
Notação: CeCN
• Ce-caracter especial
• C- caracter repetido
• N-nº de repetições
Fluxograma para o comprimento de
fileira
Supressão de caracteres nulos
Notação: CeN
Ce-caracter especial
N-Nº de repetições
Exemplo: ...vazio.
Exatamente
Após codificação: ...vazio.Ce9Exatamente
Fluxograma para o algoritmo apresentado:
Mapeamento de bit
Exemplo: ...abacate...
...abacate...codificador ...Mbbcte...
Mbbcte
Mb-Mapa de bits
Mapa de bits: 0 1 0 1 0 1 1 1
abacate
Fluxograma para o mapa de bits
Compactação de meio byte
0
1
2
3
4
5
6
7
8
9
0011
0011
0011
0011
0011
0011
0011
0011
0011
0011
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
Ce N C1 C2 C3 C4 C5 ...
1byte 1byte
1byte
1byte
Ce-caracter especial
N-nº(binário) de caracteres comprimidos
C1-Metade do caracter comprimido
C2 a C5-Metade não comprimivel
Fluxograma para a compactação de
meio byte
Técnica dos sete bits
Aplica-se somente a arquivos texto.
Baseia-se no fato que nenhum caracter
de texto utiliza o oitavo bit.
Exemplo: Compactar ‘ABCD’
A
B
C
D
0 1000001
0 1000010
0 1000011
0 1000100
Após compactação:
1000001.1000010.1000011.1000100
Representação não ASCII
Consiste em adotar uma nova
representação binária para os
caracteres. Só faz sentido se o
número de caracteres distintos
for menor que 128.
Exemplo: Compactar ‘ABCD’
Representação ASCII
Nova representação
A 01000001
00
B
01000010
01
C
01000011
10
D 01000100
11
Antes da compactação:
01000001010000100100001101000100
Após compactação:
00011011
Codificação diatômica
Permite a representação de um par
de caracteres em apenas um caracter
especial.
Exemplo: avião codificador aviCe
Exemplo:
Duplas de ocorrências Grau de ocorrências
ão
12
é
11
qu
14
ãe
03
gu
05
Fluxograma para codificação
diatômica
Substituição de padrões
São estabelecidas tabelas de palavras
de maior freqüência de ocorrência para
substituição com o caracter especial
Palavra =>Ce
Codificação relativa
• Valores intervalares
• Valores binários
Valores intervalares
Val Var1 Var2...
•Val-Primeiro valor da sequência
•VarN-Variação do valor anterior
para o atual
Exemplo:
10.3 10.1 10.8 10.4 10.4 10.9 10.2
Exemplo:
10.3 10.1 10.8 10.4 10.4 10.9 10.2
Codificador
10.3 -.2 .7 -.4 0 .5 -.7
Valores binários
Comparação feita entre uma linha e outra
Exemplo:
...01001011100010101...
...01001011111100001...
A diferença seria em 5 bits:
...______MMMM_M_...
Compressão Estatística
Realiza uma representação otimizada de
caracteres ou grupo de caracteres
• Codificação de Huffman
• Codificação de Shanno-Fano
Codificação de Huffman
Obtém uma nova representação para cada
caracter considerando sua probabilidade de
ocorrência.
O processo de obtenção baseia-se na montagem
de uma árvore binária.
Exemplo
Considerando o conjunto de 8 caracteres
definido abaixo
Caracter
A
B
C
D
E
F
G
H
Representação
000
001
010
011
100
101
110
111
Probabilidade
0.50
0.25
0.12
0.06
0.03
0.02
0.01
0.01
Aplicando a codificação de Huffman, obtemos
uma nova tabela de códigos
Caracter
Código
A
B
C
D
E
F
G
H
0
10
110
1110
11110
111110
1111110
1111111
Largura Probabilidade
1
2
3
4
5
6
7
7
0.50
0.25
0.12
0.06
0.03
0.02
0.01
0.01
Probabilidade
X Largura
0.50
0.50
0.36
0.24
0.15
0.12
0.07
0.07
2.01
Obtenção do código
de Huffman
1
0
1
0
1
0
1
0
1
0
0
1
1
0
H
G
F
E
D
C
B
A
Codificação de Shannon-Fano
Assim como o código de Huffman, este método
também obtém uma nova representação para cada
caracter de acordo com sua probabilidade de
ocorrência.
O processo de obtenção baseia-se na divisão de
conjuntos de probabilidades.
Processo de Codificação
Considerando o conjunto dos caracteres a
codificar definido abaixo
Caracter
Probabilidade
A
B
C
D
0.5
0.3
0.1
0.1
Obtenção do código de Shannon-Fano
A
0.3
00
B
0.3
01
C
0.3
10
D
0.1
11