Compressão de Dados

ORI

Ednaldo Pizzolato

COMPRESSÃO

A Compressão ou Compactação de dados destina-se a retirar a redundância dos dados de forma a diminuir o seu tamanho.

A compressão de dados, como o nome sugere, é o ato de comprimir os dados. Comprimir algo é torná-lo menor. Assim, comprimimos os dados pelos mais diversos motivos entre os quais:

• economizar espaço discos rígidos ou • ganhar desempenho (Modems).

COMPRESSÃO

Assim, o objetivo da compressão de dados é representar a informação da melhor forma possível utilizando a menor quantidade de dados possível.

COMPRESSÃO

Para comprimir utilizamos regras, chamadas de códigos ou protocolos, que quando seguidas, eliminam os bits redundantes de informações.

COMPRESSÃO

Existem 2 tipos de compressão:• Com perdas (Lossy) • Sem perdas (Lossless)

As compressões com perdas são aquelas operações que admitem alguma perda de qualidade dos dados (exemplo típico: as imagens .jpg na internet em que se percebe uma diminuição da qualidade próximo às bordas ou, inclusive, trocas de cor na imagem).

COMPRESSÃO

Existem 2 tipos de compressão:• Com perdas (Lossy) • Sem perdas (Lossless)

As compressões sem perdas são aquelas operações que não admitem alguma perda de qualidade dos dados (exemplo: as imagens gif).

COMPRESSÃO

Em 1948 o pesquisador Claude E. Shannon publicou um artigo intitulado : A Mathematical Theory of Communication em que formulava a teoria da compressão de dados e indicava que existe um limite fundamental para as compressões sem perdas (denotada por H e conhecida como taxa de entropia).

COMPRESSÃO

O valor exato de H depende da informação – mais especificamente, na natureza estatística da mesma. É possível comprimir uma informação (sem perdas) com taxa de compressão próxima a H. Entretanto, é impossível comprimir com taxas melhores que H.

COMPRESSÃO

Shannon também desenvolveu a teoria da compressão com perdas (lossy). Ela é melhor conhecida como a teoria da taxa de distorção (rate-distortion theory). Nessas compressões, o arquivo obtido da descompressão não é exatamente igual ao original. Na verdade, há uma certa quantidade de distorção, D, que é tolerada.

COMPRESSÃO

MODELAGEM

Ordem zero

Primeira ordem

Segunda ordem

Terceira ordem

Geral

COMPRESSÃO

MODELAGEMImagine que alguém vá a uma

biblioteca (com milhares de livros) para escolher um deles, e enviar seu conteúdo pela internet até sua casa (ou colocar em um pen-drive). Vamos assumir que a pessoa tenha escolhido um livro, cuja representação possa ser a seguinte: X = {x1, x2, ...} onde xi são as letras do livro.

COMPRESSÃO

MODELAGEMAgora você deve se imaginar como

sendo o “artista” que vai ter que comprimir este conjunto de letras (sem saber qual o livro que foi escolhido) de forma a ser armazenado no pen-drive, por exemplo. Para você, as letras são variáveis randômicas que mapeiam as letras e símbolos do alfabeto.

COMPRESSÃO

MODELAGEM

Na modelagem de ordem zero, cada caractere tem igual probabilidade de ocorrer, independentemente dos caracteres anteriores. Claro que isso não vai representar corretamente as palavras em um determinado idioma.

COMPRESSÃO

MODELAGEM

Na modelagem de primeira ordem, cada caractere ainda mantém sua independência dos demais, mas já se deve contemplar o fato de que algumas letras são mais freqüentes que outras.

COMPRESSÃO

MODELAGEM

Na modelagem de segunda ordem, cada caractere é dependente do caractere mais à esquerda. Por exemplo, dado que o caractere observado é q existe enorme probabilidade que o próximo seja u.

COMPRESSÃO

MODELAGEM

Na modelagem de terceira ordem, cada caractere é dependente dos dois caracteres mais à esquerda...

COMPRESSÃO

A taxa de entropia de um dado é um número que depende somente da natureza estatística do referido dado. Se o dado tem uma modelagem simples, então a taxa de entropia pode ser calculada facilmente.

COMPRESSÃO

