Universidade Federal do Pará Centro de Ciência Exatas e Naturais Departamento de Informática

Universidade Federal do ParáCentro de Ciência Exatas e Naturais

Departamento de InformáticaDisciplina: Estrutura de Dados II

Professor: Antonio Coimbra Sampaio

Compressão e Compactação

de Dados

Alunos: Abnatal Junior 9908800201Frederico Reis 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

• Run-length• Run-length estendido

• Inserção e deleção

Seleção de caracteres indicadores:

Codificação run-length

Exemplo:

run-lengthAAAAAAA Ce7A

Codificador

AAAAAAA

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- Shift Out• R- Run length• A- Caracter repetido• 980-Nº de repetições do caracter• SI- Shift In

SO R A 980 SI

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: CeNCe-caracter especialN-Nº de repetições

Exemplo: ...vazio. Exatamente

Após codificação:...vazio.Ce9Exatamente

Fluxograma para o algoritmo apresentado:

Mapeamento de bit

Exemplo: ...abacate...

codificador...abacate... ...Mbbcte...

Mbbcte

Mb-Mapa de bits

Mapa de bits:0 1 0 1 0 11 1

a b a c a t e

Fluxograma para o mapa de bits

Compactação de meio byte

0123456789

0011001100110011001100110011001100110011

0000000100100011010001010110011110001001

Ce N C1 C2 C3 C4 C5 ... 1byte 1byte 1byte 1byte

Ce-caracter especialN-nº(binário) de caracteres comprimidosC1-Metade do caracter comprimidoC2 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 0 1000001B 0 1000010C 0 1000011D 0 1000100

1000001.1000010.1000011.1000100

Após compactação:

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:

Após compactação:

00011011

01000001010000100100001101000100

Codificação diatômica

Permite a representação de um par de caracteres em apenas um caracter especial.Exemplo: avião

codificador aviCe

Duplas de ocorrências

Grau de ocorrências

ão 12

é 11

qu 14

ãe 03

gu 05

Exemplo:

Fluxograma para codificação diatômica

Substituição de padrões

Palavra =>Ce

São estabelecidas tabelas de palavras de maior freqüência de ocorrência para substituição com o caracter especial

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 outraExemplo:

...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 Representação Probabilidade

A 000 0.50B 001 0.25C 010 0.12D 011 0.06E 100 0.03F 101 0.02G 110 0.01H 111 0.01

Caracter Código Largura ProbabilidadeProbabilidade

X Largura

A 0 1 0.50 0.50B 10 2 0.25 0.50C 110 3 0.12 0.36D 1110 4 0.06 0.24E 11110 5 0.03 0.15F 111110 6 0.02 0.12G 1111110 7 0.01 0.07H 1111111 7 0.01 0.07

2.01

Aplicando a codificação de Huffman, obtemos uma nova tabela de códigos

F E D C B AH G

1 0

1 0

1 0

1 0

1 0

1 0

1 0

Obtenção do códigode Huffman

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 0.5B 0.3C 0.1D 0.1

A 0.3

B 0.3

C 0.3

D 0.1

0

0

1

1

0

1

0

1

Obtenção do código de Shannon-Fano