UNIVERSIDADE FEDERAL DE OURO PRETO PPGCC - Programa de Pós-Graduação em Ciência da Computação Disciplina de Projeto e Análise de Algoritmos Ronan Loschi

UNIVERSIDADE FEDERAL DE OURO PRETO PPGCC - Programa de Pós-Graduação em Ciência da Computação

Disciplina de Projeto e Análise de Algoritmos

Ronan Loschi R. Ferreira

Algoritmos para compressão de URLs no Twitter

Ronan Loschi R. Ferreira Seminário 2011

Orientador: Fabrício Benevenuto

1/28

Departamento de Computação UFOP

14 de julho de 2011



Ronan Loschi R. Ferreira Seminário 2011 2/28

Estrutura:

• Introdução

• Metodologia

• Análise de complexidade

• Experimentos

• Conclusão




Introdução MetodologiaAnálise de complexidadeExperimentosConclusão

Motivação:

Quantidade de informações gerada pelo uso da tecnologia:

• Bancos de dados locais;

• Banco de dados on-line (Cloud Computing)

• Google (2003) . Mais de 3,5 bilhões de páginas em seu BD;

• A Web (bilhões de páginas). Cada bilhão ocupa 10 terabytes de texto corrido;

• Um terabyte . Suficiente para armazenar o texto de um milhão de livros.

• O armazenamento e o acesso a tal quantidade de texto é um grande desafio





Dado um alfabeto C={n(c)} e um PC=ASCII = Conjunto de Dados (texto)

O problema consiste em representar o conjunto de dados originais em menos espaço.

Formulação do problema:

Solução: Compressão de Dados.

Substituir os símbolos do conjunto de dados original por outros que possam ser representados usando um número menor de bits ou bytes.





Justificativa:

• Menos espaço de armazenamento;

• Menos tempo para:

• Ser lido do disco;• Transmitido;• Pesquisado.

• Custo computacional: em 20 anos (Patterson e Hennessy(1995)).

• Tempo de acesso a discos: praticamente constante;

• Velocidade de processamento: aumentou 2 mil vezes.





Considerações:

• Velocidade de compressão e de descompressão.

Exemplo: banco de dados textuais;

• Pesquisar diretamente no texto comprimido, em vez de descomprimir o texto.

Exemplo: Casamento de cadeias.





Objetivos:

Apresentar os métodos de compressão de Huffman (1952);

Apresentar o algoritmo de Huffman;

Analisar a complexidade do algoritmo.





Metodologia:

O método usa as probabilidades de ocorrência dos símbolos para determinar

palavras de código binário, de tamanho variável, para representar cada símbolo.

Huffman binário:

• Caractere;

• Usando palavras.




Huffman binário usando caracteres (1952):

• Considera caracteres como símbolos;

• Usa uma tabela com o cálculo das frequências de ocorrência dos caracteres;

• Razão de compressão de 20 a 90%. Dependendo das características dos dados.


Exemplo:

• Antes da compressão = 100 bytes;• Após a compressão = 30 bytes;

• Razão de compressão = 30%.




• Representa de modo ótimo cada caractere:

• Atribui códigos mais curtos a símbolos com frequências altas;

• Códigos mais longos a símbolos com frequências curtas;

Huffman binário usando caracteres (1952):

• Os códigos são cadeias binárias que representam cada caractere;

• Código único, de tamanho variável, para cada símbolo diferente do texto.






3

Há outros métodos de representar os caracteres, por exemplo, usando um código binário de comprimento fixo.

ASCII 2 = 8 bits ;

O texto abc, possui (35 +18 + 23 )*1000 = 76.000 caracteres ou 228.000 bits.

O texto abc, possui (35 +18 + 23)*1000 = 76.000 caracteres ou 608.000 bits.

Representar o alfabeto C={abc} com 3 bits,:

Uma economia de 62,5%





8 bits = 76.000 caracteres ou 608.000 bits.

3 bits = 76.000 caracteres ou 228.000 bits.

Huffman = 76.000 caracteres ou 135.000 bits.

O texto abc, possui (35 *1+ 23*2 + 18*3)*1000 = 76.000 caracteres ou 135.000 bits.


Huffman binário usando caracteres:






Custo da árvore:

C = alfabeto

c = caracteres do alfabeto

f(c) = frequência do caractere c no alfabeto C;

dt(c)= profundidade de folha ou comprimento da palavra de código em bits.





A construção da árvore de Huffman:

• Utiliza uma abordagem gulosa;

• Um conjunto de n folhas representam os caracteres que formam o vocabulário do arquivo e suas respectivas frequências.

• A cada etapa, de forma gulosa, as duas árvores com frequências menores frequências são combinadas em uma única árvore e a soma de suas frequências é associada ao nó raiz.

• Ao final das n-1 etapas, temos a árvore de codificação ótima para o arquivo em questão;






• Seguindo o método de Huffman, as arestas da esquerda são rotuladas com o bit 0 e as arestas da direita com o bit 1;

• E para ser um código ótimo, a árvore dever estar sempre cheia, ou seja, cada nó que não é uma folha deve ter dois filhos.

• As palavras de código binário são identificados pelos rótulos das arestas que compõem o caminho da raiz até a folha que representa o caractere.





