Introduction to Information Retrieval
Introduction to
Information Retrieval
CS276
Information Retrieval and Web Search
Christopher Manning and Prabhakar Raghavan
Lecture 1: Boolean retrieval
Introduction to Information Retrieval
Definições
 Técnicas para encontrar documentos de natureza não
estruturada(texto em geral) que satisfaça uma
necessidade de informação de um usuário a partir de
grande quantidade de documentos.
 Coleção: Conjunto de documentos
 Objetivo: Recuperar os documentos com
informações que são relevantes para a necessidade
do usuário.
2
Introduction to Information Retrieval
Desestruturado (texto) vs. Estruturado
(banco de dados) em 1996
Empresa de
dados
estatísticos
3
Introduction to Information Retrieval
Desestruturado (texto) vs. Estruturado
(banco de dados) em 2009
4
Introduction to Information Retrieval
Técnicas RI
 Recuperação Booleana;




Modelo Clássico;
Matriz de Incidência;
Índice Invertido;
Otimização de consultas.
Introduction to Information Retrieval
The classic search model
TASK
Info Need
Verbal
form
Query
SEARCH
ENGINE
Query
Refinement
Results
Corpus
Sec. 1.1
Introduction to Information Retrieval
Matriz Incidência (Termos x Documentos)
Antony and Cleopatra
Julius Caesar
The Tempest
Hamlet
Othello
Macbeth
Antony
1
1
0
0
0
1
Brutus
1
1
0
1
0
0
Caesar
1
1
0
1
1
1
Calpurnia
0
1
0
0
0
0
Cleopatra
1
0
0
0
0
0
mercy
1
0
1
1
1
1
worser
1
0
1
1
1
0
Brutus AND Caesar BUT NOT
Calpurnia
1 se documento
contem termo, 0
caso contrario
Introduction to Information Retrieval
Sec. 1.1
Matriz de Incidência





Cada linha representa um termo.
Cada coluna representa um documento.
Cada posição do vetor pode assumir 0/1.
Onde: 0  Ausencia no texto e 1  aparece no texto.
Exemplo consulta: Brutus, Caesar and not Calpurnia
(complemento);
 Fazer uma operacao AND nas linhas Brutus, Caesar e
Calpurnia.
 Exemplo:
 110100 AND 110111 AND 101111
= 100100
(Brutus)
(Caesar)
(Calpurnia)
(Resposta)
8
Sec. 1.2
Introduction to Information Retrieval
Índice Invertido
 Para cada termo t, nos devemos criar uma lista com
os números onde o termo t aparece;
 Onde: docID, representa um número de documento;
Brutus
1
Caesar
1
Calpurnia
2
2
2
31
4
4
11 31 45173 174
5
6
16 57 132
54 101
9
Sec. 1.2
Introduction to Information Retrieval
Índice Invertido
 Em memória, podemos usar listas ligadas ou arrays de
tamanhos variáveis;
Listas
Brutus
1
Caesar
1
Calpurnia
Dicionário
2
2
2
4
11 31 45 173
4
5
6
16 57 132
31 54 101
Listas
Ordenado pelo by docID
10
Sec. 1.2
Introduction to Information Retrieval
Construção Índice Invertido
Documentos para
indexar.
Friends, Romans, countrymen.
Tokenizer
Token stream.
More on
these later.
Friends Romans
Linguistic
modules
Tokens modificados.
Índice Invertido
Countrymen
friend
roman
countryman
Indexer friend
2
4
roman
1
2
countryman
13
16
Sec. 1.2
Introduction to Information Retrieval
Passos Indexador: Token
 Dividir os documentos em pares (termos, Document
ID).
Doc 1
I did enact Julius
Caesar I was killed
i' the Capitol;
Brutus killed me.
Doc 2
So let it be with
Caesar. The noble
Brutus hath told you
Caesar was ambitious
Introduction to Information Retrieval
Passos Indexador: Ordenação
 Ordenar termos.
 Ordem alfabética
Sec. 1.2
Introduction to Information Retrieval
Sec. 1.2
Passos Indexador: Dicionário & Listas
 Criar dicionário de
termos;
 Adicionar na lista os
documentos que o
termos aparecem;
 Adicionar a
freqüência do
termo;
Sec. 1.2
Introduction to Information Retrieval
Custo de Armazenamento
Listas
dos
docIDs
Termos
e
freqüên
cias
Ponteiros
15
Sec. 1.3
Introduction to Information Retrieval
Consulta com operador: AND
 Considere a consulta:
Brutus AND Caesar
 Recuperar a lista do termo Brutus;
 Recuperar a lista do termo Caesar;
 Interseção (“Merge”) das duas listas:
2
4
8
16
1
2
3
5
32
8
64
13
128
21
Brutus
34 Caesar
16
Introduction to Information Retrieval
Interseção de duas listas
(“merge” algorithm)
17
Sec. 1.3
Introduction to Information Retrieval
Exemplo: merge algorithm
2
8
2
4
8
16
1
2
3
5
32
8
64
13
Brutus
34 Caesar
128
21
Obs: As listas devem estar ordenadas pelo docID.
18
Introduction to Information Retrieval
Sec. 1.1
Conclusões Modelo Booleano
 Ainda e utilizado em sistemas:
 E-mail, catalogo de Bibliotecas;
 Modelo de RI utilizado por 3 décadas.
 Processamento lento para consultar grande volume
de termos e documentos
 Exemplo: Um milhão de documentos, cada documento
aproximadamente com 1000 termos.
 Exatidão nas consultas
 Exemplo:
 a) Procurar palavra Brutus;
 b) Procurar palavras iniciadas com a letra B. (impossível)
19
Sec. 1.3
Introduction to Information Retrieval
Otimização de consultas
 Qual a melhor maneira de realizar a consulta
abaixo?
Brutus
2
Caesar
1
Calpurnia
4
2
8
16 32 64 128
3
5
8
16 21 34
13 16
Query: Brutus AND Calpurnia AND Caesar
20
Sec. 1.3
Introduction to Information Retrieval
Exemplo de otimização de consultas
 Inicie com os termos com as menores freqüências, ou seja,
que possuem as menores listas.
Por isso e importante
armazenar a freqüência dos
termos
Brutus
2
Caesar
1
Calpurnia
4
2
8
16 32 64 128
3
5
8
16 21 34
13 16
Execute a consulta como (Calpurnia AND Brutus) AND Caesar.
21
Introduction to Information Retrieval
Sec. 1.3
Otimização mais geral
 e.g., (madding OR crowd) AND (ignoble OR
strife)
 Pegue freqüência dos documentos para todos os
termos.
 Estime o tamanho de cada OR pela soma das
freqüências dos documentos.
 Processar em ordem crescente pelo tamanho das
listas (OR).
22
Introduction to Information Retrieval
Course staff
 Professor: Christopher Manning
Office: Gates 158
[email protected]
 Professor: Prabhakar Raghavan
pragh@yahoo-
inc.com
 TAs: Andrey Guev, Shakti Sinha, Roshan Sumbaly
 In general, don’t use the above addresses, but:
 Newsgroup: su.class.cs276
[preferred]
 [email protected]
23