Embed Size (px)
Citation preview
1
Efficient Phrase Querying with Efficient Phrase Querying with an Auxiliary Indexan Auxiliary Index
(SIGIR) 2002(SIGIR) 2002
Trabalho Trabalho realizado por: realizado por:
João Casteleiro João Casteleiro AlvesAlves
Instituto Superior TécnicoInstituto Superior TécnicoRecuperação de InformaçãoRecuperação de Informação
Prof. Dr. Pável Pereira CaladoProf. Dr. Pável Pereira Calado
2
Introdução
Pré - Processamento da imagem
Abordagem 1: Detecção de Contornos
Abordagem 2: Extracção de Características
Estrutura da apresentação
Propriedades das “queries”
Índices Invertidos
Índices “Nextword”
Abordagem combinada de avaliação de “queries”
Resultados experimentais
Conclusões
3
Procura de informação na Web é dependente de motores de busca.
Introdução
Eficiência Eficácia
Para fazer a busca de informação na Web é então necessário
Download dos textos/informação
Indexar o conteúdo
Querie
4
Crescimento da Web (consequências)
- Invisibilidade
- Mapeamento dos indíces em relação conteúdo público indexável.
Introdução
Dificuldades ao nivel das consultas (podem ser vagas)
As consultas são normalmente feitas através de simples palavras
A 08-Jul-2006 o Google indexava cerca de 24.000.000.000 páginas
5
Para se fazer uma pesquisa por frases é então necessário os motores de busca possuirem métodos apropriados.
- Índices invertidos
- Índices “nextword”
Introdução
Solução:
- Pesquisa por frases
Não é ambigua na definição do conceito
6
Devido às limitações apresentadas pelas soluções anteriores é assim proposta uma nova solução:
- Combinação de índices invertidos e de índices “nextword”.
Introdução
Os métodos de avaliação de frases “querie” podem no entanto requisitar muitos Mb, tornando o seu uso limitado.
Soluções apresentadas:
- Usar “stopping words”
- Indexar frases directamente
7
Introdução
Pré - Processamento da imagem
Abordagem 1: Detecção de Contornos
Abordagem 2: Extracção de Características
Estrutura da apresentação
Propriedades das “queries”
Índices Invertidos
Índices “Nextword”
Abordagem de avaliação da query combinada
Resultados experimentais
Conclusões
8
De modo a estudar as caracteristicas das “queries” foi analisado um grande conjunto de registos de “queries”.
- Foram usados dados do “Excite”
Após se retirar as “queries” de conteúdo obsceno, obtiveram-se 1,583,922 consultas.
132,576 ou 8,3% dizem respeito a frases “queries”.
5% contém uma palavra que não ocorre nos 21.9 Gb de dados usados
41% das “queries” que não são frases correspondem a uma frase nos 21.9Gb usados
Propriedades das “queries”
9
Estudando apenas as frases “queries” verifica-se que, 11,103 ou 8.4% incluem uma das três palavras mais comuns no conjunto de dados.
14,4% das frases “queries” contêm uma das vinte palavras mais comuns.
QUESTÃO: As palavras comuns são importantes ou não???
SIM Não
Propriedades das “queries”
10
Posto isto, usar o método de “stopping” nas palavras comuns leva a um resultado imprevísivel.
Propriedades das “queries”
Fazer o “stopping” das palavras comuns da query “tower of London” resulta em avaliar “tower --- London”.
Foram estudado os documentos encontrados para todas as “queries” com diferentes valores de “stopping” para as palavras comuns.
- “Stopping” ás 3 palavras mais comuns
- “Stopping” ás 20 palavras mais comuns
- “Stopping” ás 254 palavras mais comuns
390 x 10^6
490 x 10^6
1693 x 10^6
Nem todas as correspondências são correctas
11
Introdução
Pré - Processamento da imagem
Abordagem 1: Detecção de Contornos
Abordagem 2: Extracção de Características
Estrutura da apresentação
Propriedades das “queries”
Índices Invertidos
Índices “Nextword”
Resultados experimentais
Conclusões
Abordagem combinada de avaliação de “query”
12
Índices Invertidos
Os índices invertidos são o método standard de suporte de “queries” em grandes bases de dados de texto.
Um índice invertido é uma estrutura de dois níveis:
- O nível mais acima contém todos os índices dos termos da colecção (palavras pertencentes ao texto).
- O nível mais baixo é um conjunto de listas de “postings”, uma por cada índice de termo.
13
Índices Invertidos
Cada “posting” é assim composto por três elementos.
- d é o identificador do documento que contém o termo t.
- f d,t é a frequência de t em d.
- o é o valor das posições em d em que t é observado.
14
Índices Invertidos
Vocabulário de 5 palavras em que cada uma tem uma lista de “postings”.
É então aliciante aplicar um índice invertido na busca por um único termo.
15
Índices Invertidos
QUESTÃO: Como funcionam os índices invertidos para frases (mais do que um termo) ???
A idéia é fazer multiplas pesquisas, procurando ocorrências sucessivas dos termos nos documentos.
O primeiro termo é procurado, resultando uma lista temporária de documentos e posições do termo nos documentos
O próximo termo é pesquisado na lista temporária, sendo retirados os documentos em que o termo não ocorre na posição na posição correcta.
O processo repete-se até que o último termo seja encontrado ou que a lista temporária fique vazia.
16
Índices Invertidos
Temos então um custo linear para o processo de busca e também para o custo do espaço.
A ordem de busca dos termos da frase é fundamental.
- Devemos iniciar a busca pelo termo menos frequente (fazendo a pesquisa em ordem diferente da ordem de ocorrência dos termos na frase, mas nunca perdendo a sua posição inicial).
- Minimizamos tempo e espaço, já que a lista temporária inicial terá o menor tamanho possível
Iniciar uma pesquisa por um termo muito comum nos documentos pode levar a uma lista intratável.
17
Índices Invertidos
Podem ser usadas diversas técnicas de optimização da consulta por frases com índices invertidos.
Uma optimização importante é o uso de técnicas de compressão.
18
Introdução
Pré - Processamento da imagem
Abordagem 1: Detecção de Contornos
Abordagem 2: Extracção de Características
Estrutura da apresentação
Propriedades das “queries”
Índices Invertidos
Índices “Nextword”
Resultados experimentais
Conclusões
Abordagem combinada de avaliação de “query”
19
Os ficheiros invertidos permitem a avaliação de “queries” por frases, no entanto, as técnicas de indexação de frases orientadas são mais eficientes.
Uma dessas técnicas é conhecida como índices “nextword”
Índices “Nextword”
Um índice “nextword” é uma estrutura de 3 niveis:
- No primeiro nível temos as palavras do vocabulário, a que se chamam de “firstwords”.
- No segundo nível temos o índice para a próxima palavra
- No último nível, para cada “nextword” existe uma lista de “postings” das posições em que o par “firstword-nextword” ocorrem.
20
- Neste exemplo existem 2 “firstword” “in” e “new”.
- Existem algumas “nextword” “all”, “new”, “age”, etc.
- Para cada par “firstword-nextword” existe uma lista de postings.
Índices “Nextword”
21
Facilmente se percebe que o tamanho das listas de “postings” para os índices “nextword” é normalmente pequeno.
Índices “Nextword”
A maioria dos pares não aparece frequentemente
“boulder municipal employees credit union”
“boulder”.”municipal”, “employess”.”credit” e ”credit”.”union”
“boulder”.”municipal”, “municipal”.” employess” e ”credit”.”union”
Qual o conjunto de pares que deve ser avaliado???
22
Método de escolha da ordem de avaliação dos pares
- Se o número dos termos querie for par, a query consiste em n/2 pares dijuntos.
- Se o número dos termos da querie for impar, a query consiste em n/2 pares conjuntos.
Índices “Nextword”
Exemplo: “The man who is”
23
O índice “nextword” obtido para a colecção de dados usada tinha o tamanho de 4487 Mb, muito maior que um índice invertido.
Índices “Nextword”
O tempo de avaliação de “queries” reduziu significativamente (quando comparado com os índices invertidos).
24
Introdução
Pré - Processamento da imagem
Abordagem 1: Detecção de Contornos
Abordagem 2: Extracção de Características
Estrutura da apresentação
Propriedades das “queries”
Índices Invertidos
Índices “Nextword”
Resultados experimentais
Conclusões
Abordagem combinada de avaliação de “query”
25
Abordagem de avaliação da query combinada
Esta abordagem tenta obter o melhor dos dois métodos apresentados antes (listas ínvertidas e listas “nextword”).
Objectivo: Manter a eficiência das consultas, diminuindo o tamanho dos índices gerados.
É então usado um esquema de “top frequency”.
- Apenas as palavras mais comuns são usadas como índice “nextword”.
- As restantes palavras são indexadas como um índice invertido.
26
Abordagem de avaliação da query combinada
“historic” e “railroads” são processados tendo em conta o índice invertido.
“historic railroads in new hampshire”
“in” e “new” são palavras comuns, logo o par “in”.”new” deve ser procurado nos índices “nextword”.
“new”.”hampshire” ou “hampshire”???
27
Introdução
Pré - Processamento da imagem
Abordagem 1: Detecção de Contornos
Abordagem 2: Extracção de Características
Estrutura da apresentação
Propriedades das “queries”
Índices Invertidos
Índices “Nextword”
Resultados experimentais
Conclusões
Abordagem combinada de avaliação de “query”
28
Abordagem 1: Detecção de Contornos
Resultados experimentais
Usar um índice “nextword” permite a avaliação de todas as frase “queries” de um modo rápido.
Verifica-se que se consegue obter tamanhos de índices de menores dimênsões.
Índice combinadoÍndice “Nextword”
Os tempos obtidos pela abordagem combinada são os melhores.
29
Introdução
Pré - Processamento da imagem
Abordagem 1: Detecção de Contornos
Abordagem 2: Extracção de Características
Estrutura da apresentação
Propriedades das “queries”
Índices Invertidos
Índices “Nextword”
Resultados experimentais
Conclusões
Abordagem combinada de avaliação de “query”
30
Foi proposto o uso de um índice auxiliar pequeno para frases “queries” de grandes coleccções de texto
Conclusões
Todas as palavras estão indexadas num índice invertido, no entanto as mais comuns estão também num índice “nextword” (abordagem combinada).
Estes resultados demonstram ainda que não é necessário fazer “stopping” nas frases.
O custo dos índices de avaliação de frases foi substancialmente reduzido.
O sistema pode ser melhorado, especialmente na escolha de pares durante a avaliação da querie.
31
FIM
