Tecnologias da Comunicação
Humana
Transmission and Storage
13340, Hugo Costa
14676, Luís Aguilar
14119, Fernando Cunha
Transmission and Storage
• Neste domínio é fundamental falar de compressão de
dados.
• E também é importante falar de índices.
Porquê da Compressão?
• Economia de espaço
• Economia de rede
• Velocidade de acesso
• Processamento eficiente
Código de Huffman
• Método de compressão muito usado e fiável
• Maneira de funcionamento muito simples, consiste em
criar árvores binárias.
• Método usado pelo Winzip.
Algoritmo Huffman
• Monta uma tabela de frequências da ocorrência de cada
caracter.
• Cada caracter é representado por um conjunto de bits.
• Somar os índices com menor frequência, repetidamente até
termos só uma árvore binária.
Algoritmo Huffman
• Considerando:
• Somar os índices com menor frequência
Algoritmo Huffman
• Continuando a somar e colocando os índices com menor
frequência no nodo esquerdo
Algoritmo Huffman
• Finalmente a árvore:
Codificação dos Símbolos
Símbolo
a
" "
c
l
t
s
e
j
Código
0
10
1100
1101
1110
11110
111110
111111
• Estes códigos são utilizados na descodificação
Considerar nodo esquerdo 0 e nodo direito 1.
Objectivo Huffman
• Codificar os símbolos mais frequentes com o menor
número de bits.
• Permite diminuir drasticamente o tamanho dos ficheiros.
Exercício
• Ponham-se atentos que sai na frequência
Porquê dos Índices?
• Aumento da performance de pesquisas.
• Diminuição do tempo de resposta.
• Resumindo eficiência.
Tipos Índices
• Índice Invertido
• Suffix Array
• Suffix Tree
Índices Invertidos
• O indíce invertido é a estrutura básica por trás de qualquer
algoritmo de IR.
• Qualquer forma de melhorar a eficiência do uso do II
melhora também a performance global do sistema de IR.
• Nalguns casos, conseguimos reduzir um índice para 10 %
do seu tamanho original.
• Os indíces invertidos tornam-se necessários para se
encontrar eficazmente os termos de um conjunto de
documentos.
• Uma lista de palavras, cada uma das quais aponta para uma
lista de ocorrências em documentos.
Índices Invertidos
pal1
Doc 1
Doc 6
Doc 16
pal2 ...
...
...
...
paln
...
...
...
Índices Invertidos
• Com um média de 6 letras por termo, um contador de
documentos de 4 bytes e um apontador de 4 bytes para o
ínicio da lista de cada termo, são necessários 14 bytes por
termo. Um corpus de 8 milhões de termos ocuparia 128
MB.
• Cabe portanto facilmente em memória.
• Mas quanto maior for o indíce, maior vai ser o espaço de
armazenamento necessário para o guardar.
• O tamanho (espaço de armazenamento) afecta
directamente o tempo de processamento (I/O)
• Então o tamanho do Índice tem de ser reduzido ao máximo
Compressão de Índices
• Usam-se então técnicas de compressão de índices
• Byte Aligned (Fixed Length Index Compression)
• Elias Gamma (Variable Length Index Compression)
• Flat Huffman
Compressão de Índices
Fixed Length Index Compression
•
•
•
•
É o tipo de algoritmo mais simples de todos.
Algoritmo está relacionado com as fronteiras do Byte.
É fácil de implementar
Melhora a performance em runtime, prejudicando um
pouco a taxa de compressão
• Oferece boa compressão (15% do tamanho de um índice
invertido, usando stop words)
Compressão de Índices
Fixed Length Index Compression
• Num índice invertido, as entradas para cada palavra são
armazenadas em ordem descendente
• Então para cada identificador de documento, apenas a
diferença entre o identificador corrente e o identificador que
o precede precisa de ser guardada. Exemplo:
benfica
Doc 5
3
campeão
...
...
Benfica está no
documento 5 e no 8,
por exemplo...
...
...
...
Compressão de Índices
Fixed Length Index Compression
• No caso de não haver ainda nenhum identificador de
documento, guarda-se uma versão comprimida do deste.
• Uma elevada proporção de valores relativamente baixos é
assim garantida.
• Uma vez que as diferenças entre as ocorrências são
relativamente pequenas precisamos de uma quantidade baixa
de bits para guardar essa diferença.
•
Ex: 1 byte  64
2 bytes  16384
3 bytes  4.194.304
4 bytes  2 ^ 30 – 1
63 – 00 111111
180 – 01 000000 10110100
1 – 00 000001
Neste exemplo de Byte Aligned, usa-se os primeiros 2 bits para indicar quantos
bytes vamos usar para guardar a diferença (por isso 2^30 e não 2^32)
Compressão de Índices
Fixed Length Index Compression
• Na melhor das hipóteses, um x até 64 pode ser guardado em
um byte. Se não tivessemos compressão precisariamos de 4
bytes.
• Se tivessemos que guardar 180, 63, 4, 2, 1 precisariamos de
160 bits (20 bytes).
• Com este tipo de compressão precisamos apenas de 48 bits (4
bytes)
180 – 01 000000 10110100
63 – 00 111111
4 – 00 000100
2 – 00 000010
1 – 00 000001
Compressão de Índices
Variable Length Index Compression
• A técnica descrita por Witten, Moffat e Bell também tira
proveito do facto de para a maioria das palavras, as diferenças
entre os ids dos documentos que as contêm ser relativamente
pequena.
• Consegue-se guardar um inteiro x com 2 * ( log2 x) + 1 bits.
• Ex: 14 guarda-se com 2 *( log2 14) +1 = 2*3 + 1 = 7 bits.
• O primeiro ( log2 x) usa-se para guardar uma representação de
base 1 de inteiros usando apenas o dígito 1. Depois um stop bit
de zero. O ( log2 x) seguinte usa-se para representar a
diferença x – 2 ^ ( log2 x) .
Compressão de Índices
Variable Length Index Compression
• Ex.: 14: ( log2 14) = 3. Na representação de base 1 = 111 (três
uns para o 3)
• Acrescentamos um 0 (stop bit).
• 14 – 2^3 = 14 – 8 = 6 em binário 110.
• Então representamos 14 por 1110110
• Para guardarmos o nosso exemplo de há pouco:
180, 63, 4, 2 e 1
usávamos apenas 35 bits.
Outras técnicas para ganhar
eficiência
• Pesquisas demonstram que atrasar o update do índice na
altura da introdução de documentos no corpus melhora
consideravelmente a eficiência sem degradar de forma notória
a eficácia do sistema de IR.
(Frieder, Grossman, Chowdury e Frieder - Efficiency
Considerations for Scalable Information Retrieval Servers)
• Uma vez que os utilizadores de sistemas de IR não toleram
respostas demoradas e a pesquisa em bases de dados
gigantescas requer sempre vastos recursos computacionais, o
processamento em paralelo torna-se inevitável.
Suffix Trees e Suffix Arrays
• Consideram o texto como uma string longa
• Cada posição no texto é considerado como um sufixo de
texto
• Sufixo é a string que vai desde a posição inicial do sufixo
até ao fim do texto
• Cada sufixo é identificado pela sua posição
Suffix Tree
• Uma árvore de sufixos T para uma palavra t=t1...tm é uma
árvore com raiz com exactamente m folhas numeradas 1 a
m
• Cada nó interno da árvore com excepção da raiz tem pelo
menos 2 ramos e cada ramo é rotulado com uma
subpalavra de t
• Se dois ramos partem do mesmo nó de T, então os seus
rótulos diferem pelo menos no primeiro caractere
Suffix Tree – Exercício
1 6 9 11 17 19 24 28
33
40 46 50 55 60
• This is a text. A text has many words. Words are made from letters.
•
•
•
•
•
•
•
text . A text has many words. Words are made from letters.
text has many words. Words are made from letters.
many words. Words are made from letters.
words. Words are made from letters.
Words are made from letters.
made from letters.
letters.
Suffix Trie
Exemplo de Construção
GOOGOL$
1234567
Suffix Tree
Exemplo de Construção
Suffix Tree
• Custo computacional de construção elevado
• Ocupam ainda mais espaço que o próprio texto
• Não são práticas para textos grandes
• Ao contrário dos indices invertidos guarda a sequência das
palavras
• Ideal para querys complicadas
• Pesquisa facilitada
Suffix Tree
Pesquisas
• Pesquisa é feita a partir da raíz da árvore, e percorrendo os
nodos da árvore conforme a query
• Se chegarmos a um ponto onde a query foi satisfeita, então
devolvemos todos os resultados
• Se não por outro lado chegarmos a um ponto onde não
podemos descer mais na árvore e a query não foi satisfeita,
a pesquisa termina
Suffix Tree
Pesquisas
• Query = GO
– Resultdo = GOOGOL$,GOL$
• Query = GOLO
– Resultdo = null
Suffix Array
• Mesmas funcionalidades do suffix trees, mas requerem
muito menos espaço
• Array com ponteiros para os sufixos de texto
• Possibilitam buscas binárias
• Pesquisas são feitas em disco
• Perde-se funcionalidade, mas ganha-se espaço
Suffix Array - Exemplo
1 6 9 11 17 19 24 28
33
40 46 50 55 60
• This is a text. A text has many words. Words are made from letters.
60 50 28 19 11 40 33
Suffix Array
Pesquisa Binária
String = mississippi
i
11
L
ippi
8
5
issippi
Query = isse
2
ississippi
1
mississippi
10
pi
M
9
ppi
7
sippi
sisippi
4
ssippi
6
ssissippi
3
R
Exemplos
• http://www.beluga.ch/code/applets/huffman/
• http://w3.ualg.pt/~hshah/algoritmos/aula17/aula17.htm
Referências
(1) Efficiency Considerations for Scalable Information Retrieval Servers
Ophir Frieder, David A. Grossman, Abdur Chowdhury and Gideon Frieder
em http://jodi.tamu.edu/Articles/v01/i05/Frieder/
(2) On the Mapping of Index Compression Techniques on CSR
Information Retrievall
Sterling Stuart Stein e Nazli Goharian
em http://lingcog.iit.edu/~scubed/paper.pdf
(3)
(4)
http://articulos.conclase.net/compresion/huffman.html
Modern Information Retrieval
Ricardo Baeza-Yates, Berthier Ribeiro-Neto