Indexação Automática de Documentos

Eveline Alonso VelosoPUC-MINAS

Referências

BAEZA-YATES, Ricardo e RIBEIRO-NETO, Berthier. Modern Information Retrieval. 1ª edição, New York: ACM Press, 1999, capítulo 8.

Introdução Quando um sistema de recuperação

de informação processa uma consulta; deve recuperar e retornar documentos

relevantes para essa consulta. Consideremos inicialmente consultas

compostas por palavras-chave. Para determinar os documentos

relevantes para uma consulta composta por palavras-chave;

é necessário que o sistema de recuperação de informação determine primeiro os documentos onde os termos da consulta são encontrados.

Problema

Que estrutura de dados deve ser utilizada; de forma que possamos

encontrar rapidamente os documentos onde os termos utilizados na consulta aparecem?

Busca Seqüencial Opção mais óbvia:

procurar os termos especificados na consulta seqüencialmente nos documentos.

Essa opção é considerada apenas quando o documento: é pequeno; não pode se submeter a nenhum pré-

processamento. Exemplo:

localizar do Microsoft Word.

Índices Segunda opção:

construção e manutenção de estruturas de dados chamadas de índices;

que aumentam a velocidade da busca. É interessante construir e manter um

índice quando a coleção de documentos: é muito grande; é semi-estática.

Coleções semi-estáticas: podem ser atualizadas a intervalos regulares de

tempo; diariamente, por exemplo;

mas não apresentam a inserção de milhares de palavras por segundo.

É o caso da maioria das bases de dados atuais; inclusive das coleções das máquinas de busca.

Índices Para acelerar o processamento

da consulta; o índice deve ser construído antes

de ser necessário consultá-lo durante o processamento da consulta.

A melhor opção atualmente, para os tipos de consultas mais comuns, são os arquivos invertidos.

Arquivo Invertido

Mecanismo orientado a palavra.

Utilizado para indexar uma coleção de documentos; com o objetivo de acelerar o

processamento das consultas posteriormente.

Arquivo Invertido A estrutura de um arquivo invertido

é composta por dois elementos: vocabulário:

conjunto de termos de indexação distintos da coleção.

ocorrências: para cada termo do vocabulário;

é indicada uma lista com todos os documentos onde esse termo aparece;

lista de ocorrências. O conjunto de todas essas listas é chamado

de ocorrências.

Arquivo Invertido Dependendo dos tipos de consultas

oferecidos pelo sistema de recuperação de informação e do modelo de recuperação de informação utilizado; pode ser necessário armazenar, na lista

de ocorrências do termo, outras informações relacionadas à ocorrência do termo no documento:

frequência: número de ocorrências do termo no

documento; exata posição do termo no documento;

facilita o processamento de consultas por frase exata e por proximidade.

Exercício 1 Considere a coleção:

d1: Este é um texto. d2: palavras. d3: Um texto tem muitas d4: Palavras são d5: compostas por letras.

e construa o arquivo invertido correspondente.

1. Operações sobre o texto: conversão de todos os

caracteres para minúsculo; eliminação de marcas de

pontuação; eliminação das stopwords:

este, é, um, tem, são, por.

Exercício 1

2. Construção do arquivo invertido:

vocabulário ocorrênciastexto 1-1-1 3-1-1palavras 2-1-1 4-1-1muitas 3-1-2compostas 5-1-1letras 5-1-2

Exercício 1

Construção do Arquivo

Invertido Para grandes coleções de

documentos; como é o caso das atuais

máquinas de busca; não é possível manter todo

o índice em memória.

Construção do Arquivo

Invertido 1º passo:

Criação da estrutura que armazenará o vocabulário da coleção:

o espaço necessário para armazenar o vocabulário da coleção é relativamente pequeno;

por isso, em geral, a estrutura de dados utilizada para armazenar o vocabulário da coleção é mantida toda em memória.

Estrutura de dados normalmente utilizada para armazenar o vocabulário da coleção:

hash.

Construção do Arquivo

Invertido 1º passo:

Criação da estrutura que armazenará o vocabulário da coleção:

é necessário então estimar o tamanho do vocabulário da coleção;

essa estimativa é utilizada para alocar a quantidade de memória necessária ao hash.

Recomendações: o tamanho do hash, N, deve ser:

número primo; maior ou igual ao tamanho estimado para

o vocabulário da coleção.

Construção do Arquivo

Invertido 2º passo:

Determinação da função hash: recomendação:

escolher uma função hash que implique em poucas colisões.

Exemplo de função hash que resulta em poucas colisões:

Utilizaremos uma função hash mais simples:

