Algorítmos e estrutura de dados III

Algorítmos e estrutura de dados III

Carlos Oberdan Rolim

Ciência da Computação

Sistemas de Informação

Compressão e Compactação de dados

Compressão de Dados X Compactação de Dados

São dois processos distintos

Compressão: reduz a quantidade de bits para representar algum dado

Compactação: união dados que não estejam unidos.

Ex.: Desfragmentação de discos

Compressão de Dados

A compressão de dados, como o próprio nome sugere, é o ato de comprimir dados

Comprimir algo é torná-lo menor, através de algum algoritmo de compressão, reduzindo a quantidade de bits para se representar um dado

Comprimir dados destina-se também a retirar a redundância, baseando-se que muitos dados contém informações redundantes que podem ou precisam ser eliminadas de alguma forma

Ex. A seqüência ‘AAAAAA’, que ocupa 6 bytes, poderia ser comprimida para ‘6A’, que ocupa 2 bytes

Compressão de Dados

Além da eliminação de dados redundantes, a compressão de dados apresenta algumas vantagens:

A economia de espaço em disco: quanto mais a informação for comprimida, maior a quantidade de informação pode ser armazenada;

Rapidez no tempo de transmissão de dados: informações comprimidas são transmitidas mais rapidamente daquelas que não estão;

MAS

Tem-se um Preço a pagar => o custo computacional para codificar e decodificar o texto.

Compressão de Dados

Com o avanço da tecnologia, a velocidade de processamento aumentou aproximadamente 2 mil vezes. Melhor investir mais poder de computação em compressão com o objetivo de obter mais espaço em disco ou menor tempo de transmissão.

Além disso, métodos recentes de compressão têm permitido:

Obter maior compressão em relação a métodos tradicionais, gerando maior economia de espaço.

Acessar diretamente qualquer parte do texto comprimido sem necessidade de descomprimir todo o texto desde o início

Razão de Compressão

Uma das formas de se verificar a eficiência de um algoritmo é através da razão de compressão

Ela é definida pela porcentagem que o arquivo comprimido representa em relação ao tamanho do arquivo não comprimido.

Exemplo: se o arquivo não comprimido possui 100 bytes e o arquivo comprimido resultante possui 30 bytes, então a razão de compressão é de 30%, ou 10:3

Tipos de Compressão

Existem dois tipos de compressão:

Compressão sem perda de dados

Compressão com perda de dados

Compressão sem Perda de Dados

Compressão sem Perda de Dados

Definido como uma operação sem perdas de nenhum dado

A informação é comprimida por algum algoritmo e, ao descomprimir, todas as informações são recuperadas

Exemplo típico: arquivos bzip, gzip, .gz

Os mais conhecidos são o .zip ou .rar.

Compressão sem Perda de Dados

Ele é usado quando é importante que a informação original e a descompactada sejam idênticas

Ex.: executáveis e documentos texto

E com relação às imagens?

Alguns formatos usam apenas esse tipo. Ex. PNG e GIF*

Outros formatos usam ambos. Ex.: TIFF e MNG

Outros formatos usam algoritmos com perdas. Ex.: .bmp, .jpeg

Técnicas de Compressão sem Perda de Dados

Antes de se utilizar a técnicas de compressão, é necessário saber qual o tipo de informação que será compactada

Texto

Imagens

Sons

Algoritmos de compactação de textos não são eficientes na compactação de sons

Existem basicamente dois tipos de algoritmos de de compressão sem perda de dados :

Algoritmos de Modelos Estatísticos

Transformação de Burrows-Wheeler

LZ77

LZW

Algoritmos codificados que produzem seqüência de bits

Codificação Aritmética ou Freqüência de Caracteres

Codificação de Huffman

Existem algoritmos que são mesclas dos dois tipos de algoritmos. Ex.: o algoritmo DEFLATE utiliza uma combinação do algoritmo LZ77 e de Huffman.

Técnicas de Compressão sem Perda de Dados

Freqüência de Caracteres

Idéia bastante simples: determina-se a quantidade de símbolos idênticos consecutivos na cadeia

Cada uma das sub-seqüências máximas de símbolos na cadeia é substituída por um número

Esse número indica a freqüência do símbolo em questão

Freqüência de Caracteres – Exemplo

BBBEAAAAFFHHHHHCBMMALLLCDDBBBBBBBCC

3B1E4A2F5HCB2MA3LC2D7B2C

E se a conjunto de caractere tivesse um símbolo numérico?

Nesse caso, emprega-se um símbolo especial, ex., @, para anunciar que o ítem após esse símbolo representa um número

Freqüência de Caracteres – Exemplo

AAA33333BA6666888DDDDDDD99999999999AABBB1

3A5@3BA4@63@87D11@92A3B1@1

Codificação de Huffman - Motivação

Um dos métodos mais conhecidos

Cada caracter ASCII usa 7 bits – 8 bits para ASCII extendido

Em um texto a letra E aparece mais vezes que a letra Z

Como o padrão é fixo os caracteres usam a mesma quantidade de bits

A idéia do algoritmo é atribuir códigos mais curtos a símbolos com freqüências altas

Usar número variável de bits de acordo com a freqüência

A = 0 E = 110 I =10 O= 11 U=101 !=111

Necessidade de compactar dados

Coleção de dados com 50.000 ocorrencias de a, e, i, o, u, !. Caracteres com a seguinte frequencia:

Para armazenar 6 caracteres com sequencia fixa de bits 2 bits não serve, sendo necessários 3 bits.

Então total de bits será 50.000 x 3 = 150.000 bits

Caracter A E I O U !