d b c a

9 18 23 35

c a

23 35

d b

9 18

27

d b

9 18

27

c

23

50

A

35

d b

9 18

27

c

23

50

a

35

85

a)

• Alfabeto C={a,b,c,d}

•Frequências f(c) = {a=35, b=18, c=23, d=9}


b)

c)d)

0

0

0

1

1

1





Compressão e Descompressão:

Por exemplo, um arquivo de 4 caracteres abcd obtemos as codificações :

Código fixo (3 bits): 000.001.010.011 com 12 bits;

Código de Huffman: 0.111.10.110 com 9 bits;

O símbolo ( . ) denota a concatenação.

db ca

db ca





O Algoritmo de Huffman:




Huffman usando palavras:

(Moura (1999); Moura, Navarro, Ziviani e Baeza-Yates, 2000; Ziviani, Moura, Navarro e Baeza-Yates, 2000)





Huffman usando palavras:






O Algoritmo de Huffman usando palavras:

Atribuído a Moffat e Katajainen (1995) e descrito em Moffat e Turpin (2002), e em [2];

Calcula os comprimentos dos códigos em vez dos códigos propriamente ditos;

A compressão atingida é a mesma, independentemente dos códigos utilizados;

Além disso é possível gerar a palavra de código binário, de uma palavra, a partir dos comprimentos dos códigos obtidos.

O mesmo é válido para os algoritmos de codificação e decodificação.





O Algoritmo de Huffman usando palavras:

O algoritmo divide-se em três fases distintas: 1- Construção da árvore de Huffman;

2- Calculadas as profundidades dos nós internos da árvore;

3- Calculadas as profundidades dos nós folhas da árvore, a partir da profundidade dos nós internos.

As profundidades dos nós folhas são utilizados para a obtenção do código de Huffman para cada palavra.

Métodos de Huffman baseados em caracteres comprimem o texto para aproximadamente 60%, enquanto métodos de Huffman baseado em palavras comprimem o texto para valores pouco acima de 25%. [2]





Análise de Complexidade:

Fila de prioridades Q = O(lgn)

Inicialização de Q = O(n)

O loop (executado exatamente n-1) = O(nlgn)

Desse modo, o tempo de execução total do algoritmo de Huffman, em um conjunto de n caracteres é O(nlgn). [3]

Algoritmo de Huffman usando caractere:





Análise de Complexidade:

O algoritmo, para o Método de Huffman usando palavras, calcula os comprimentos dos códigos a partir do vetor A contendo as frequências das palavras, em ordem não crescente, a um custo O(n) em tempo e espaço.

Prioridades Q = O(n)

Inicialização de Q = O(n)

Comprimentos dos códigos = O(n) + O(n) = c*O(n)

A árvore de Huffman não é usada na prática!

Algoritmo de Huffman usando palavras:





Experimentos:





Conclusão:

O método de compressão de Huffman é uma boa opção;

Vantagem do Huffman Usando palavras: Melhor taxa de compressão e ordem de complexidade.

A construção da árvore de Huffman é um passo importante para a compreensão das diferentes soluções propostas.

Os experimentos realizados, embora simples, demonstram a utilidade e a vantagem de se comprimir dados com o objetivo de ganhar espaço em disco.

Este trabalho está diretamente relacionado com o tema da dissertação

Contribuição da disciplina de Projeto e Analise de Algoritmos em uma aplicação real.





Trabalhos futuros:

Embora não explorados neste artigo, outros métodos de compressão como os da família de Ziv-Lempel, podem ser pesquisados e implementados.

Implementação do método de Huffman usando palavras;

Experimentos demonstrando a pesquisa direta no texto comprimido e acesso direto a qualquer parte do texto comprimido.





Bibliografia:

[1] Wikipedia, “Compressão de dados,” 2011, http://pt.wikipedia.org/wiki/Algoritmodecompressao, Acesso em 06/06/2011.

[2] N. Ziviani, Projeto de Algoritmos com Implementações em Pascal e C, 3rd ed. Cengage Learning, 2011, iSBN: 978-85-221-1050-6.

[3] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. The MIT Press, 2009, iSBN-13: 978-0-262-53305-8.

[4] D. Antoniades, I. Polakis, G. Kontaxis, E. Athanasopoulos, S. Ioannidis, E. Markatos, and T. Karagiannis, “we.b: The web of short urls,” in Int’l Conference on World Wide Web., 2011, pp. 715–724.

[5] F. Benevenuto, G. Magno, T. Rodrigues, and V. Almeida, “Detecting spammers on twitter,” in Annual Collaboration, Electronic messaging, Anti-Abuse and Spam Conference (CEAS), Redmond, Washington, USA. July, 2010, pp. 1–9.

[6] C. Grier, K. Thomas, V. Paxson, and M. Zhang, “@spam: The underground on 140 characters or less,” in ACM conference on Computer and communications security (CCS), 2010, pp. 27–37.

Documents

UNIVERSIDADE FEDERAL DE OURO PRETO PPGCC - Programa de Pós-Graduação em Ciência da Computação Disciplina de Projeto e Análise de Algoritmos Ronan Loschi