Introduction to Information Retrieval
Introduction to
Information Retrieval
CS276: Information Retrieval and Web Search
Christopher Manning and Prabhakar Raghavan
Lecture 2: The term vocabulary and postings
lists
Introduction to Information Retrieval
Relembrando….
Documentos para
indexar.
Friends, Romans, countrymen.
Tokenizer
Token
Friends Romans
Countrymen
Linguistic
modules
Tokens modificados.
Indices Invertidos.
friend
roman
countryman
Indexer friend
2
4
roman
1
2
countryman
13
16
Introduction to Information Retrieval
Analisando um documento
 Problemas de um documento
 Qual o formato?
 Existem diversos formatos;
 pdf/word/excel/html.
 Qual a língua?
 Diversidade das línguas.
 Quais os conjuntos de caracteres e usado?
Sec. 2.1
Introduction to Information Retrieval
Operações sobre texto
 Fases
 Análise léxica
 Elimina dígitos, pontuação, etc
 Eliminação de stopwords
 Artigos, pronomes, etc
 Operação de stemming
 Redução da palavra ao seu radical
Introduction to Information Retrieval
TOKENS
Introduction to Information Retrieval
Tokenization
 Input: “Friends, Romans and Countrymen”
 Output: Tokens
 Friends
 Romans
 Countrymen
 Quais os tokens são validos?
Sec. 2.2.1
Introduction to Information Retrieval
Sec. 2.2.1
Tokenization
 Problemas na tokenization:
 Finland’s capital 
Finland? Finlands? Finland’s?
 Hewlett-Packard  Hewlett and Packard tem
dois tokens?
 Como fazer com os hífens?
 state-of-the-art
 co-education
 San Francisco: um token ou dois?
 Como decidir a quantidade de tokens?
Sec. 2.2.1
Introduction to Information Retrieval
Números





3/20/91
Mar. 12, 1991
55 B.C.
B-52
My PGP key is 324a3df234cb23e
(800) 234-2333
20/3/91
Introduction to Information Retrieval
Tokenization: Problemas das línguas
 Frances
 L'ensemble  one token or two?
 L ? L’ ? Le ?
 Alemão
 Lebensversicherungsgesellschaftsangestellter
Sec. 2.2.1
Introduction to Information Retrieval
Tokenization: Problemas das línguas
 Língua arábica
Sec. 2.2.1
Introduction to Information Retrieval
Stop words
 Palavras que não acrescentam semântica na
sentença, com isso podem ser eliminadas;
 Exemplo língua inglesa: the, a, and, to, be
 Existe uma tabela padronizada de acordo com a língua.
Sec. 2.2.2
Introduction to Information Retrieval
Stop words: Tabela Português
Introduction to Information Retrieval
Padronização dos termos
 Tokenization depende da língua.
 Padronizar as palavras na mesma forma:




U.S.A. e USA tem o mesmo significado
Acentos: e.g., Francês résumé vs. resume.
Tremas: e.g., Alemão: Tuebingen vs. Tübingen
Reduzir para letras minúsculas
 Fed vs. fed
 SAIL vs. sail
 Retirar os hífens dos termos:
 anti-discriminatory, antidiscriminatory
Sec. 2.2.3
Sec. 2.2.3
Introduction to Information Retrieval
Padronização dos termos
 Exemplos:
 Enter: window
 Enter: windows
 Enter: Windows
Search: window, windows
Search: Windows, windows, window
Search: Windows
Introduction to Information Retrieval
Thesauri and soundex
 Sinônimos e homônimos?
 E.g., classes equivalentes:
 car = automobile
color = colour
 Nos podemos reescrever para formar classes equivalentes:
 Quando um documento contem automobile, utilizamos o índice de carautomobile (e vice-versa)
 Ou nos podemos expandir a consulta para:
 Quando a consulta conter automobile, analisar car também.
 Como lidar com os erros ortográficos?
 Utilizar a técnica de soundex, o qual se baseia em heurísticas
fonéticas.
 Veremos detalhes nos capítulos 3 e 9
Introduction to Information Retrieval
Sec. 2.2.4
Lemmatization
 Reduzir formas variantes dos termos:
 E.g.,
 am, are, is  be
 car, cars, car's, cars'  car
 the boy's cars are different colors  the boy car be
different color
Introduction to Information Retrieval
Sec. 2.2.4
Stemming
 Reduzir os termos antes da indexação;
 Reconhecer os padrões de formação das palavras;
 Depende da língua;
 Baseado em regras;
 e.g., automate(s), automatic, automation todos reduzidos
para automat.
for example compressed
and compression are both
accepted as equivalent to
compress.
for exampl compress and
compress ar both accept
as equival to compress
Sec. 2.2.4
Introduction to Information Retrieval
Porter’s algorithm
 Commonest algorithm for stemming English
 Remocado dos sufixos das palvras;
 Baseado em regras de acordo com a lingua;
 Algoritmo procura pela maior sequencia de letras que casa
com uma regra.
 Exemplo:
Termo
engineering
engineered
engineer
Stem
engineer
engineer
engineer
Introduction to Information Retrieval
Regras Algoritmo de Porter




sses  ss
ies  i
ational  ate
tional  tion
 Regras dependem do tamanho da palavra
 (m>1) EMENT →
 replacement → replac
 cement → cement
