11

Arquivos InvertidosArquivos Invertidos

André Ferreira da SilvaAndré Ferreira da Silva

Jimy Marques MadeiroJimy Marques Madeiro

Talita Perciano Costa LeiteTalita Perciano Costa Leite

UNIVERSIDADE FEDERAL DE ALAGOASUNIVERSIDADE FEDERAL DE ALAGOASDEPARTAMENTO DE TECNOLOGIA DA INFORMAÇÃODEPARTAMENTO DE TECNOLOGIA DA INFORMAÇÃO

CIÊNCIA DA COMPUTAÇÃOCIÊNCIA DA COMPUTAÇÃO

22

RoteiroRoteiro• O que é a estruturaO que é a estrutura• Como funcionaComo funciona• Operações em arquivos invertidos de Registros Operações em arquivos invertidos de Registros

de Dadosde Dados– Modificando os dadosModificando os dados– AtualizandoAtualizando

• Arquivos Invertidos para busca em documentosArquivos Invertidos para busca em documentos– Busca em documentos textoBusca em documentos texto

• Granularidade do Índice de um Arquivo InvertidoGranularidade do Índice de um Arquivo Invertido• Construção de índicesConstrução de índices

– Matriz de freqüênciaMatriz de freqüência– Inversão em memóriaInversão em memória– Inversão baseada em ordenaçãoInversão baseada em ordenação

33

O que é a estruturaO que é a estrutura

• Organização ou estrutura de arquivo que Organização ou estrutura de arquivo que permite uma procura rápida por consultas permite uma procura rápida por consultas em geral envolvendo valores de chaves em geral envolvendo valores de chaves secundárias especificadossecundárias especificados

• Os valores das chaves secundárias são Os valores das chaves secundárias são usados como uma base para localizar uma usados como uma base para localizar uma classe de registro de dadosclasse de registro de dados

• Possui duas partes principais:Possui duas partes principais:– Estrutura de buscaEstrutura de busca– Lista invertidaLista invertida

44

O que é a estruturaO que é a estrutura

• O tipo mais comum de arquivo invertido tem um nível-duplo O tipo mais comum de arquivo invertido tem um nível-duplo de indexação e lista de acesso associadade indexação e lista de acesso associada

AGE

CITY

EMP-ADDR

...

Atlanta

Chicago

Detroit

Houston

Atlanta

Atlanta

Chicago

Chicago

Atlanta

Chicago

Chicago

Índice de nível 1 Índice de nível 1

(tipos de atributos)(tipos de atributos)Índice de nível 2 Índice de nível 2

(valores de item)(valores de item)Nível 3 Nível 3

(listas de acesso)(listas de acesso)Nível 4Nível 4

(registros de (registros de dados)dados)

55

O que é a estruturaO que é a estrutura

• Arquivos completamente invertidosArquivos completamente invertidos– É invertido sobre todos os tipos itens chave no É invertido sobre todos os tipos itens chave no

registroregistro– Estabelecem acesso rápido para base de dadosEstabelecem acesso rápido para base de dados– Grande espaço de armazenamento na Grande espaço de armazenamento na

indexaçãoindexação

• Arquivo parcialmente invertidoArquivo parcialmente invertido– É invertido sobre um número selecionado de É invertido sobre um número selecionado de

tipos de itens chave tipos de itens chave

66

Como funcionaComo funciona

• Arquivos invertidos são tradicionalmente Arquivos invertidos são tradicionalmente utilizados para a implementação de índices utilizados para a implementação de índices lexicográficos (Harman et al. 1992)lexicográficos (Harman et al. 1992)

• Busca por frases:Busca por frases:– Índice invertido contém para cada palavra:Índice invertido contém para cada palavra:

• Um apontador para cada um dos documentos dos Um apontador para cada um dos documentos dos quais a palavra ocorrequais a palavra ocorre

• As posições da palavra nesse documentoAs posições da palavra nesse documento

– Busca torna-se mais eficiente nesse tipo de Busca torna-se mais eficiente nesse tipo de índiceíndice

– A dimensão do próprio índice é um problemaA dimensão do próprio índice é um problema– Índice precisa ser atualizado a cada Índice precisa ser atualizado a cada

modificação do documento originalmodificação do documento original

77

Como funcionaComo funciona

