Strings
(Compressão)
Estrutura de Dados II
Jairo Francisco de Souza
Compressão de Dados
• Objetivos
– Reduzir espaço de armazenagem
– Reduzir tempo de transmissão
• Muito importante
– Informação (e dados) tende a crescer de forma exponencial
• Exemplos:
– Compressão de arquivos em geral
• ZIP, GZIP, BZIP, BOA.
– Sistemas de arquivos: NTFS.
– Multimedia.
• Imagens: GIF, JPEG
• Som: MP3.
• Vídeo: MPEG, DivX™, HDTV.
– Comunicação
• Modems
• Faxes
Compressão x Compactação
• Compressão
– Mudança na representação de algum dado para
reduzir seu tamanho
• Compactação
– União de dados que não estão unidos
• Exemplo:
– Compressão do HD: reduzir o tamanho dos arquivos
– Compactação do HD: juntar partes disjuntas
(desfragmentar)
Sistemas de recuperação de
informação
• Métodos recentes de compressão têm
permitido:
– 1. Pesquisar diretamente o texto comprimido
mais rapidamente do que o texto original.
– 2. Obter maior compressão em relação a
métodos tradicionais, gerando maior
economia de espaço.
– 3. Acessar diretamente qualquer parte do
texto comprimido sem necessidade de
descomprimir todo o texto desde o início
Codificação e Decodificação
• Seja M a mensagem que desejamos armazenar/transmitir
– Codificação: Gerar uma representação “comprimida” C(M) que,
espera-se, utilize menos bits
– Decodificação: Reconstrução da mensagem original ou alguma
aproximação M’
• Razão de Compressão: bits de C(M) / bits de M
• Compressão sem perda: M = M’
– Texto, programas fonte, executáveis etc
– RC: 50-75% ou menos
• Compressão com perda: M ~ M’
– Imagens, som, vídeo
– Uma idéia é descartar informação não perceptível pelos sentidos
– RC: 10% ou mais, dependendo do fator de qualidade
Codificação por Seqüências
Repetidas
• Conhecida como Run-length encoding (RLE).
• Idéia é explorar longas seqüências de caracteres repetidos
– Substituir seqüência pelo número de repetições seguido do caractere
repetido
– Se seqüência tem menos de 3 caracteres, ignorar regra
• Exemplo:
– AAAABBBAABBBBBCCCCCCCCDABCBAAABBBBCCCD
→ 4A3BAA5B8CDABCB3A4B3CD
• Como representar o número de repetições?
– Alguns esquemas + ou – complicados
– Pode levar à inflação de um arquivo se as seqüências são curtas
• Se o arquivo é binário, saída consiste apenas de contagens de
repetições
– Por exemplo, tente comprimir a cadeia 10001110011111001101
• Aplicações
– Imagens preto e branco
• Compressão aumenta com a resolução
• Usado nos arquivos .rle do Windows 3.x, que eram bitmaps usadas na tela de
inicialização do sistema operacional.
Codificação de Huffman
• Idéia é usar caracteres (símbolos) com número variável de bits
– Caracteres mais comuns na mensagem são codificados com menos bits
e caracteres menos comuns com mais
• Árvore de Prefixos de Huffman
– Dada uma mensagem, encontra a melhor (menor) codificação para os
caracteres
– Algoritmo:
• Tabular freqüências dos símbolos
• Montar uma floresta de tries unitários com todos os
símbolos e suas freqüências
• Repetir
– Localizar os dois tries com menor freqüência Fi e Fj
– Uní-los num trie único com freqüência Fi + Fj
Exemplo de Codificação de
Huffman
Char Freq
• Freqüências dos
caracteres
• Árvore de Huffman
é um heap
– Pode implementar
utilizando um array,
assim como é feito no
HeapSort
E
125
T
93
A
80
O
76
I
72
N
71
S
65
R
61
H
55
L
41
D
40
C
31
U
27
Exemplo de Codificação de
Huffman
A
O
T
E
80
76
93
125
D
L
R
S
N
I
H
40
41
61
65
71
73
55
C
U
31
27
Exemplo de Codificação de
Huffman
A
O
T
E
80
76
93
125
D
L
R
S
N
I
40
41
61
65
71
73
H
58
55
C
U
31
27
Exemplo de Codificação de
Huffman
A
O
80
76
81
T
E
93
125
D
L
R
S
N
I
40
41
61
65
71
73
H
58
55
C
U
31
27
Exemplo de Codificação de
Huffman
A
O
80
76
81
T
E
93
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de
Huffman
A
O
80
76
T
E
93
81
126
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de
Huffman
A
O
80
76
T
E
93
81
126
144
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de
Huffman
156
A
O
80
76
T
E
93
81
126
144
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de
Huffman
156
174
A
O
80
76
T
E
93
81
126
144
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de
Huffman
156
174
A
O
80
76
238
T
E
93
81
126
144
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de
Huffman
156
270
174
A
O
80
76
238
T
E
93
81
126
144
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de
Huffman
330
156
270
174
A
O
80
76
238
T
E
93
81
126
144
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de
Huffman
330
508
156
270
174
A
O
80
76
238
T
E
93
81
126
144
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de
Huffman
838
330
508
156
270
174
A
O
80
76
238
T
E
93
81
126
144
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de
HuffmanChar Freq Fixo Huff
E
125
0000
110
T
93
0001
000
A
80
0010
000
O
76
0011
011
I
73
0100
1011
N
71
0101
1010
S
65
0110
1001
R
61
0111
1000
H
55
1000
1111
L
41
1001
0101
D
40
1010
0100
C
31
1011
11100
U
27
1100
11101
Total
838
4.00
3.62
Codificação de Huffman
• Implementação.
– Dois passos
• Tabular freqüências e construir o trie
• Codificar mensagem percorrendo o trie
– Usar uma fila de prioridades (heap)
• Complexidade O(M + N log N)
– M é o comprimento da mensagem
– N é o número de caracteres distintos
• Dificuldades
– Transmissão do trie
• Pode ser resolvido com variante progressiva (Knuth): Trie é
construído simultaneamente pelo codificador e decodificador
Codificação de Huffman
• Em algumas aplicações, como sistemas de
recuperação de informação, o uso de
palavras ao invés de caracteres torna-se
importante
• Métodos de Huffman baseados em
caracteres comprimem o texto para
aproximadamente 60%.
• Métodos de Huffman baseados em palavras
comprimem o texto para valores pouco acima
de 25%.
Codificação de Huffman
• Exemplo:
– “Para cada rosa rosa, uma rosa é uma rosa”
• Divisão do texto:
– Separadores são caracteres que aparecem entre palavras: espaço,
vírgula, ponto, ponto e vírgula, interrogação, e assim por diante.
– Uma forma eficiente de lidar com palavras e separadores é
representar o espaço simples de forma implícita no texto
comprimido.
– Nesse modelo, se uma palavra é seguida de um espaço, então,
somente a palavra é codificada.
– Senão, a palavra e o separador são codificados separadamente.
– No momento da decodificação, supõe-se que um espaço simples
segue cada palavra, a não ser que o próximo símbolo corresponda a
um separador.
Exercício
• Codifique o texto abaixo usando a
codificação de Huffman
– yabba dabba doo
• Decodifique o texto abaixo, utilizando a
árvore fornecida:
– 001101101100110001011
Codificação de Huffman
• Problemas
– Como inserir novos símbolos na árvore?
– E se não soubermos a frequência dos
símbolos previamente?
Huffman adaptativo
• A árvore é construída durante a compressão/descompressão (não
necessita de ser enviada previamente)
• Não necessita de conhecer a estatística da fonte a priori
• Se a estatística variar, o código adapta-se automaticamente
• Algoritmo
– Reservar um símbolo de “escape” na árvore para representar os símbolos
que ainda não ocorreram
– Atualizar os pesos de todos os nós da árvore com o respectivo número de
ocorrências (permite obter a estatística da fonte)
– Atualizar a árvore de forma a que todos os nós tenham pesos ordenados
da esquerda para a direita e de baixo para cima
Huffman adaptativo
• O algoritmo foi desenvolvido
independentemente por Faller (1973) e
Gallager (1978) e melhorado por Knuth
(1985), ficando conhecido como algoritmo
FGK.
• Existe ainda outro melhoramento feito por
Vitter (1987), conhecido como algoritmo V,
que não é apresentado aqui.
• O Huffman adaptativo é usado no comando
compact do UNIX
Huffman adaptativo
•
A idéia do FGK é baseada na seguinte
propriedade de irmandade:
– se cada nó tem um irmão (exceto a raiz) e o
cruzamento de árvore extensão-primeiro
direita-para-a-esquerda gera uma lista de nós
com contadores de frequência não
crescentes, pode-se provar que uma árvore
com a propriedade de irmandade é uma
árvore de Huffman.
•
Assim, na codificação adaptativa, verificamos se a
propriedade de irmandade está sendo violada. Em
caso positivo, deve-se reestruturar a árvore para
restabelecer essa propriedade.
– A restruturação da árvore parece complexa,
mas basta fazer a troca entre os nós
adjacentes do cruzamento de árvore
extensão-primeiro direita-para-a-esquerda.
Exemplo: “ABRACADABRA”
Exemplo: “ABRACADABRA”
Huffman adaptativo
Código gerado para “ABRACADABRA”:
“A 0 B 00 R 0 100 C 0 1100 D 0 110 110 0”
●
●
●
Para entender o código, é preciso verificar o passo a
passo da construção da árvore.
Cada letra significa uma inserção na árvore.
Os bits que antecedem a letra indicam a posição do nó
de escape.
●
●
Sempre que for enviada uma letra não pertencente à árvore,
retorna-se os bits correspondente ao nó de escape e, em
seguida, a letra a ser enviada.
Ao decodificar, a árvore final deverá ser idêntica à
árvore criada ao codificar!
Exercício
• Ex1: Codifique a sequência
ALOHAMAHALO com Huffman Adaptativo
• Ex2: Decodifique a sequência
M0A00H11100L1100O111011101101111
Algoritmo Lempel-Ziv
• Desenvolvido por Abraham Lempel e
Jacob Ziv em 1977.
– Chamado de LZ77
• Usado no programa PKZIP, GZIP, nos
arquivos de formato ZIP e no formato de
imagens PNG
• Não necessita conhecer os símbolos a
priori
36
Algoritmo LZ77
• Baseado em duas janelas contíguas de
tamanho fixo: dicionário e buffer
• A posição das janelas vão sendo
deslocadas à medidas que os símbolos
vão sendo codificados.
37
Algoritmo LZ77: Codificador
• Inicializa-se o buffer (de dimensão Nb) com os primeiros
Nb símbolos da sequência a codificar
• Inicialmente o dicionário não contém nenhum símbolo
• Enquanto houver símbolos a codificar
– Identificar no dicionário a maior sequência de símbolos que
também esteja presente no buffer (a começar no cursor)
– Associar à sequência o código (p, l, c) onde
• p é a posição relativa (a contar do cursor) da maior sequência do
dicionário
• l é o comprimento da maior sequência
• c é o símbolo do buffer que se segue à sequência
– Deslocar as janelas (dicionário + buffer) de l+1 símbolos
38
Questões de implementação
• Caso 1
– Quanto não existe nenhuma sequência no
dicionário que corresponda às sequências do
buffer (a começar do cursor), então o código
para esses casos é (0, 0, c), onde c é o
primeiro símbolo do buffer
39
Questões de implementação
• Caso 2
– É vantajoso poder codificar certas sequências com
p < l. Por exemplo, considere a seguinte situação
– Neste caso, o código será (2, 5, a), o que significa:
• Recua 2 símbolos no dicionário, copia os 5 símbolos que
se seguem, e acrescenta um “a” no final.
– Visto que para p = 2 só sobram 2 símbolos no
dicionário (o “e” e o “t”), o que se faz é uma cópia
circular: recomeça-se a copiar os símbolos a partir
da posição p quando se atinge o fim do dicionário. 40
Exemplo - LZ77
• Sequência a codificar: bananabanabofana
– Nd = 6 (comprimento do dicionário).
– Nb = 4 (comprimento do buffer).
–
–
–
–
–
– (0,0,b),(0,0,a),(0,0,n)...
41
Exemplo - LZ77
• Sequência a codificar: bananabanabofana
–
–
–
–
–
–
–
– (0,0,b),(0,0,a),(0,0,n),(2,3,b),(4,4,o),(0,0,f),
(6,3,Null)
42
LZ77 - Decodificador
• Exemplo:
(0, 0, p) (0, 0, a) (2, 2, i) (4, 5, b) (0, 0, o) (0, 0, f) (6, 3, s)
43
Exercício
• Codifique a seguinte cadeia com LZ77,
considerando buffer de tamanho 4 e dicionário de
tamanho 6
– ATGTCGTCATGTCATGCTAGCTATGTGTCATGTATG
• Decodifique o código abaixo
– (0, 0, a), (0, 0, b), (0, 0, c), (3, 1, c), (4, 10, b),
(1, 3, a), (1, 1, Null)
44
Algoritmo LZ78
• Difere na forma com que é gerido e atualizado o dicionário
• Ao invés de uma janela deslizante, o dicionário é uma tabela de
sequências que já foram analisadas no processo de codificação.
• Não há limite de entradas no dicionário
– Assim, é possível que uma sequência encontre uma ocorrência na tabela,
mesmo que esta tenha acontecido muito atrás no processo de subdivisão
• O algoritmo codifica novas sequências com apenas (1) um número
correspondente à entrada do dicionário que contém a sequência
com todos os símbolos, à exceção do último da nova sequência, e
(2) um caractere
45
Algoritmo LZ78 - Codificador
• Dicionário = null
• String = null
• Enquanto houver símbolos para codificar
– c = próximo símbolo
– Se String+c é uma sequência presente no dicionário
• String = String + c
– Caso contrário
• Enviar código (índice de String no Dicionário, c)
• Atualizar Dicionário com String + c
• String = null
46
Exemplo - LZ78
• Sequência a codificar: bananabanabofana
47
48
LZ78 - Decodificador
• Exemplo:
(0, p), (0, a), (1, a), (0, i), (2, p), (2, i), (2, b), (0, o), (0, f), (6, a)
49
LZ78 - Decodificador
• Exemplo:
(0, p), (0, a), (1, a), (0, i), (2, p), (2, i), (2, b), (0, o), (0, f), (6, a)
50
Exercício
• Codifique a seguinte cadeia com LZ78
– ATGTCGTCATGTCATGCTAGCTATGTGTCA
TGTATG
• Decodifique o código abaixo com LZ78
– (0, a)(0,b)(0,r)(1,c)(1,d)(1,b)(4,a)(2,r)(1,null)
51
Algoritmo LZW
• Modificação do LZ78 desenvolvido e patenteado por
Terry Welch em 1984
• É geralmente utilizado em imagens nas quais não se
quer perder a definição original.
• O codificador LZW reduz, pela compressão, os
arquivos de imagens gráficas a 1/3 ou 1/4 de seu
tamanho original.
• Usado nos formatos TIFF (opcional) e GIF (padrão)
• O algoritmo exclui o símbolo da palavra de código
52
Algoritmo LZW - Codificador
• Dicionário = todos os símbolos da fonte (por
exemplo, a tabela ASCII)
• String = 1o símbolo da sequência a codificar
• Enquanto houver símbolos para codificar
– c = próximo símbolo
– Se String+c é uma sequência presente no Dicionário
• String = String + c
– Caso contrário
• Enviar código (índice de String no Dicionário)
• Atualizar Dicionário com String+c
• String = c
– Enviar código (índice de String no Dicionário)
53
Exemplo - ZVW
• Sequência a codificar: bananabanabofana
• Dicionário inicializado com a tabela ASCII
estendida (de 0 a 255)
• String inicializada com o 1o caracter da
sequência
54
55
Algoritmo LZW - Decodificador
• Dicionário = todos os símbolos da fonte (por exemplo, a
tabela ASCII)
• Stringold = 1o símbolo da sequência a codificar
• Saída = Stringold
• Enquanto houver códigos para decodificar
– Lê novo código
– Stringnew = sequência correspondente a novo código
– Saída = Stringnew
– c = 1o símbolo de Stringnew
– Adicionar Stringold + c a Dicionário
– Stringold = Stringnew
56
Algoritmo LZW - Decodificador
• Exemplo:
(112), (97), (256), (105), (257), (97), (259), (98), (111), (102), (261), (97)
Dicionário inicializado com a tabela ASCII
57
Exercício
• Codifique a seguinte string com LZW
– ATGTCGTCATGTCATGCTAGCTATGTGTCA
TGTATG
• Decodifique o código abaixo com LZW,
considerando A = 65 e o dicionario com
ultimo termo igual a Z = 90
– 65 66 82 65 67 65 68 95 97
58