Universidade Federal de Minas Gerais Departamento de Ciência da Computação Compressão de Textos...

Universidade Federal de Minas GeraisDepartamento de Ciência da Computação

Compressão de TextosCompressão de Textos

Juliano Palmieri Lage

2/28Implementação de Sistemas de Informação para Web

Por que usar compressão?Por que usar compressão?

Economia de espaço

Economia de rede

Velocidade de acesso

Processamento eficiente

3/28Implementação de Sistemas de Informação para Web

Conceitos Básicos...Conceitos Básicos...

Modelagem– Estática– Semi-estática– Adaptativa

Codificação– Dicionário– Estatística

4/28Implementação de Sistemas de Informação para Web

Conceitos BásicosConceitos Básicos

Desempenho dos métodos– Taxa de Compressão

• (1 – n/u) x 100

– Bits por caracter•cn/u

– Razão de compressão• (n/u) x 100

5/28Implementação de Sistemas de Informação para Web

Exemplos de CompressãoExemplos de Compressão

Prefixos de Redundância Mínima– Huffman

Dicionário– LZ77, LZ78

– Gzip, Compress, bzip2

Codificação Aritimética

6/28Implementação de Sistemas de Informação para Web

Huffman com PalavrasHuffman com Palavras

Integração com RI

Modelo Sem-Espaços

Duas passagens pelo texto:

– Coleta de estatísticas

– Codificação

7/28Implementação de Sistemas de Informação para Web

Exemplo...Exemplo...

“Para cada rosa rosa, uma rosa é uma rosa”

Símbolos– {“para”, “cada”, ”rosa”, “,□”,

“uma”, “é”}Freqüências

– 1, 1, 4, 1, 2, 1

8/28Implementação de Sistemas de Informação para Web

Exemplo...Exemplo...

para:1 cada:1 rosa:4 , □:1 uma:2 é:1

para:1 cada:1

20 1

rosa:4 , □:1 uma:2 é:1

9/28Implementação de Sistemas de Informação para Web

Exemplo...Exemplo...

para:1 cada:1

20 1

rosa:4 , □:1 uma:2é:1

20 1

para:1 cada:1

20 1

, □:1 é:1

20 1

4

rosa:4 uma:2

10

10/28Implementação de Sistemas de Informação para Web

Exemplo...Exemplo...

para:1 cada:1

20 1

, □:1 é:1

20 1

4

rosa:4

uma:2

6

0

0 1

1

11/28Implementação de Sistemas de Informação para Web

ExemploExemplo

para:1 cada:1

20 1

, □:1 é:1

20 1

4

rosa:4

uma:2

6

0

0 1

1

0 1

10

12/28Implementação de Sistemas de Informação para Web

Codificação de HuffmanCodificação de Huffman

Árvore Canônica

Abordagem da árvore

– Trivial

– Ineficiente

Comprimento dos códigos

13/28Implementação de Sistemas de Informação para Web

Algoritmo Eficiente...Algoritmo Eficiente...

Recebe como entrada um vetor

A com as freqüências ordenadas

(não-crescente).

Saída vetor com comprimento

dos códigos (1, 2, 4, 4, 4, 4)

14/28Implementação de Sistemas de Informação para Web

Algoritmo EficienteAlgoritmo Eficiente

Manipulação de vários vetores

logicamente distintos in situ

Divide-se em 3 fases:

– Combinação dos nós

– Profundidade dos nós internos

– Comprimento dos códigos

15/28Implementação de Sistemas de Informação para Web

Primeira Fase...Primeira Fase...

Direita para esquerdaFreqüência é mantida até nó ser

processadoNão precisa de apontador para

pais de nós folha– (0,1,2,3,3) -> (1,2,4,4,4,4)

16/28Implementação de Sistemas de Informação para Web

Primeira fase...Primeira fase...

void calculoHuffman(A, n) { r = n; s = n; for (t = n; t >= 2; t--){ /* Procura posicao */ if (s < 1 || (r > t && A[r] < A[s])){/* No interno */ A[t] = A[r]; A[r] = t; r--; } else { /* No-folha */ A[t] = A[s]; s--; } /* Atualiza Frequencias */ if (s < 1 || (r > t && A[r] < A[s])){ A[t] += A[r]; A[r] = t; r--; } else { A[t] += A[s]; s--; } }

17/28Implementação de Sistemas de Informação para Web

Segunda fase...Segunda fase...

Esquerda para direitaProfundidade dos nós internos

– Raiz = 0– Filhos = Pai+1

18/28Implementação de Sistemas de Informação para Web

Segunda FaseSegunda Fase

{...}A[2] = 0; for (t = 3; t <= n; t++) A[t] = A[A[t]] + 1;

{...}

19/28Implementação de Sistemas de Informação para Web

Terceira Fase...Terceira Fase...

Esquerda pra direitad indica nós disponíveis no nível

h u indica nós utilizados no nível h

20/28Implementação de Sistemas de Informação para Web

Terceira FaseTerceira Fase

d = 1; u = 0; h = 0; r = 2; t = 1; while (d > 0){ while (r <= n && A[r] == d) { u++; r++; } while (d > u) { A[t] = h; t++; d--; } d = 2 * u; h++; u = 0; }

21/28Implementação de Sistemas de Informação para Web

Códigos Canônicos...Códigos Canônicos...

Comprimentos dados pelo algoritmo de Huffman

Códigos de um mesmo comprimento são inteiros consecutivos

22/28Implementação de Sistemas de Informação para Web

Códigos CanônicosCódigos Canônicos

Compressão baseada em duas tabelas de tamanho L

Base: primeiro código do nível

Offset: índice da primeira palavra do nível

23/28Implementação de Sistemas de Informação para Web

CodificaçãoCodificação

Recebe o índice da palavra como parâmetro

Exemplo: 4 (“cada”)

codifica(int i){ l = 1; while (i >= offset[l+1]) l++; codigo = i - offset[l] + base[l]; Escreve(codigo, l);}

24/28Implementação de Sistemas de Informação para Web

DecodificaçãoDecodificação

Retorna o índice da palavra

Exemplo: 1100 (“para”)

int decodifica(){ l = 1; codigo = leBit(entrada); while ((codigo << 1) >= base[l+1]){ codigo <<=1; codigo += leBit(entrada); l++; } return codigo - base[l] + offset[l];}

25/28Implementação de Sistemas de Informação para Web

Huffman com Huffman com BytesBytes

Huffman Pleno– 0x70 0x71 0x4f | 0x71 0x4f

Huffman Sincronizado– 0xf0 0x71 0x4f | 0xf1 0x4f

26/28Implementação de Sistemas de Informação para Web

Pesquisa em Texto Pesquisa em Texto ComprimidoComprimido Casamento exato:

– Busca no vocabulário– Procura direta com padrão comprimido

Casamento aproximado:– Busca aproximada no vocabulário– Marca-se palavras encontradas– Percorre-se o arquivo comprimido e

analisa se chegou em uma palavra marcada

27/28Implementação de Sistemas de Informação para Web

Casamento AproximadoCasamento Aproximado

Máscara de bitsAutômato não-determinista

uma ro* rosa

28/28Implementação de Sistemas de Informação para Web

Dúvidas?Dúvidas?Dúvidas?Dúvidas?