• A pesquisa é feita da seguinte forma:A pesquisa é feita da seguinte forma:– O primeiro termo é pesquisadoO primeiro termo é pesquisado– Como resultado tem-se uma lista temporária Como resultado tem-se uma lista temporária

de documentos e posições contendo o termo de documentos e posições contendo o termo pesquisadopesquisado

– Utiliza-se a lista temporária para pesquisar o Utiliza-se a lista temporária para pesquisar o próximo termopróximo termo

– Repete-se a pesquisa para os próximos termos Repete-se a pesquisa para os próximos termos até que o último tenha sido pesquisado, ou até até que o último tenha sido pesquisado, ou até que a lista esteja vaziaque a lista esteja vazia

• É desejável que os termos menos comuns É desejável que os termos menos comuns sejam pesquisados inicialmente. sejam pesquisados inicialmente.

88

Modificando os dadosModificando os dados

AGE

CITY

EMP-ADDR

...

Atlanta

Chicago

Detroit

Houston

Atlanta

Atlanta

Chicago

Chicago

Atlanta

Chicago

Chicago

Índice de nível 1 Índice de nível 1

(tipos de atributos)(tipos de atributos)Índice de nível 2 Índice de nível 2

(valores de item)(valores de item)Nível 3 Nível 3

(listas de acesso)(listas de acesso)Nível 4Nível 4

(registros de (registros de dados)dados)

99

AGE

CITY

EMP-ADDR

...

Atlanta

Chicago

Detroit

Houston

Atlanta

Atlanta

Chicago

Chicago

Atlanta

Chicago

Chicago

Modificando os dadosModificando os dadosÍndice de nível 1 Índice de nível 1

(tipos de atributos)(tipos de atributos)Índice de nível 2 Índice de nível 2

(valores de item)(valores de item)Nível 3 Nível 3

(listas de acesso)(listas de acesso)Nível 4Nível 4

(registros de (registros de dados)dados)

1010

Modificando os dadosModificando os dadosÍndice de nível 1 Índice de nível 1

(tipos de atributos)(tipos de atributos)Índice de nível 2 Índice de nível 2

(valores de item)(valores de item)Nível 3 Nível 3

(listas de acesso)(listas de acesso)Nível 4Nível 4

(registros de (registros de dados)dados)

AGE

CITY

EMP-ADDR

...

Atlanta

Chicago

Detroit

Houston

Atlanta

Atlanta

Chicago

Chicago

Atlanta

Chicago

Chicago

Chicago

1111

AtualizandoAtualizando

AGE

CITY

EMP-ADDR

...

Atlanta

Chicago

Detroit

Houston

Atlanta

Atlanta

Atlanta

Atlanta

Atlanta

Atlanta

Atlanta

Atlanta

1212

Arquivos Invertidos para Busca Arquivos Invertidos para Busca em Documentosem Documentos

• ComponentesComponentes– Léxico: conjunto de palavras em um Léxico: conjunto de palavras em um

conjunto de documentos;conjunto de documentos;– Lista de ocorrências: todas as entradas Lista de ocorrências: todas as entradas

que se aplicam a uma palavra específica;que se aplicam a uma palavra específica;– Postings: entrada em uma lista invertida.Postings: entrada em uma lista invertida.

• ConstruçãoConstrução

1313

ExemploExemplo

1.1. Chocolate mousse Chocolate mousse pie;pie;

2.2. Chocolate chip Chocolate chip cookies;cookies;

3.3. Spinach pie;Spinach pie;

4.4. BaklavaBaklava

bake

baklava

chip

chocolate

cookie

mousse

pie

spinach

2

4

2

1

2

1

1

3

3 4

2

3 4

“I want to bake something with chocolate.”

1414

Busca em Documentos Busca em Documentos TextoTexto• Termo únicoTermo único

– Busca no vocabulário e recupera lista de Busca no vocabulário e recupera lista de ocorrênciasocorrências

• ConjunçãoConjunção– Intersecção das listas de ocorrênciasIntersecção das listas de ocorrências

• DisjunçãoDisjunção– União das listas de ocorrênciasUnião das listas de ocorrências

• NegaçãoNegação– Complemento do resultadoComplemento do resultado

1515

ExemploExemplo

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.

1616

ExemploExemploNú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)

1717

ExemploExemplo

