UNIVERSIDADE FEDERAL DE ALAGOAS
DEPARTAMENTO DE TECNOLOGIA DA INFORMAÇÃO
CIÊNCIA DA COMPUTAÇÃO
Arquivos Invertidos
André Ferreira da Silva
Jimy Marques Madeiro
Talita Perciano Costa Leite
1
Roteiro
•
•
•
O que é a estrutura
Como funciona
Operações em arquivos invertidos de Registros de
Dados
– Modificando os dados
– Atualizando
• Arquivos Invertidos para busca em documentos
– Busca em documentos texto
• Granularidade do Índice de um Arquivo Invertido
• Construção de índices
– Matriz de freqüência
– Inversão em memória
– Inversão baseada em ordenação
2
O que é a estrutura
• Organização ou estrutura de arquivo que
•
•
permite uma procura rápida por consultas em
geral envolvendo valores de chaves secundárias
especificados
Os valores das chaves secundárias são usados
como uma base para localizar uma classe de
registro de dados
Possui duas partes principais:
– Estrutura de busca
– Lista invertida
3
O que é a estrutura
• O tipo mais comum de arquivo invertido tem um nível-duplo de
indexação e lista de acesso associada
Índice de nível 1
(tipos de atributos)
Índice de nível 2
(valores de item)
Nível 3
(listas de acesso)
Nível 4
(registros de dados)
Atlanta
AGE
CITY
EMP-ADDR
Atlanta
...
Atlanta
Chicago
Chicago
Detroit
Chicago
Houston
Atlanta
Chicago
Chicago
4
O que é a estrutura
• Arquivos completamente invertidos
– É invertido sobre todos os tipos itens chave no
registro
– Estabelecem acesso rápido para base de dados
– Grande espaço de armazenamento na indexação
• Arquivo parcialmente invertido
– É invertido sobre um número selecionado de tipos de
itens chave
5
Como funciona
• Arquivos invertidos são tradicionalmente
•
utilizados para a implementação de índices
lexicográficos (Harman et al. 1992)
Busca por frases:
– Índice invertido contém para cada palavra:
• Um apontador para cada um dos documentos dos quais a
palavra ocorre
• As posições da palavra nesse documento
– Busca torna-se mais eficiente nesse tipo de índice
– A dimensão do próprio índice é um problema
– Índice precisa ser atualizado a cada modificação do
documento original
6
Como funciona
• A pesquisa é feita da seguinte forma:
– O primeiro termo é pesquisado
– Como resultado tem-se uma lista temporária de
documentos e posições contendo o termo pesquisado
– Utiliza-se a lista temporária para pesquisar o próximo
termo
– Repete-se a pesquisa para os próximos termos até
que o último tenha sido pesquisado, ou até que a lista
esteja vazia
• É desejável que os termos menos comuns sejam
pesquisados inicialmente.
7
Modificando os dados
Índice de nível 1
(tipos de atributos)
Índice de nível 2
(valores de item)
Nível 3
(listas de acesso)
Nível 4
(registros de dados)
Atlanta
AGE
CITY
EMP-ADDR
Atlanta
...
Atlanta
Chicago
Chicago
Detroit
Chicago
Houston
Atlanta
Chicago
Chicago
8
Modificando os dados
Índice de nível 1
(tipos de atributos)
Índice de nível 2
(valores de item)
Nível 3
(listas de acesso)
Nível 4
(registros de dados)
Atlanta
AGE
CITY
EMP-ADDR
Atlanta
...
Atlanta
Chicago
Chicago
Detroit
Chicago
Houston
Atlanta
Chicago
Chicago
9
Modificando os dados
Índice de nível 1
(tipos de atributos)
Índice de nível 2
(valores de item)
Nível 3
(listas de acesso)
Nível 4
(registros de dados)
Atlanta
AGE
CITY
EMP-ADDR
Atlanta
...
Atlanta
Chicago
Chicago
Detroit
Chicago
Houston
Atlanta
Chicago
Chicago
Chicago
10
Atualizando
Atlanta
AGE
CITY
EMP-ADDR
Atlanta
...
Atlanta
Atlanta
Chicago
Detroit
Atlanta
Houston
Atlanta
Atlanta
Atlanta
Atlanta
11
Arquivos Invertidos para Busca em
Documentos
• Componentes
– Léxico: conjunto de palavras em um conjunto
de documentos;
– Lista de ocorrências: todas as entradas que se
aplicam a uma palavra específica;
– Postings: entrada em uma lista invertida.
• Construção
12
Exemplo
1. Chocolate mousse
2.
3.
4.
pie;
Chocolate chip
cookies;
Spinach pie;
Baklava
bake
2
baklava
4
chip
2
chocolate
1
cookie
2
mousse
1
pie
1
spinach
3
3
4
2
3
4
“I want to bake something with chocolate.”
13
Busca em Documentos Texto
• Termo único
– Busca no vocabulário e recupera lista de
ocorrências
• Conjunção
– Intersecção das listas de ocorrências
• Disjunção
– União das listas de ocorrências
• Negação
– Complemento do resultado
14
Exemplo
Documento
Texto
1
Pease porridge hot, pease porridge
cold,
2
Pease porridge in the pot,
3
Nine days old.
4
Some like it hot, some like it cold,
5
Some like it in the pot,
6
Nine days old.
15
Exemplo
Número
Termo
Documento
1
cold
(2;1,4)
2
days
(2;3,6)
3
hot
(2;3,6)
4
in
(2;1,4)
5
it
(2;2,5)
6
like
(2;4,5)
7
nine
(2;4,5)
8
old
(2;3,6)
9
Pease
(2;1,2)
10
porridge
(2;1,2)
11
pot
(2;2,5)
12
some
(2;4,5)
13
the
(2;2,5)
16
Exemplo
• Termo Único:
– Procurar termo “hot”
• Conjunção:
– Procurar “some AND hot”
• <4,5> AND <1,4> => <4>
• Disjunção:
– Procurar “hot OR nine”
• <1,4> OR <3,6> => <1,3,4,6>
• Negação:
– Procurar “NOT (some AND hot)”
• <1,2,3,5,6>
17
Granularidade do Índice de um
Arquivo Invertido
• Grossa
– Identifica apenas um bloco de texto
• Moderada
– Identifica apenas um documento
• Fina
– Identifica cada palavra (cada byte)
18
Grossa
• Índice requer menos memória
• Consulta exige mais processamento em
cada bloco
• Consulta de frase leva a maior número de
“false matches”
19
Fina
• Busca por frase é eficiente
• Busca aproximada é eficiente
• Índice requer mais memória
20
Exemplo
Número
Termo
(Documento;Palavras)
1
cold
[2;(1;6),(4;8)]
2
days
[2;(3;2),(6;2)]
3
hot
[2;(1;3),(4;4)]
4
in
[2;(2;3),(5;4)]
5
it
[2;(4;3,7),(5;3)]
6
like
[2;(4;2,6),(5;2)]
7
nine
[2;(3;1),(6;1)]
8
old
[2;(3;3),(6;3)]
9
Pease
[2;(1;1,4),(2;1)]
10
porridge
[2;(1;2.5),(2;2)]
11
pot
12
some
13
the
[2;(2;5),(5;6)]
[2;(4;1,5),(5;1)]
[2;(2;4),(5;5)]
21
Construção de Índices
• Métodos
– Matriz de freqüência
– Inversão em memória
– Inversão baseada em ordenação
22
Matriz de freqüência
• Cada linha corresponde a um documento
e cada coluna corresponde a um termo do
vocabulário
• Construção é bastante cara
– Ex.: Bíblia contém 8.965 termos e 31.101
documentos. Tamanho da matriz: 8.965 x
31.101 x 4 bytes ≈ 1 Gigabyte de memória
principal
23
Exemplo
cold
days
hot
in
it
like
1
1
-
1
-
-
-
2
2
2
-
-
-
1
-
-
1
1
3
-
1
-
-
-
-
-
-
4
1
-
1
-
2
2
-
-
5
-
-
-
1
1
1
-
-
6
-
1
-
-
-
-
-
-
pot
some
the
-
-
-
1
-
1
-
-
-
-
2
-
1
1
1
-
-
-
pease porridge
24
Número
Termo
Documento
1
2
3
4
5
6
1
cold
1
-
-
1
-
-
2
days
-
-
1
-
-
1
3
hot
1
-
-
1
-
-
4
in
-
1
-
-
1
-
5
it
-
-
-
2
1
-
6
like
-
-
-
2
1
-
7
nine
-
-
1
-
-
1
8
old
-
-
1
-
-
1
9
Pease
2
1
-
-
-
-
10
porridge
2
1
-
-
-
-
11
pot
-
1
-
-
1
-
12
some
-
-
-
2
1
-
13
the
-
1
-
-
1
25
Inversão em memória
Algoritmo:
1. Crie uma estrutura de dicionário vazia S.
2. Para cada documento Dd na coleção, 1≤ d ≤ N.
(a) Leia Dd, realizando o parser para obter termos indexáveis.
(b) Para cada termo indexável t pertencente a Dd,
i. Faça fd,t receber a freqüência do termo t em Dd.
ii. Busque por t em S.
iii. Se t não estiver em S, insira-o.
iv. Adicione um nó armazenando (d,fd,t) na lista
correspondente ao termo t.
3. Para cada termo 1 ≤ t ≤ n,
(a) Inicialize uma nova entrada do arquivo invertido.
(b) Para cada (d,fd,t) na lista correspondente a t, adicione (d,fd,t)
a essa entrada.
(c) Comprima a entrada.
(d) Adicione essa entrada no arquivo invertido.
26
Inversão em memória
• O índice é todo construído em memória principal
• Para armazenar o vocabulário: tabela hash é
•
•
geralmente a melhor escolha
Listas encadeadas em memória para armazenar
as listas invertidas em termos
Leva cerca de 6 horas para indexar uma coleção
de 5GB e consome 4GB de memória principal e
nenhum espaço extra em disco
27
Inversão Baseada em Ordenação
Algoritmo:
1. Construa um arquivo de saída temporário com registros
<t, d, ft >
2 . Ordene os registros usando o merge-sort
(a) Leia um pedaço do arquivo temporário
(b) Ordene-o (usando o quicksort)
(c) Escreva-o de volta no mesmo lugar
(d) Utilize o merge-sort para ordenação dos
pedaços
3. Leia o arquivo temporário e construa o arquivo
invertido.
28
Inversão Baseada em Ordenação
• Consome menos memória principal
• A inversão para a coleção de 5GB leva cerca de
•
20 horas usando 40MB de memória principal e
8GB de espaço extra em disco
Devido a grande quantidade de espaço em disco
consumida durante a inversão, este método é
considerado o melhor para coleções de tamanho
moderado (10 a 100MB)
29