Frequencia 52 8 12 11 7 10

Necessidade de compactar dados

Agora vamos supor que os caracteres são representados com uma sequencia variavel de bits

Abaixo está o cálculo do total de bits usado

Caracter A E I O U !

Sequencia variavel 0 110 10 11 101 111

Caracter A E I O U !

Qtd de bits 1 3 2 2 3 3

Frequencia 52 8 12 11 7 10

Total por carac. 26.000 12.000 12.000 11.000 10.500 15.000

Necessidade de compactar dados

Novo total são 86.500 bits

Representa uma economia de 42 % de espaço de armazenamento utilizando bits variáveis

Ganhe-se em economia mas aumenta-se a compexidade no uso

Como saber quando a sequencia de bits de um caracter termina e quando outro comeca

Com sequencia fixa seria só contar de n em n bits

Algoritmo de Huffman auxilia justamente nesse ponto propondo que uma arvore binaria auxiliar na construcao da tabela e identificacao dos bits

Codificação de Huffman

No algoritmo, forma-se uma árvore binária com arestas rotuladas

0 para o filho da esq uerda

1 para o filho da direita

Cada símbolo si está associado a uma folha da árvore

O código de si é igual à seqüência dos rótulos das arestas, desde a raiz até a folha

Codificação de Huffman - Exemplo

Suponha que um certa cadeia de caracteres S={s1, s2, ..., sn}

Seja a seqüência de caracteres

s4s3s3s1s3s1s4s5s1s3s3s3s3s3s2s3s5s2s2s2s4

E baseado na tabelaDúvidas:

Como montar a tabela?

Como ficaria minha árvore de Huffman?

Símbolo Código

S1 101

S2 111

S3 0

S4 110

S5 100

Codificação de Huffman - Exemplo

A seqüência dos 4 primeiros caracteres (S4 S3 S3 S1) da cadeia anterior ficaria:

11000101S4 S3S3 S1

Símbolo Código

S1 101

S2 111

S3 0

S4 110

S5 100S5 S2S4S1

0 1 0 1

10

1

S3

0

Codificação de Huffman

O objetivo então é construir uma árvore com custo mínimo, ou seja, a árvore mínima ou árvore de Huffman

Para construir:

Conte a quantidade de vezes que cada item aparece na seqüência

Some os dois itens com menores valores e adicione à árvore resultante

Itens com menor valor ficam à esquerda; os maiores à direita;

Proceda até que todos os itens tenham sido colocados na árvore

Árvores de Huffman - Construção

Na seqüência apresentada:

s4s3s3s1s3s1s4s5s1s3s3s3s3s3s2s3s5s2s2s2s4

Símbolo Frequencia

S1 3

S2 4

S3 9

S4 3

S5 2

S1 S2 S3 S4 S5

Árvores de Huffman - Construção

S5

S2 S3 S4

S1

50 1

S5 S2

S3

S4S1

5 70 1 0 1

Símbolo Frequencia

S1 3

S2 4

S3 9

S4 3

S5 2

Árvores de Huffman - Construção

S5 S2

S3

S4S1

5 70 1 0 1

1210

S5 S2

21

S4S1

5 70 1 0 1

1210

1

S3

0

Símbolo Frequencia

S1 3

S2 4

S3 9

S4 3

S5 2

Árvores de Huffman - Construção

Percorrendo a árvore de Huffman a tabela seria montada

Símbolo Código

S1 101

S2 111

S3 0

S4 110

S5 100

Compressão com Perda de Dados

Compressão com Perda de Dados

Definido como operação que admite alguma perda de qualidade dos dados

A informação é comprimida por algum algoritmo e, ao descomprimir, a informação é diferente da original, mas suficientemente parecida para que seja útil

Exemplo típico: a maioria das imagens .jpg na internet em que se percebe uma diminuição da qualidade próximo às bordas ou trocas de cor na imagem

Compressão com Perda de Dados

Dependendo do algoritmo aplicado, essa compressão sofre de perda constante

Perdem-se dados sucessivamente, à medida em que se aplica o algoritmo várias vezes, ao comprimir e descomprimir. Isso resulta numa maior perda de dados do que a aplicação do algoritmo de uma só vez

Compressão com Perda de Dados

Existem dois esquemas básicos de compressão:

Métodos de Transformação

Métodos Preditivos

Em alguns sistemas, as duas técnicas são combinadas.

Métodos de Transformação

Amostras de figuras ou sons são transformados em pequenos segmentos

Esses pequenos segmentos são transformados em um novo espaço base, e quantizado (limitação de possíveis valores)

Os valores quantizados são codificados para entropia

Métodos Preditivos

Informações decodificadas são usadas para prever qual será o próximo pacote, ex., próximo frame de imagem;

O erro entre o dado previsto e o dado real, junto com qualquer informação extra necessária para reproduzir a previsão, são quantizados e codificados;

Comparação entre os Métodos com e sem Perda de

Dados

Compressão com Perda de Dados

A compressão com perda consegue uma dimensão menor em disco

Possui, porém, uma qualidade mínima com relação ao original

Mais comumente usada em sons, vídeos e imagens, principalmente na troca de informações pela internet

Vídeos podem ser comprimidos numa razão de 300:1, perdas imperceptíveis ao ouvido humano;

Sons e imagens são comprimidos numa razão 10:1, mas imagem tem a qualidade afetada

Exemplo de Compressão com Perda

Imagem Original (12KB)

Imagem Comprimida (85% menos

informação, 1.8KB)

Mesma Imagem Altamente Comprimida (96% menos

informação, 0.56KB)