• Termo Único:Termo Único:– Procurar termo “hot”Procurar termo “hot”

• Conjunção:Conjunção:– Procurar “some AND hot”Procurar “some AND hot”

• <4,5> AND <1,4> => <4><4,5> AND <1,4> => <4>

• Disjunção:Disjunção:– Procurar “hot OR nine”Procurar “hot OR nine”

• <1,4> OR <3,6> => <1,3,4,6><1,4> OR <3,6> => <1,3,4,6>

• Negação:Negação:– Procurar “NOT (some AND hot)”Procurar “NOT (some AND hot)”

• <1,2,3,5,6><1,2,3,5,6>

1818

Granularidade do Índice de um Granularidade do Índice de um Arquivo InvertidoArquivo Invertido

• GrossaGrossa– Identifica apenas um bloco de textoIdentifica apenas um bloco de texto

• ModeradaModerada– Identifica apenas um documentoIdentifica apenas um documento

• FinaFina– Identifica cada palavra (cada byte)Identifica cada palavra (cada byte)

1919

GrossaGrossa

• Índice requer menos memóriaÍndice requer menos memória

• Consulta exige mais processamento Consulta exige mais processamento em cada blocoem cada bloco

• Consulta de frase leva a maior Consulta de frase leva a maior número de “false matches”número de “false matches”

2020

FinaFina

• Busca por frase é eficienteBusca por frase é eficiente

• Busca aproximada é eficienteBusca aproximada é eficiente

• Índice requer mais memóriaÍndice requer mais memória

2121

ExemploExemploNú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 [2;(2;5),(5;6)]

12 some [2;(4;1,5),(5;1)]

13 the [2;(2;4),(5;5)]

2222

Construção de ÍndicesConstrução de Índices

• MétodosMétodos– Matriz de freqüênciaMatriz de freqüência– Inversão em memóriaInversão em memória– Inversão baseada em ordenaçãoInversão baseada em ordenação

2323

Matriz de freqüênciaMatriz de freqüência

• Cada linha corresponde a um Cada linha corresponde a um documento e cada coluna corresponde documento e cada coluna corresponde a um termo do vocabulárioa um termo do vocabulário

• Construção é bastante caraConstrução é bastante cara– Ex.: Bíblia contém 8.965 termos e 31.101 Ex.: Bíblia contém 8.965 termos e 31.101

documentos. Tamanho da matriz: 8.965 x documentos. Tamanho da matriz: 8.965 x 31.101 x 4 bytes ≈ 1 Gigabyte de 31.101 x 4 bytes ≈ 1 Gigabyte de memória principalmemória principal

2424

ExemploExemplocold days hot in it like peasepease porridgporridg

ee

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

- - -

2525

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 -

2626

Inversão em memóriaInversão em memóriaAlgoritmo: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.

2727

Inversão em memóriaInversão em memória

• O índice é todo construído em memória O índice é todo construído em memória principalprincipal

• Para armazenar o vocabulário: tabela Para armazenar o vocabulário: tabela hashhash é geralmente a melhor escolhaé geralmente a melhor escolha

• Listas encadeadas em memória para Listas encadeadas em memória para armazenar as listas invertidas em termosarmazenar as listas invertidas em termos

• Leva cerca de 6 horas para indexar uma Leva cerca de 6 horas para indexar uma coleção de 5GB e consome 4GB de memória coleção de 5GB e consome 4GB de memória principal e nenhum espaço extra em discoprincipal e nenhum espaço extra em disco

2828

Inversão Baseada em Inversão Baseada em OrdenaçãoOrdenaçã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ços3. Leia o arquivo temporário e construa o arquivo invertido.

2929

Inversão Baseada em Inversão Baseada em OrdenaçãoOrdenação

• Consome menos memória principalConsome menos memória principal

• A inversão para a coleção de 5GB leva cerca A inversão para a coleção de 5GB leva cerca de 20 horas usando 40MB de memória de 20 horas usando 40MB de memória principal e 8GB de espaço extra em discoprincipal e 8GB de espaço extra em disco

• Devido a grande quantidade de espaço em Devido a grande quantidade de espaço em disco consumida durante a inversão, este disco consumida durante a inversão, este método é considerado o melhor para método é considerado o melhor para coleções de tamanho moderado (10 a coleções de tamanho moderado (10 a 100MB)100MB)