Sec. 2.2.4
Introduction to Information Retrieval
Sec. 2.2.4
Algoritmo Porter língua portuguesa
Introduction to Information Retrieval
FASTER POSTINGS MERGES:
SKIP POINTERS/SKIP LISTS
Sec. 2.3
Introduction to Information Retrieval
Relembrando a “merge” básico
 Caminhamos por duas listas simultaneamente
comparando o valor das listas, quando encontramos
uma interseção adicionamos na lista de resultados.
2
8
2
4
8
41
1
2
3
8
48
11
64
17
Como podemos melhorar?
128 Brutus
21
31 Caesar
Sec. 2.3
Introduction to Information Retrieval
Query processing with skip pointers
128
41
2
4
8
41
64
128
31
11
1
48
2
3
8
11
17
21
31
Suponha que caminhamos nas duas listas ate achar a
interseção entre elas (ex. 8)
Nos então temos os valores 41 e 11. 11 e o menor.
Como o topo do lista e 31 e o ponteiro da outra lista e
41 podemos entao “escapar” para final da lista.
Introduction to Information Retrieval
PHRASE QUERIES AND POSITIONAL
INDEXES
Introduction to Information Retrieval
Consulta de frases
 Queremos consultar uma frase
 Exemplo: “stanford university” – como uma frase
 For this, it no longer suffices to store only
<term : docs> entries
Sec. 2.4
Introduction to Information Retrieval
Sec. 2.4.1
Primeira solução: Biword indexes
 Separamos pares dos termos contidos na frase e
criamos um índice para cada par;
 Exemplo do texto “Friends, Romans, Countrymen”
podemos gerar as biwords
 friends romans
 romans countrymen
 Cada uma das biwords é agora um termo do
dicionário.
Introduction to Information Retrieval
Sec. 2.4.1
Consultar frases longas
 Dividimos a frases em Biwords e aplicamos a
consulta booleana;
 Exemplo:
“stanford university palo alto “
Aplicando o conceito acima temos:
stanford university AND university palo AND palo alto
Introduction to Information Retrieval
Sec. 2.4.1
Extended biwords
 Dividimos os termos em Nomes (N) e
artigos/preposições (X).
 Chamamos uma string de terms NX*N como uma
extended biword.
 Cada extended biword é um novo termo no
dicionario.
 Exemplo: catcher in the rye
N
X X N
 Processo de consulta: analisá-lo em N’s and X’s
 Consulta pelo índice: catcher rye
Introduction to Information Retrieval
Sec. 2.4.1
Problemas para biword indexes
 Dicionário de Índices muito grande
 Inviável na pratica.
 Biword índices não são a solução-padrão (para todos os
biwords), mas pode ser parte de uma estratégia.
Introduction to Information Retrieval
Solução 2: Positional indexes
 Nas listas, armazenamos para cada termo a
posição(ões) que aparecem no documento:
<term, number of docs containing term;
doc1: position1, position2 … ;
doc2: position1, position2 … ;
etc.>
Sec. 2.4.2
Sec. 2.4.2
Introduction to Information Retrieval
Positional index exemplo
<be: 993427;
1: 7, 18, 33, 72, 86, 231;
2: 3, 149;
4: 17, 191, 291, 430, 434;
5: 363, 367, …>
Aparecem nos docs 1,2,4,5
Como consultar “to be
or not to be”?
 Be: aparece no documento 1 nas seguintes
posições: 7,18,33,72,86,231
 Mas agora precisamos lidar com mais do que
apenas termos em comuns em documentos
precisamos saber se estão próximos ou não.
Sec. 2.4.2
Introduction to Information Retrieval
Recuperando uma frase
 Extraímos o índice invertido para cada termo: to, be, or, not.
 Merge das listas doc:position enumerando todas as posições
com “to be or not to be”.
 to:
 2:1,17,74,222,551;
 4:8,16,190,429,433;
 7:13,23,191; ...
 be:
 1:17,19;
 4:17,191,291,430,434;
 5:14,19,101; ...
Em comum os documentos 4, em
seguida analisar as posições: nesse
exemplo temos mais próximos
429(to),430(be) e 433(to),434(be)
Introduction to Information Retrieval
Sec. 2.4.2
Tamanho do índice por posição
 Existem técnicas de compressão dos valores das
posições, será discutido no capitulo 5.
 Essa técnica aumenta substancialmente o espaço em
disco necessário para armazenamento dos índices e
posições.
 Grande vantagem dessa técnica é o poder de buscar
frases pela proximidade das palavras.
Introduction to Information Retrieval
Sec. 2.4.2
Regras
 Um índice por posição é de 2 a 4 vezes que um índice
não posicional
 Tamanho do índice por posição e de 35 a 50% do
volume do texto original.
 Obs.: Esses dados são baseados na língua inglesa.
Introduction to Information Retrieval
Resources for today’s lecture
 IIR 2
 MG 3.6, 4.3; MIR 7.2
 Porter’s stemmer:
http://www.tartarus.org/~martin/PorterStemmer/

Skip Lists theory: Pugh (1990)

 Multilevel skip lists give same O(log n) efficiency as trees
H.E. Williams, J. Zobel, and D. Bahle. 2004. “Fast Phrase
Querying with Combined Indexes”, ACM Transactions on
Information Systems.
http://www.seg.rmit.edu.au/research/research.php?author=4

D. Bahle, H. Williams, and J. Zobel. Efficient phrase querying with an
auxiliary index. SIGIR 2002, pp. 215-221.