Na modelagem de ordem zero, os caracteres são estatisticamente independentes uns dos outros (cada letra do alfabeto tem igual probabilidade de ocorrer). Seja m o tamanho do alfabeto. Assim, a entropia pode ser dada por:

Se o alfabeto contiver 27 letras, então H = 4.75 bits/caractere. Notar que no ASCII são 8 bits por caractere.

caracterebitsH m /log2

COMPRESSÃO

Na modelagem de primeira ordem, como apresentado anterioremente, os caracteres ainda são estatisticamente independentes uns dos outros, mas a probabilidade de cada letra ocorrer deve ser contemplada. Assim, se m é o tamanho do alfabeto, a entropia pode ser dada por:

Se o alfabeto contiver 27 letras, então, neste caso, H seria 4.07 bits/caractere. Novamente, no ASCII são necessários 8 bits por caractere.

caracterebitsppH i

m

ii /log2

1

COMPRESSÃO

Compressão = modelo + código

entrada modelo

codificador

saída

simb

prob.

Para ilustrar, vamos utilizar um alfabeto de 2 letras {a,b}, onde as probabilidades são dadas pelo grafo a seguir:

COMPRESSÃO

a b 0.90.9 0.1

0.1

Para a modelagem de ordem zero, teríamos cada caractere associado a um bit: a 0 e o b 1, já que são caracteres com probabilidades iguais de ocorrer.

Seq. Original : aaaaaaabbbbbbbbbbbbbaaaa

0000000111111111111100001 bit / caractere1 bit / caractere

COMPRESSÃO

Para a modelagem de SEGUNDA ordem, teríamos a seguinte tabela de probabi-lidade:

Seq. Original :

aaaaaaabbbbbbbbbbbbbaaaa

0 0 0 1101010.............. 0 0

0,83 bit / caractere bit / caractere

COMPRESSÃOaa 0,45 0

bb 0,45 10

ab 0,05 110

ba 0,05 111

Suponha que estejamos, agora, trabalhan-do com um alfabeto de 5 letras, onde as probabilidades de ocorrência são as seguintes:

a 0,4b 0,3c 0,1d 0,1e 0,1

COMPRESSÃO

Suponha que estejamos, agora, trabalhan-do com um alfabeto de 5 letras, onde as probabilidades de ocorrência são as seguintes:

a 0,4 0b 0,3 1c 0,1 1d 0,1 1e 0,1 1

COMPRESSÃO

Suponha que estejamos, agora, trabalhan-do com um alfabeto de 5 letras, onde as probabilidades de ocorrência são as seguintes:

a 0,4 0b 0,3 10c 0,1 11d 0,1 11e 0,1 11

COMPRESSÃO

Suponha que estejamos, agora, trabalhan-do com um alfabeto de 5 letras, onde as probabilidades de ocorrência são as seguintes:

a 0,4 0b 0,3 10c 0,1 110d 0,1 111e 0,1 111

COMPRESSÃO

Suponha que estejamos, agora, trabalhan-do com um alfabeto de 5 letras, onde as probabilidades de ocorrência são as seguintes:

a 0,4 0b 0,3 10c 0,1 110d 0,1 1110e 0,1 1111

COMPRESSÃO

Agora, vamos supor o mesmo alfabeto (5 letras), mas com codificação de huffman.

a 0,4

b 0,3

c 0,1

d 0,1

e 0,1

COMPRESSÃO

Agora, vamos supor o mesmo alfabeto (5 letras), mas com codificação de huffman.

a 0,4

b 0,3

c 0,1

d 0,1

e 0,1

COMPRESSÃO

d e

D-E

Agora, vamos supor o mesmo alfabeto (5 letras), mas com codificação de huffman.

a 0,4

b 0,3

c 0,1

d-e 0,2

COMPRESSÃO

d e

D-E c

D-E-C

Agora, vamos supor o mesmo alfabeto (5 letras), mas com codificação de huffman.

a 0,4

b 0,3

DEC 0,3

COMPRESSÃO

d e

D-E c

D-E-C

• Trabalho– Fazer um resumo de compressão, colocando

informações sobre codigo aritmético e algoritmos baseados em dicionário;

– Codificar Shannon-Fano e Huffman.

COMPRESSÃO