Algorítmos e estrutura de
dados III
Carlos Oberdan Rolim
Ciência da Computaçã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
Técnicas de Compressão sem Perda de
Dados
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.
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:
Caracter
A
Frequencia 52
E
I
O
U
!
8
12 11
7
10
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
Necessidade de compactar dados
Agora vamos supor que os caracteres são representados com uma
sequencia variavel de bits
Caracter
A
E
I
O
U
!
Sequencia variavel
0
110
10
11
101
111
Abaixo está o cálculo do total de bits usado
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
Dúvidas:
E baseado na tabela
Símbolo
Código
S1
101
S2
111
S3
0
S4
110
S5
100
Como montar a
tabela?
Como ficaria
minha árvore de
Huffman?
Codificação de Huffman - Exemplo
Símbolo
Código
S1
101
S2
111
S3
0
S4
110
S5
100
1
0
S3
1
0
0
1
0
S5
S1
S4
A seqüência dos 4 primeiros caracteres (S4 S3 S3 S1) da cadeia anterior ficaria:
11000101
S4 S3 S3 S1
1
S2
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
5
0
S5
S2
S3
S4
5
1
S1
Símbolo
7
0
1
S5
S1
Frequencia
S1
3
S2
4
S3
9
S4
3
S5
2
0
S4
S3
1
S2
Árvores de Huffman - Construção
12
S3
1
0
5
1
0
S5
S1
S4
1
S3
7
0
21
0
12
1
0
1
5
S2
Símbolo
Frequencia
S1
3
S2
4
S3
9
S4
3
S5
2
7
0
1
0
S5
S1
S4
1
S2
Á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)