Modelo booleano

Recuperação de Informação em Bases de Texto
Aula 2
1
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Suporta operações booleanas: AND, OR, NOT
– “Que documentos contêm as palavras sonho e
acção e não têm a palavra sonâmbolo.”
• sonho AND acção AND NOT sonâmbolo
2
Recuperação de Informação em Bases de Texto
• Modelo booleano
– sonho AND acção AND NOT sonâmbolo
– Abordagens:
• Força bruta (sem pré-processamento):
– 1. selecção dos documentos que contêm a
palavra “sonho”;
– 2. destes, selecção dos documentos que
contêm a palavra “acção”;
– 3. destes, selecção dos documentos que
não contêm a palavra “sonâmbolo”.
3
Recuperação de Informação em Bases de Texto
• Modelo booleano
– sonho AND acção AND NOT sonâmbolo
– Abordagens:
• Força bruta -> inviável para colecções de
documentos de dimensão média/grande.
• Pré-processamento dos textos
– Matriz de termos-documentos
4
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Matriz de termos-documentos
Livro do desassosego Mensagem
acção
1
0
sonho
1
1
sonâmbolo
0
0
5
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Matriz de termos-documentos
– Interrogação:
• sonho AND acção AND NOT sonâmbolo
• 11 AND 10 AND NOT 00
• 11 AND 10 AND 11
• 10
– Resposta: “Livro do desassossego” -- Fernando
Pessoa
6
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Resposta: “Livro do desassossego” -- Fernando
Pessoa
• “Tenho que escolher o que detesto - ou o
sonho, que a minha inteligência odeia, ou a
acção, que a minha sensibilidade repugna;
ou a acção, para que não nasci, ou o sonho,
para que ninguém nasceu.”
7
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Matriz de termos-documentos
• Suponhamos uma colecção com 1 milhão de
documentos, cada um com uma média de
1000 palavras, cada uma com uma média de
6 bytes -> 6GB;
• Suponhamos que existem cerca de 500.000
termos distintos na colecção;
• A matriz de termos-documentos terá 500.000
* 1 milhão de elementos = 500.000.000.000!
8
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Matriz de termos-documentos
• Não é viável representar todos os elementos!
• Mas o número de “1”s é -> 1.000.000 docs *
1000 palavra = 1.000.000.000
• Ou seja, 1/500 = 0.2% de “1”s e 99.8% de
“0”s
• A solução é representar somente a
informação positiva -> “inverted index”,
“inverted file”.
9
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Inverted index
• Para cada termo, guarda-se a lista dos
documentos que o contêm.
– “acção” -> “doc 1”.
– “sonho” -> “doc 1”; “doc 2”
• Implementação:
– Array
– Listas ligadas
– Listas ligadas ordenadas
10
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Como construir o “inverted index”?
• Identificar as palavras/tokens de cada
documento;
– “Tenho”; “que”; “escolher”; ...
• “Normalizar” essas palavras
– “ter”; “que”; “escolher”; ...
• Criação dos índices ordenados por
identificador do documento
– ter -> “doc 1”; “doc 3”
– ...
11
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Como construir o “inverted index”?
• O dicionário (conjunto de todos os termos)
deverá ter, para cada entrada:
– termo (string)
– nº de documentos que a contêm (tamanho
da lista apontada)
» (ter,2) -> “doc 1”; “doc 3”
12
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Como construir o “inverted index”?
• O dicionário pode ser implementado por:
– tabela de hash
– lista ordenada
– b-tree
– trie (árvore de prefixos)
– ...
13
Recuperação de Informação em Bases de Texto
• Modelo booleano
– O dicionário pode ser implementado por:
• tabela de hash
– acesso eficiente; “problemas” com
ordenação; problemas com alguns
operadores (wildcards: *, ?)
• lista ordenada
– acesso pouco eficiente;
14
Recuperação de Informação em Bases de Texto
• Modelo booleano
– O dicionário pode ser implementado por:
• b-tree
– acesso eficiente
• trie (árvore de prefixos)
– acesso “razoavelmente” eficiente
(dependendo da implementação)
– pesquisa por prefixação, com wildcards
(*, ?) simplificada
15
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Como processar as interrogações sobre
“inverted indexes”?
• sonho
– Lista de “doc ids” apontados pelo termo
“sonho” do dicionário.
• sonho AND acção
– Intersecção das listas de “doc ids”
» “acção” -> “doc 1”.
» “sonho” -> “doc 1”; “doc 2”
» “sonho” AND “acção” -> “doc 1”
16
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Como processar as interrogações sobre
“inverted indexes”?
• operador OR
– reunião de listas
• operador NOT
– complemento de listas/conjuntos
17
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Complexidade das operações booleanas sobre
“inverted indexes”?
• AND e OR são de complexidade linear com o
tamanho das listas, se os elementos tiverem
ordenados;
• NOT é um operador “caro” -> criar a lista
complemento -> complexidade linear com a
dimensão do dicionário!
18
Recuperação de Informação em Bases de Texto
• Modelo booleano
– AND(P1,P2) --> intersecção(lista(P1), lista(P2))
– intersecção(L1, L2)
• L = {}
• while L1 <> nil and L2 <> nil
– if (docID(first(L1)) = docID(first(L2)))
» add(L, first(L1)); L1++; L2++
– else if (docID(first(L1)) < docID(first(L2)))
» L1++
– else L2++
• return L
19
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Como optimizar o processamento das
interrogações?
• Sequências de ANDs
– Começar por calcular a intersecção das
listas com menor cardinalidade (a
intersecção só pode diminuir a
cardinalidade de um conjunto!)
– Usar a informação guardada no dicionário
sobre o número de documentos que
contêm o termo.
20
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Como optimizar o processamento das
interrogações?
• Estratégia geral:
– Transformar a interrogação numa
disjunção (ANDs) de expressões e
calcular as intersecções começando pela
expressão com menor cardinalidade
21
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Limitações/extensões:
• Expressões multi-palavra
– “Inverted indexes” devem guardar
informação sobre a posição da palavra no
documento;
– Alternativa: dicionário multi-palavra
22
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Limitações/extensões:
• Operadores de proximidade
– sonho perto_de acção
– “Inverted indexes” devem guardar
informação sobre a posição da palavra no
documento;
23
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Limitações/extensões:
• Estrutura dos documentos
– autor = “F. Pessoa” AND contém(texto,
sonho)
– “Inverted indexes” devem guardar
informação sobre os campos em que as
palavas surgem nos documentos.
24
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Limitações/extensões:
• Modelo não tem em conta a frequência de
ocorrência das palavras nos documentos
– maior frequência provavelmente implica
maior relevância
• Extensão ao modelo para os “inverted
indexes” guardarem a frequência de
ocorrência dos termos nos documentos
• Como usar esta informação (peso dos
termos) para ordenação dos resultados?
25
Recuperação de Informação em Bases de Texto
• Modelo booleano
– Limitações/extensões:
• Uso exclusivo de lógica booleana pode ser
uma limitação:
– sonho AND acção AND sonâmbolo
• Será que os documentos que contêm duas
das três palavras não deveriam ser
seleccionados, caso não haja nenhum que
contenha a totalidade dos termos?
26
Recuperação de Informação em Bases de Texto
• Como avaliar a qualidade do sistemas de RI?
– Precisão
• % de documentos seleccionados que são
relevantes
– Recall/cobertura/abrangência
• % de documentos relevantes que foi
seleccionado
– ...
27