termo do c caracter

)c(posição*)c(ord )hash(termo

N mod termo) do caracteres de (n )termo(hash

Construção do Arquivo

Invertido 3º passo:

Formação das triplas: cada termo de indexação identificado

no documento que está sendo indexado é mapeado em uma tripla:

<identificador do termo, identificador do documento, freqüência do termo no documento>, em que:

identificador do termo: número identificador do termo de acordo com a tabela hash;

identificador do documento: número identificador do documento que está sendo indexado;

freqüência do termo no documento: nessa primeira passagem é sempre igual a 1.

Construção do Arquivo

Invertido 4º passo:

Ordenação das triplas: para grandes coleções de documentos, em

geral, as triplas não cabem todas simultaneamente em memória.

Assim, quando a quantidade de memória disponível ou os documentos a serem indexados acabam;

as triplas presentes em memória são ordenadas utilizando-se um algoritmo de ordenação interna;

normalmente o quicksort; armazenadas em disco;

em arquivos temporários chamados de runs; e a memória é limpa;

tornando-se disponível para a acomodação de novas triplas.

Construção do Arquivo

Invertido 4º passo:

Ordenação das triplas: durante esse passo, se duas ou mais

triplas idênticas são identificadas; elas são substituídas por uma única

tripla; que indica no campo freqüência do

termo no documento a quantidade de triplas idênticas;

e apenas essa única tripla é armazenada em disco;

no run correspondente.

Construção do Arquivo

Invertido Após a execução do 4º passo;

o procedimento de indexação automática de documentos retorna ao 3º passo.

Os 3º e 4º passos vão se repetindo; alternadamente; até que todos os documentos da

coleção tenham sido completamente lidos.

Construção do Arquivo

Invertido 5º passo:

Intercalação dos arquivos intermediários:

utilizando-se algum algoritmo de ordenação externa;

geralmente intercalação balanceada; os diversos runs são agrupados em um

único arquivo ordenado armazenado em disco;

o arquivo de ocorrências. Em geral, esse é um arquivo binário;

para facilitar a localização das triplas durante a busca.

Construção do Arquivo

Invertido 5º passo:

Intercalação dos arquivos intermediários: durante esse passo, quando duas ou mais

triplas relacionadas à ocorrência de um mesmo termo, em um mesmo documento, são identificadas;

elas são substituídas por uma única tripla; que indica no campo freqüência do termo no

documento a quantidade total de ocorrências do do termo no documento.

Finalmente, o hash é atualizado com a indicação;

para cada termo de indexação; das posições inicial e final, no arquivo de

ocorrências armazenado em disco, de suas triplas.

No momento da busca; é necessário ler, do arquivo de

ocorrências armazenado em disco;

apenas a porção desse arquivo correspondente às informações do termo de indexação pesquisado.

Busca

Exercício 2 Considere a coleção:

d1: Este é um texto. d2: palavras. d3: Um texto tem muitas d4: Palavras são d5: compostas por letras.

e construa o arquivo invertido correspondente, considerando que a quantidade de memória disponível comporta apenas três triplas simultaneamente.

Operações sobre o texto: conversão de todos os

caracteres para minúsculo; eliminação de marcas de

pontuação; eliminação das stopwords:

este, é, um, tem, são, por.

Exercício 2

1º passo: tamanho da tabela hash (N):

N = 5 2º passo:

função hash:

5 mod termo) do caracteres de (n )termo(hash

Exercício 2

Exercício 2 hash(texto) =

5 mod 5 = 0 hash(palavras) =

8 mod 5 = 3 hash(muitas) =

6 mod 5 = 1 hash(compostas)

= 9 mod 5 = 4

hash(letras) = 6 mod 5 = 1

0 texto

1 muitas

2

3 palavras

4 compostas

5 letras

3º e 4º passos: formação das triplas, ordenação e

armazenamento nos arquivos intermediários (runs):

<0, 1, 1> <3, 2, 1> <0, 3, 1>run #1: <0, 1, 1> <0, 3, 1> <3, 2, 1> <1, 3, 1> <3, 4, 1> <4, 5, 1>run #2: <1, 3, 1> <3, 4, 1> <4, 5, 1> <5, 5, 1>run #3: <5, 5, 1>

Exercício 2

5º passo: intercalação dos arquivos

intermediários (runs):

run #1: <0, 1, 1> <0, 3, 1> <3, 2, 1> run #2: <1, 3, 1> <3, 4, 1> <4, 5, 1> run #3: <5, 5, 1>

Ocorrências: <0, 1, 1> <0, 3, 1> <1, 3, 1> <3, 2,

1> <3, 4, 1> <4, 5, 1> <5, 5, 1>

Exercício 2

5º passo: atualização da tabela hash:

Exercício 2

0 texto - pi: 0 - pf: 1

1 muitas - pi: 2 - pf: 2

2

3 palavras - pi: 3 - pf: 4

4 compostas - pi: 5 - pf: 5

5 letras - pi: 6 - pf: 6

Ocorrências: <1, 1> <3, 1> <3, 1> <2, 1> <4, 1> <5, 1> <5, 1>