58
Strings (Compressão) Estrutura de Dados II Jairo Francisco de Souza

Strings (Compressão) - ufjf.br£o.pdf · •Tabular freqüências dos símbolos •Montar uma floresta de tries unitários com todos os símbolos e suas freqüências •Repetir

  • Upload
    vominh

  • View
    235

  • Download
    0

Embed Size (px)

Citation preview

Strings(Compressão)

Estrutura de Dados IIJairo 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

• Freqüências dos caracteres

• Árvore de Huffman é um heap– Pode implementar

utilizando um array, assim como é feito no HeapSort

125

Freq

93

80

76

72

71

61

55

41

40

E

Char

T

A

O

I

N

R

H

L

D

31

27

C

U

65S

Exemplo de Codificação de Huffman

R S N I

E

H

C U

31 27

5571 7361 65

125

40

T

D L

41

93

A O

80 76

Exemplo de Codificação de Huffman

R S N I

E

H

C U

58

D L

A O T

31 27

5571 7361 65

125

40 41

9380 76

Exemplo de Codificação de Huffman

R S N I

E

H

C U

58

D L

81

A O T

31 27

5571 7361 65

125

40 41

9380 76

Exemplo de Codificação de Huffman

R S N I

E

H

C U

58

113

D L

81

A O T

31 27

5571 7361 65

125

40 41

9380 76

Exemplo de Codificação de Huffman

R S N I

E

H

C U

58

113126

D L

81

A O T

31 27

5571 7361 65

125

40 41

9380 76

Exemplo de Codificação de Huffman

R S N I

E

H

C U

58

113144126

D L

81

A O T

31 27

5571 7361 65

125

40 41

9380 76

Exemplo de Codificação de Huffman

R S N I

E

H

C U

58

113144126

D L

81

156

A O T

31 27

5571 7361 65

125

40 41

9380 76

Exemplo de Codificação de Huffman

R S N I

E

H

C U

58

113144126

D L

81

156 174

A O T

31 27

5571 7361 65

125

40 41

9380 76

Exemplo de Codificação de Huffman

R S N I

E

H

C U

58

113144126

238

T

D L

81

156 174

A O

58

11314412681

31 27

5571 7361 65

125

40 41

9380 76

Exemplo de Codificação de Huffman

R S N I

E

H

C U

58

113144126

238270

T

D L

81

156 174

A O

31 27

5571 7361 65

125

40 41

9380 76

Exemplo de Codificação de Huffman

R S N I

E

H

C U

58

113144126

238270

330

T

D L

81

156 174

A O

31 27

5571 7361 65

125

40 41

9380 76

Exemplo de Codificação de Huffman

R S N I

E

H

C U

58

113144126

238270

330 508

T

D L

81

156 174

A O

31 27

5571 7361 65

125

40 41

9380 76

Exemplo de Codificação de Huffman

R S N I

E

H

C U

58

113144126

238270

330 508

838

T

D L

81

156 174

A O

31 27

5571 7361 65

125

40 41

9380 76

Exemplo de Codificação de Huffman

125

Freq

93

80

76

73

71

61

55

41

40

E

Char

T

A

O

I

N

R

H

L

D

31

27

C

U

65S

0000

Fixo

0001

0010

0011

0100

0101

0111

1000

1001

1010

1011

1100

0110

110

Huff

000

000

011

1011

1010

1000

1111

0101

0100

11100

11101

1001

838Total 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

36

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

37

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.

38

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

39

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

40

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.

41

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)...

42

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)

43

LZ77 - Decodificador• Exemplo:

(0, 0, p) (0, 0, a) (2, 2, i) (4, 5, b) (0, 0, o) (0, 0, f) (6, 3, s)

44

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)

45

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

46

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

47

Exemplo - LZ78

• Sequência a codificar: bananabanabofana

48

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

LZ78 - Decodificador

• Exemplo: (0, p), (0, a), (1, a), (0, i), (2, p), (2, i), (2, b), (0, o), (0, f), (6, a)

51

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)

52

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

53

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)

54

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

55

56

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

57

Algoritmo LZW - Decodificador• Exemplo:

(112), (97), (256), (105), (257), (97), (259), (98), (111), (102), (261), (97)

Dicionário inicializado com a tabela ASCII

58

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