Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
GSI024 - Organização e Recuperação de
Informação
Dicionários e recuperação tolerante
Marcelo Keese Albertini
2013-05
Recuperação booleana
1 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Conteúdo
1
Revisão
2
Dicionários
3
Consultas com caracter curinga
4
Distância de edição
5
Correção ortográfica
6
Soundex
Recuperação booleana
2 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Conteúdo
1
Revisão
2
Dicionários
3
Consultas com caracter curinga
4
Distância de edição
5
Correção ortográfica
6
Soundex
Recuperação booleana
3 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distinção entre tipo e token
Token – uma instância de uma palavra um termo em um
documento
Tipo – uma classe de equivalência de tokens
In June, the dog likes to chase the cat in the barn.
12 tokens, 9 tipos
Recuperação booleana
4 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Problemas na tokenização
O que são os delimitadores? Espaço? Apostófre? Hı́fen?
Para cada um desses: às vezes delimitam, às vezes sim
Não há espaços em vários idiomas! (e.g., Chinês)
Não há espaços em subtantivos compostos em Holandês,
Alemão, Sueco (Lebensversicherungsgesellschaftsangestellter)
Recuperação booleana
5 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Problemas com classe de equivalência
Um termo uma classe de equivalência de tokens
Como definir classes de equivalência?
Números (3/20/91 vs. 20/3/91)
Mudança de maiúscula/minúscula
Stemming, Stemmer de Porter
Análise morfológica: inflexão vs. derivação
Problemas de classe de equivalência em outros idiomas
Morfologias mais complexas
Finlandês: um verbo pode tem 12 mil formas diferentes
Acentos, tremas
Recuperação booleana
6 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Salta ponteiros
16
Brutus
2 4 8 16 19 23 28 43
5
Caesar
Recuperação booleana
72
28
51
98
1 2 3 5 8 41 51 60 71
7 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índices posicionais
Listas de ı́ndices não posicionais: cada referência é um simples docID
Listas de ı́ndices posicionais: cada referência é um docID e uma lista de
posições
Exemplo de consulta: “to1 be2 or3 not4 to5 be6 ”
to, 993427:
h 1: h7, 18, 33, 72, 86, 231i;
2: h1, 17, 74, 222, 255i;
4: h8, 16, 190, 429, 433i;
5: h363, 367i;
7: h13, 23, 191i; . . . i
be, 178239:
h 1: h17, 25i;
4: h17, 191, 291, 430, 434i;
5: h14, 19, 101i; . . . i
Documento 4 é um resultado!
Recuperação booleana
8 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índices posicionais
Com um ı́ndice posicional, podemos responder consultas de
expressões.
Com um ı́ndice posicional, podemos responder consultas de
proximidades.
Recuperação booleana
9 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Conteúdo
Recuperação booleana
10 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Conteúdo
Recuperação tolerante: o que fazer se não há correspondencia
exata entre termos de consulta e termos de documentos
Recuperação booleana
10 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Conteúdo
Recuperação tolerante: o que fazer se não há correspondencia
exata entre termos de consulta e termos de documentos
Consultas com caracteres curingas
Recuperação booleana
10 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Conteúdo
Recuperação tolerante: o que fazer se não há correspondencia
exata entre termos de consulta e termos de documentos
Consultas com caracteres curingas
Correção ortográfica
Recuperação booleana
10 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Conteúdo
1
Revisão
2
Dicionários
3
Consultas com caracter curinga
4
Distância de edição
5
Correção ortográfica
6
Soundex
Recuperação booleana
11 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índice invertido
Para cada termo t, armazenamos uma lista de todos os
documentos que contém t.
Brutus
−→
1
2
4
11
31
45
173
174
César
−→
1
2
4
5
6
16
57
132
Calpúrnia
−→
2
31
54
101
...
..
.
| {z }
dicionário
Recuperação booleana
|
{z
referências
}
12 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índice invertido
Para cada termo t, armazenamos uma lista de todos os
documentos que contém t.
Brutus
−→
1
2
4
11
31
45
173
174
César
−→
1
2
4
5
6
16
57
132
Calpúrnia
−→
2
31
54
101
...
..
.
| {z }
dicionário
Recuperação booleana
|
{z
referências
}
12 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Dicionários
Um dicionário é uma estrutura de dados para armazenar o
vocabulário de termos
Recuperação booleana
13 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Dicionários
Um dicionário é uma estrutura de dados para armazenar o
vocabulário de termos
Vocabulário: os dados
Recuperação booleana
13 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Dicionários
Um dicionário é uma estrutura de dados para armazenar o
vocabulário de termos
Vocabulário: os dados
dicionário: a estrutura de dados para armazenar um
vocabulário
Recuperação booleana
13 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
dicionário como um array de entradas de tamanho fixo
Para cada termo, precisamos armazenar os seguintes itens:
Recuperação booleana
14 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
dicionário como um array de entradas de tamanho fixo
Para cada termo, precisamos armazenar os seguintes itens:
frequência em documentos
Recuperação booleana
14 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
dicionário como um array de entradas de tamanho fixo
Para cada termo, precisamos armazenar os seguintes itens:
frequência em documentos
ponteiro para lista de ı́ndices
Recuperação booleana
14 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
dicionário como um array de entradas de tamanho fixo
Para cada termo, precisamos armazenar os seguintes itens:
frequência em documentos
ponteiro para lista de ı́ndices
...
Recuperação booleana
14 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
dicionário como um array de entradas de tamanho fixo
Para cada termo, precisamos armazenar os seguintes itens:
frequência em documentos
ponteiro para lista de ı́ndices
...
Assuma no momento que podemos armazenar essa
informação em uma estrutura de tamanho fixo
Recuperação booleana
14 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
dicionário como um array de entradas de tamanho fixo
Para cada termo, precisamos armazenar os seguintes itens:
frequência em documentos
ponteiro para lista de ı́ndices
...
Assuma no momento que podemos armazenar essa
informação em uma estrutura de tamanho fixo
Assuma que armazenamos essas estruturas em um array
Recuperação booleana
14 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
dicionário como um array de entradas de tamanho fixo
termo
espaço necessário:
a
aachen
...
zulu
20 bytes
frequência
no
documento
656,265
65
...
221
4 bytes
ponteiro
para lista de
referências
−→
−→
...
−→
4 bytes
Como procurar por um termo qi nesse array durante o tempo da
consulta? Isso é, qual estrutura de dados usamos para localizar a
entrada (linha) em um array onde qi é armazenado?
Recuperação booleana
15 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Estrutura de dados para procurar por termo
Duas classes principais de estruturas de dados: hashes e
árvores
Recuperação booleana
16 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Estrutura de dados para procurar por termo
Duas classes principais de estruturas de dados: hashes e
árvores
Alguns ORI usam hashes, outros, árvores
Recuperação booleana
16 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Estrutura de dados para procurar por termo
Duas classes principais de estruturas de dados: hashes e
árvores
Alguns ORI usam hashes, outros, árvores
Critério para quando usar hashes vs. árvores:
Recuperação booleana
16 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Estrutura de dados para procurar por termo
Duas classes principais de estruturas de dados: hashes e
árvores
Alguns ORI usam hashes, outros, árvores
Critério para quando usar hashes vs. árvores:
Há um número fixo de termo ou esses aumentarão?
Recuperação booleana
16 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Estrutura de dados para procurar por termo
Duas classes principais de estruturas de dados: hashes e
árvores
Alguns ORI usam hashes, outros, árvores
Critério para quando usar hashes vs. árvores:
Há um número fixo de termo ou esses aumentarão?
Quais são as frequências relativas com as quais várias chaves
serão acessados?
Recuperação booleana
16 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Estrutura de dados para procurar por termo
Duas classes principais de estruturas de dados: hashes e
árvores
Alguns ORI usam hashes, outros, árvores
Critério para quando usar hashes vs. árvores:
Há um número fixo de termo ou esses aumentarão?
Quais são as frequências relativas com as quais várias chaves
serão acessados?
Quantos termos são prováveis para ter?
Recuperação booleana
16 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Hashes
Cada termo no vocabulário é referenciado por uma chave-hash
Recuperação booleana
17 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Hashes
Cada termo no vocabulário é referenciado por uma chave-hash
Tentar evitar colisões
Recuperação booleana
17 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Hashes
Cada termo no vocabulário é referenciado por uma chave-hash
Tentar evitar colisões
Durante a consulta, faça: obtenha chave hash do termo, trate
colisões, localizar entrada no array de tamanho fixo
Recuperação booleana
17 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Hashes
Cada termo no vocabulário é referenciado por uma chave-hash
Tentar evitar colisões
Durante a consulta, faça: obtenha chave hash do termo, trate
colisões, localizar entrada no array de tamanho fixo
Pros: buscar em uma hash é mais rápido que uma busca em
uma árvore
Recuperação booleana
17 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Hashes
Cada termo no vocabulário é referenciado por uma chave-hash
Tentar evitar colisões
Durante a consulta, faça: obtenha chave hash do termo, trate
colisões, localizar entrada no array de tamanho fixo
Pros: buscar em uma hash é mais rápido que uma busca em
uma árvore
tempo de busca é constante
Recuperação booleana
17 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Hashes
Cada termo no vocabulário é referenciado por uma chave-hash
Tentar evitar colisões
Durante a consulta, faça: obtenha chave hash do termo, trate
colisões, localizar entrada no array de tamanho fixo
Pros: buscar em uma hash é mais rápido que uma busca em
uma árvore
tempo de busca é constante
Contras
Recuperação booleana
17 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Hashes
Cada termo no vocabulário é referenciado por uma chave-hash
Tentar evitar colisões
Durante a consulta, faça: obtenha chave hash do termo, trate
colisões, localizar entrada no array de tamanho fixo
Pros: buscar em uma hash é mais rápido que uma busca em
uma árvore
tempo de busca é constante
Contras
não permite encontrar variantes (resume vs. résumé)
Recuperação booleana
17 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Hashes
Cada termo no vocabulário é referenciado por uma chave-hash
Tentar evitar colisões
Durante a consulta, faça: obtenha chave hash do termo, trate
colisões, localizar entrada no array de tamanho fixo
Pros: buscar em uma hash é mais rápido que uma busca em
uma árvore
tempo de busca é constante
Contras
não permite encontrar variantes (resume vs. résumé)
sem busca de prefixo (todos os termos iniciando com automat)
Recuperação booleana
17 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Hashes
Cada termo no vocabulário é referenciado por uma chave-hash
Tentar evitar colisões
Durante a consulta, faça: obtenha chave hash do termo, trate
colisões, localizar entrada no array de tamanho fixo
Pros: buscar em uma hash é mais rápido que uma busca em
uma árvore
tempo de busca é constante
Contras
não permite encontrar variantes (resume vs. résumé)
sem busca de prefixo (todos os termos iniciando com automat)
necessário para reconstruir tabela hash periodicamente se
vocabulário aumenta ao longo do tempo
Recuperação booleana
17 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Árvores
Árvores resolvem o problema com prefixos (encontre todos os
termos iniciando com automat).
Recuperação booleana
18 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Árvores
Árvores resolvem o problema com prefixos (encontre todos os
termos iniciando com automat).
Árvore mais simples: árvore binária
Recuperação booleana
18 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Árvores
Árvores resolvem o problema com prefixos (encontre todos os
termos iniciando com automat).
Árvore mais simples: árvore binária
Busca é ligeiramente mais lento que com hash: O(log M),
onde M é o tamanho do vocabulário
Recuperação booleana
18 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Árvores
Árvores resolvem o problema com prefixos (encontre todos os
termos iniciando com automat).
Árvore mais simples: árvore binária
Busca é ligeiramente mais lento que com hash: O(log M),
onde M é o tamanho do vocabulário
O(log M) somente vale para árvore balanceada
Recuperação booleana
18 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Árvores
Árvores resolvem o problema com prefixos (encontre todos os
termos iniciando com automat).
Árvore mais simples: árvore binária
Busca é ligeiramente mais lento que com hash: O(log M),
onde M é o tamanho do vocabulário
O(log M) somente vale para árvore balanceada
Rebalanceamento de árvores binárias é caro
Recuperação booleana
18 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Árvores
Árvores resolvem o problema com prefixos (encontre todos os
termos iniciando com automat).
Árvore mais simples: árvore binária
Busca é ligeiramente mais lento que com hash: O(log M),
onde M é o tamanho do vocabulário
O(log M) somente vale para árvore balanceada
Rebalanceamento de árvores binárias é caro
Árvores B mitigam o problema de rebalanceamento
Recuperação booleana
18 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Árvores
Árvores resolvem o problema com prefixos (encontre todos os
termos iniciando com automat).
Árvore mais simples: árvore binária
Busca é ligeiramente mais lento que com hash: O(log M),
onde M é o tamanho do vocabulário
O(log M) somente vale para árvore balanceada
Rebalanceamento de árvores binárias é caro
Árvores B mitigam o problema de rebalanceamento
Definição de árvore-B: todo nó interno tem um número de
filhos no intervalo [a, b] onde a, b são números inteiros
positivos apropriados , e.g., [2, 4].
Recuperação booleana
18 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Árvore binária
Recuperação booleana
19 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Árvore B
Recuperação booleana
20 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Conteúdo
1
Revisão
2
Dicionários
3
Consultas com caracter curinga
4
Distância de edição
5
Correção ortográfica
6
Soundex
Recuperação booleana
21 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Consultas com caracter curinga
mon*: encontrar documentos com termos começando com
mon
Recuperação booleana
22 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Consultas com caracter curinga
mon*: encontrar documentos com termos começando com
mon
Fácil com dicionário baseado em árvore B: recuperar todos
termos t no intervalo: mon ≤ t < moo
Recuperação booleana
22 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Consultas com caracter curinga
mon*: encontrar documentos com termos começando com
mon
Fácil com dicionário baseado em árvore B: recuperar todos
termos t no intervalo: mon ≤ t < moo
*mon: encontrar todos documentos com termos terminando
com mon
Recuperação booleana
22 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Consultas com caracter curinga
mon*: encontrar documentos com termos começando com
mon
Fácil com dicionário baseado em árvore B: recuperar todos
termos t no intervalo: mon ≤ t < moo
*mon: encontrar todos documentos com termos terminando
com mon
Mantém uma árvore adicional para termos ao contrário
Recuperação booleana
22 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Consultas com caracter curinga
mon*: encontrar documentos com termos começando com
mon
Fácil com dicionário baseado em árvore B: recuperar todos
termos t no intervalo: mon ≤ t < moo
*mon: encontrar todos documentos com termos terminando
com mon
Mantém uma árvore adicional para termos ao contrário
Então recupera todos termos t no intervalo: nom ≤ t < non
Recuperação booleana
22 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Consultas com caracter curinga
mon*: encontrar documentos com termos começando com
mon
Fácil com dicionário baseado em árvore B: recuperar todos
termos t no intervalo: mon ≤ t < moo
*mon: encontrar todos documentos com termos terminando
com mon
Mantém uma árvore adicional para termos ao contrário
Então recupera todos termos t no intervalo: nom ≤ t < non
Resultado: um conjunto de termos que correspondem ao uma
consulta com caracter curinga
Recuperação booleana
22 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Consultas com caracter curinga
mon*: encontrar documentos com termos começando com
mon
Fácil com dicionário baseado em árvore B: recuperar todos
termos t no intervalo: mon ≤ t < moo
*mon: encontrar todos documentos com termos terminando
com mon
Mantém uma árvore adicional para termos ao contrário
Então recupera todos termos t no intervalo: nom ≤ t < non
Resultado: um conjunto de termos que correspondem ao uma
consulta com caracter curinga
Então recupere documentos que contém quaisquer dos termos
Recuperação booleana
22 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Como manipular * no meio de um termo
Exemplo: m*nchen
Recuperação booleana
23 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Como manipular * no meio de um termo
Exemplo: m*nchen
Podemos procurar m* e *nchen na árvore-B e interseccionar
os dois conjuntos
Recuperação booleana
23 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Como manipular * no meio de um termo
Exemplo: m*nchen
Podemos procurar m* e *nchen na árvore-B e interseccionar
os dois conjuntos
Custoso
Recuperação booleana
23 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Como manipular * no meio de um termo
Exemplo: m*nchen
Podemos procurar m* e *nchen na árvore-B e interseccionar
os dois conjuntos
Custoso
Alternativa: ı́ndice permuterm
Recuperação booleana
23 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Como manipular * no meio de um termo
Exemplo: m*nchen
Podemos procurar m* e *nchen na árvore-B e interseccionar
os dois conjuntos
Custoso
Alternativa: ı́ndice permuterm
Ideia básica: rotacionar toda consulta com caracter curinga,
tal que * ocorre no final
Recuperação booleana
23 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Como manipular * no meio de um termo
Exemplo: m*nchen
Podemos procurar m* e *nchen na árvore-B e interseccionar
os dois conjuntos
Custoso
Alternativa: ı́ndice permuterm
Ideia básica: rotacionar toda consulta com caracter curinga,
tal que * ocorre no final
Guardar cada dessas rotações no dicionário, e.g., em uma
árvore-B
Recuperação booleana
23 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índice permuterm
Para termo hello: adicionar hello$, ello$h, llo$he, lo$hel, e
o$hell para a árvore-B onde $ é um sı́mbolo especial
Recuperação booleana
24 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Permuterm → termo mapeado
Recuperação booleana
25 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índice permuterm
Para hello, armazenamos: hello$, ello$h, llo$he, lo$hel, e
o$hell
Recuperação booleana
26 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índice permuterm
Para hello, armazenamos: hello$, ello$h, llo$he, lo$hel, e
o$hell
Consultas
Recuperação booleana
26 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índice permuterm
Para hello, armazenamos: hello$, ello$h, llo$he, lo$hel, e
o$hell
Consultas
Para X, busca por X$
Recuperação booleana
26 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índice permuterm
Para hello, armazenamos: hello$, ello$h, llo$he, lo$hel, e
o$hell
Consultas
Para X, busca por X$
Para X*, busca por $X*
Recuperação booleana
26 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índice permuterm
Para hello, armazenamos: hello$, ello$h, llo$he, lo$hel, e
o$hell
Consultas
Para X, busca por X$
Para X*, busca por $X*
Para *X, busca por X$*
Recuperação booleana
26 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índice permuterm
Para hello, armazenamos: hello$, ello$h, llo$he, lo$hel, e
o$hell
Consultas
Para
Para
Para
Para
Recuperação booleana
X, busca por X$
X*, busca por $X*
*X, busca por X$*
*X*, busca por X*
26 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índice permuterm
Para hello, armazenamos: hello$, ello$h, llo$he, lo$hel, e
o$hell
Consultas
Para
Para
Para
Para
Para
Recuperação booleana
X, busca por X$
X*, busca por $X*
*X, busca por X$*
*X*, busca por X*
X*Y, busca por Y$X*
26 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índice permuterm
Para hello, armazenamos: hello$, ello$h, llo$he, lo$hel, e
o$hell
Consultas
Para X, busca por X$
Para X*, busca por $X*
Para *X, busca por X$*
Para *X*, busca por X*
Para X*Y, busca por Y$X*
Exemplo: para hel*o, busca o$hel*
Recuperação booleana
26 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índice permuterm
Para hello, armazenamos: hello$, ello$h, llo$he, lo$hel, e
o$hell
Consultas
Para X, busca por X$
Para X*, busca por $X*
Para *X, busca por X$*
Para *X*, busca por X*
Para X*Y, busca por Y$X*
Exemplo: para hel*o, busca o$hel*
Índice permuterm seria melhor chamado de uma árvore
permuterm
Recuperação booleana
26 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índice permuterm
Para hello, armazenamos: hello$, ello$h, llo$he, lo$hel, e
o$hell
Consultas
Para X, busca por X$
Para X*, busca por $X*
Para *X, busca por X$*
Para *X*, busca por X*
Para X*Y, busca por Y$X*
Exemplo: para hel*o, busca o$hel*
Índice permuterm seria melhor chamado de uma árvore
permuterm
Mas ı́ndice permuterm é um nomais comum
Recuperação booleana
26 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processar uma busca no ı́ndice permuterm
Rotacionar caractere curinga para a direita
Recuperação booleana
27 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processar uma busca no ı́ndice permuterm
Rotacionar caractere curinga para a direita
Usar busca com árvore B como antes
Recuperação booleana
27 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processar uma busca no ı́ndice permuterm
Rotacionar caractere curinga para a direita
Usar busca com árvore B como antes
Problema: permuterm mais que quadriplica o tamanho do
dicionário comparado a uma árvore B normal (empı́rico)
Recuperação booleana
27 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índices k-grama
Mais eficiente em relação ao espaço que ı́ndice permuterm
Recuperação booleana
28 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índices k-grama
Mais eficiente em relação ao espaço que ı́ndice permuterm
Enumerar todos k-grama caracteres (sequência de k)
ocorrendo em um termo
Recuperação booleana
28 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índices k-grama
Mais eficiente em relação ao espaço que ı́ndice permuterm
Enumerar todos k-grama caracteres (sequência de k)
ocorrendo em um termo
2-gramas são chamados bigramas.
Recuperação booleana
28 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índices k-grama
Mais eficiente em relação ao espaço que ı́ndice permuterm
Enumerar todos k-grama caracteres (sequência de k)
ocorrendo em um termo
2-gramas são chamados bigramas.
Exemplo: de April is the cruelest month temos os bigramas:
$a ap pr ri il l$ $i is s$ $t th he e$ $c cr ru ue el le es st t$ $m
mo on nt h$
Recuperação booleana
28 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índices k-grama
Mais eficiente em relação ao espaço que ı́ndice permuterm
Enumerar todos k-grama caracteres (sequência de k)
ocorrendo em um termo
2-gramas são chamados bigramas.
Exemplo: de April is the cruelest month temos os bigramas:
$a ap pr ri il l$ $i is s$ $t th he e$ $c cr ru ue el le es st t$ $m
mo on nt h$
$ é um sı́mbolo delimitador de palavras, como antes
Recuperação booleana
28 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índices k-grama
Mais eficiente em relação ao espaço que ı́ndice permuterm
Enumerar todos k-grama caracteres (sequência de k)
ocorrendo em um termo
2-gramas são chamados bigramas.
Exemplo: de April is the cruelest month temos os bigramas:
$a ap pr ri il l$ $i is s$ $t th he e$ $c cr ru ue el le es st t$ $m
mo on nt h$
$ é um sı́mbolo delimitador de palavras, como antes
Manter um ı́ndice invertido a partir de bigramas para os
termos que têm o bigrama
Recuperação booleana
28 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Lista de ı́ndices em um ı́ndice invertido com 3-gram
etr
Recuperação booleana
- beetroot - metric
- petrify
- retrieval
29 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
ı́ndices k-gramas (bigrama, trigrama, . . . )
Note que agora tem dois diferentes tipos de ı́ndices invertidos
Recuperação booleana
30 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
ı́ndices k-gramas (bigrama, trigrama, . . . )
Note que agora tem dois diferentes tipos de ı́ndices invertidos
O ı́ndice invertido de termos-documentos para encontrar
documentos baseados em uma consulta de termos
Recuperação booleana
30 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
ı́ndices k-gramas (bigrama, trigrama, . . . )
Note que agora tem dois diferentes tipos de ı́ndices invertidos
O ı́ndice invertido de termos-documentos para encontrar
documentos baseados em uma consulta de termos
O ı́ndice de k-grams para encontrar termos baseados em uma
consulta que consiste de k-grams
Recuperação booleana
30 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processar termos com caractere curinga em um ı́ndice
bigrama
Consulta mon* agora pode ser executada como:
$m and mo and on
Recuperação booleana
31 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processar termos com caractere curinga em um ı́ndice
bigrama
Consulta mon* agora pode ser executada como:
$m and mo and on
Obtemos todos termos com o prefixo mon . . .
Recuperação booleana
31 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processar termos com caractere curinga em um ı́ndice
bigrama
Consulta mon* agora pode ser executada como:
$m and mo and on
Obtemos todos termos com o prefixo mon . . .
. . . mas também muitos “falsos positivos” como moon.
Recuperação booleana
31 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processar termos com caractere curinga em um ı́ndice
bigrama
Consulta mon* agora pode ser executada como:
$m and mo and on
Obtemos todos termos com o prefixo mon . . .
. . . mas também muitos “falsos positivos” como moon.
Nós devemos pós-processar esses termos de acordo com a
consulta
Recuperação booleana
31 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processar termos com caractere curinga em um ı́ndice
bigrama
Consulta mon* agora pode ser executada como:
$m and mo and on
Obtemos todos termos com o prefixo mon . . .
. . . mas também muitos “falsos positivos” como moon.
Nós devemos pós-processar esses termos de acordo com a
consulta
Termos restantes são então buscados no ı́ndice invertido de
termos-documentos
Recuperação booleana
31 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processar termos com caractere curinga em um ı́ndice
bigrama
Consulta mon* agora pode ser executada como:
$m and mo and on
Obtemos todos termos com o prefixo mon . . .
. . . mas também muitos “falsos positivos” como moon.
Nós devemos pós-processar esses termos de acordo com a
consulta
Termos restantes são então buscados no ı́ndice invertido de
termos-documentos
ı́ndice k-gram vs. ı́ndice permuterm
Recuperação booleana
31 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processar termos com caractere curinga em um ı́ndice
bigrama
Consulta mon* agora pode ser executada como:
$m and mo and on
Obtemos todos termos com o prefixo mon . . .
. . . mas também muitos “falsos positivos” como moon.
Nós devemos pós-processar esses termos de acordo com a
consulta
Termos restantes são então buscados no ı́ndice invertido de
termos-documentos
ı́ndice k-gram vs. ı́ndice permuterm
ı́ndice k-gram é mais eficiente em relação ao espaço
Recuperação booleana
31 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processar termos com caractere curinga em um ı́ndice
bigrama
Consulta mon* agora pode ser executada como:
$m and mo and on
Obtemos todos termos com o prefixo mon . . .
. . . mas também muitos “falsos positivos” como moon.
Nós devemos pós-processar esses termos de acordo com a
consulta
Termos restantes são então buscados no ı́ndice invertido de
termos-documentos
ı́ndice k-gram vs. ı́ndice permuterm
ı́ndice k-gram é mais eficiente em relação ao espaço
ı́ndice permuterm index não requer pós-processamento
Recuperação booleana
31 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Exercı́cio
Recuperação booleana
32 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Exercı́cio
Google tem um capacidade muito limitada para consultas com
caractere curinga
Recuperação booleana
32 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Exercı́cio
Google tem um capacidade muito limitada para consultas com
caractere curinga
Por exemplo, essa consulta não funciona bem no Google:
[gen* universit*]
Recuperação booleana
32 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Exercı́cio
Google tem um capacidade muito limitada para consultas com
caractere curinga
Por exemplo, essa consulta não funciona bem no Google:
[gen* universit*]
Intenção: busca-se pela Universidade de Geneva, mas não se
sabe os acentos para as palavras “universite” e “geneva” em
francês
Recuperação booleana
32 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Exercı́cio
Google tem um capacidade muito limitada para consultas com
caractere curinga
Por exemplo, essa consulta não funciona bem no Google:
[gen* universit*]
Intenção: busca-se pela Universidade de Geneva, mas não se
sabe os acentos para as palavras “universite” e “geneva” em
francês
Google: operador * funciona somente com palavras completas
entre aspas duplas “quem vê * * * *”
Recuperação booleana
32 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Exercı́cio
Google tem um capacidade muito limitada para consultas com
caractere curinga
Por exemplo, essa consulta não funciona bem no Google:
[gen* universit*]
Intenção: busca-se pela Universidade de Geneva, mas não se
sabe os acentos para as palavras “universite” e “geneva” em
francês
Google: operador * funciona somente com palavras completas
entre aspas duplas “quem vê * * * *”
Recuperação booleana
32 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Exercı́cio
Google tem um capacidade muito limitada para consultas com
caractere curinga
Por exemplo, essa consulta não funciona bem no Google:
[gen* universit*]
Intenção: busca-se pela Universidade de Geneva, mas não se
sabe os acentos para as palavras “universite” e “geneva” em
francês
Google: operador * funciona somente com palavras completas
entre aspas duplas “quem vê * * * *”
Porque o Google não suporta * de maneira completa?
Recuperação booleana
32 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processando consultas com curingas no ı́ndices de
termos-documentos
Recuperação booleana
33 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processando consultas com curingas no ı́ndices de
termos-documentos
Problema 1: precisamos executar um grande número de
consultas booelanas
Recuperação booleana
33 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processando consultas com curingas no ı́ndices de
termos-documentos
Problema 1: precisamos executar um grande número de
consultas booelanas
Semântica: conjução de disjunções
Recuperação booleana
33 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processando consultas com curingas no ı́ndices de
termos-documentos
Problema 1: precisamos executar um grande número de
consultas booelanas
Semântica: conjução de disjunções
Para [gen* universit*]: geneva university or geneva université
or genève university or genève université or general
universities or . . .
Recuperação booleana
33 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processando consultas com curingas no ı́ndices de
termos-documentos
Problema 1: precisamos executar um grande número de
consultas booelanas
Semântica: conjução de disjunções
Para [gen* universit*]: geneva university or geneva université
or genève university or genève université or general
universities or . . .
Muito caro
Recuperação booleana
33 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processando consultas com curingas no ı́ndices de
termos-documentos
Problema 1: precisamos executar um grande número de
consultas booelanas
Semântica: conjução de disjunções
Para [gen* universit*]: geneva university or geneva université
or genève university or genève université or general
universities or . . .
Muito caro
Problema 2: Usuários odeiam digitar
Recuperação booleana
33 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processando consultas com curingas no ı́ndices de
termos-documentos
Problema 1: precisamos executar um grande número de
consultas booelanas
Semântica: conjução de disjunções
Para [gen* universit*]: geneva university or geneva université
or genève university or genève université or general
universities or . . .
Muito caro
Problema 2: Usuários odeiam digitar
Se consultas como [teor* pitag*] para [teorema de pitágoras]
são permitidas, usuários vão usar bastante
Recuperação booleana
33 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processando consultas com curingas no ı́ndices de
termos-documentos
Problema 1: precisamos executar um grande número de
consultas booelanas
Semântica: conjução de disjunções
Para [gen* universit*]: geneva university or geneva université
or genève university or genève université or general
universities or . . .
Muito caro
Problema 2: Usuários odeiam digitar
Se consultas como [teor* pitag*] para [teorema de pitágoras]
são permitidas, usuários vão usar bastante
Isso potencialmente aumenta o custo de respostas
Recuperação booleana
33 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Processando consultas com curingas no ı́ndices de
termos-documentos
Problema 1: precisamos executar um grande número de
consultas booelanas
Semântica: conjução de disjunções
Para [gen* universit*]: geneva university or geneva université
or genève university or genève université or general
universities or . . .
Muito caro
Problema 2: Usuários odeiam digitar
Se consultas como [teor* pitag*] para [teorema de pitágoras]
são permitidas, usuários vão usar bastante
Isso potencialmente aumenta o custo de respostas
Custo amenizado por “Google suggest”: sugestões durante
escrita da busca
Recuperação booleana
33 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Conteúdo
1
Revisão
2
Dicionários
3
Consultas com caracter curinga
4
Distância de edição
5
Correção ortográfica
6
Soundex
Recuperação booleana
34 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica
Recuperação booleana
35 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica
Dois principais usos
Recuperação booleana
35 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica
Dois principais usos
Correção de documentos na indexação
Recuperação booleana
35 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica
Dois principais usos
Correção de documentos na indexação
Correção da busca de usuários
Recuperação booleana
35 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica
Dois principais usos
Correção de documentos na indexação
Correção da busca de usuários
2 métodos para correção
Recuperação booleana
35 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica
Dois principais usos
Correção de documentos na indexação
Correção da busca de usuários
2 métodos para correção
Correção de palavra isolada
Recuperação booleana
35 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica
Dois principais usos
Correção de documentos na indexação
Correção da busca de usuários
2 métodos para correção
Correção de palavra isolada
Verificar cada palavra individualmente por erros
Recuperação booleana
35 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica
Dois principais usos
Correção de documentos na indexação
Correção da busca de usuários
2 métodos para correção
Correção de palavra isolada
Verificar cada palavra individualmente por erros
Não corrige erros que resultam em palavra correta: um
asteroide caiu do seu
Recuperação booleana
35 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica
Dois principais usos
Correção de documentos na indexação
Correção da busca de usuários
2 métodos para correção
Correção de palavra isolada
Verificar cada palavra individualmente por erros
Não corrige erros que resultam em palavra correta: um
asteroide caiu do seu
Correção sensı́vel a contexto
Recuperação booleana
35 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica
Dois principais usos
Correção de documentos na indexação
Correção da busca de usuários
2 métodos para correção
Correção de palavra isolada
Verificar cada palavra individualmente por erros
Não corrige erros que resultam em palavra correta: um
asteroide caiu do seu
Correção sensı́vel a contexto
Observa palavras ao redor
Recuperação booleana
35 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica
Dois principais usos
Correção de documentos na indexação
Correção da busca de usuários
2 métodos para correção
Correção de palavra isolada
Verificar cada palavra individualmente por erros
Não corrige erros que resultam em palavra correta: um
asteroide caiu do seu
Correção sensı́vel a contexto
Observa palavras ao redor
pode corrigir seu/céu
Recuperação booleana
35 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Corrigindo documentos
Recuperação booleana
36 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Corrigindo documentos
Não estamos interessados em correção iterativa e.g.
processador de textos
Recuperação booleana
36 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Corrigindo documentos
Não estamos interessados em correção iterativa e.g.
processador de textos
Em ORI, usamos correção de documentos principalmente para
documentos digitalizados com scanner e OCR
Recuperação booleana
36 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Corrigindo documentos
Não estamos interessados em correção iterativa e.g.
processador de textos
Em ORI, usamos correção de documentos principalmente para
documentos digitalizados com scanner e OCR
A filosofia básica em ORI é: não alterar documentos
Recuperação booleana
36 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Corrigindo consultas
Recuperação booleana
37 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Corrigindo consultas
Primeiro: correção de palavras independentes
Recuperação booleana
37 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Corrigindo consultas
Primeiro: correção de palavras independentes
Premissa 1: existe uma lista de palavras “corretas” da onde
vêm as correções
Recuperação booleana
37 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Corrigindo consultas
Primeiro: correção de palavras independentes
Premissa 1: existe uma lista de palavras “corretas” da onde
vêm as correções
Premissa 2: temos um meio de computar a distância entre a
palavra errada e a correta
Recuperação booleana
37 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Corrigindo consultas
Primeiro: correção de palavras independentes
Premissa 1: existe uma lista de palavras “corretas” da onde
vêm as correções
Premissa 2: temos um meio de computar a distância entre a
palavra errada e a correta
Algoritmo de correção simples: retornar a palavra correta que
tem a menor distância para a palavra errada
Recuperação booleana
37 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Corrigindo consultas
Primeiro: correção de palavras independentes
Premissa 1: existe uma lista de palavras “corretas” da onde
vêm as correções
Premissa 2: temos um meio de computar a distância entre a
palavra errada e a correta
Algoritmo de correção simples: retornar a palavra correta que
tem a menor distância para a palavra errada
Exemplo: infomação → informação
Recuperação booleana
37 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Corrigindo consultas
Primeiro: correção de palavras independentes
Premissa 1: existe uma lista de palavras “corretas” da onde
vêm as correções
Premissa 2: temos um meio de computar a distância entre a
palavra errada e a correta
Algoritmo de correção simples: retornar a palavra correta que
tem a menor distância para a palavra errada
Exemplo: infomação → informação
Para a lista de palavras corretas, podemos usar o vocabulário
de todas as palavras que ocorrem na nossa coleção
Recuperação booleana
37 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Corrigindo consultas
Primeiro: correção de palavras independentes
Premissa 1: existe uma lista de palavras “corretas” da onde
vêm as correções
Premissa 2: temos um meio de computar a distância entre a
palavra errada e a correta
Algoritmo de correção simples: retornar a palavra correta que
tem a menor distância para a palavra errada
Exemplo: infomação → informação
Para a lista de palavras corretas, podemos usar o vocabulário
de todas as palavras que ocorrem na nossa coleção
Porque isso é problemático?
Recuperação booleana
37 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Alternativas para o uso do vocabulário de termos
Recuperação booleana
38 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Alternativas para o uso do vocabulário de termos
Um dicionário padrão
Recuperação booleana
38 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Alternativas para o uso do vocabulário de termos
Um dicionário padrão
Um dicionário especializado (para sistemas de ORI
especializados: e.g. advocacia
Recuperação booleana
38 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Alternativas para o uso do vocabulário de termos
Um dicionário padrão
Um dicionário especializado (para sistemas de ORI
especializados: e.g. advocacia
O vocabulário de termos da coleção apropriadamente
ponderado (pela frequência)
Recuperação booleana
38 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância entre palavra errada e correta
Recuperação booleana
39 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância entre palavra errada e correta
Várias alternativas
Recuperação booleana
39 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância entre palavra errada e correta
Várias alternativas
Distância de edição e de Levenshtein
Recuperação booleana
39 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância entre palavra errada e correta
Várias alternativas
Distância de edição e de Levenshtein
Distância de edição ponderada
Recuperação booleana
39 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância entre palavra errada e correta
Várias alternativas
Distância de edição e de Levenshtein
Distância de edição ponderada
Sobreposição de k-gramas
Recuperação booleana
39 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de edição
Recuperação booleana
40 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de edição
A distância de edição entre strings s1 e s2 é o número mı́nimo
de operações básicas para transformar s1 em s2
Recuperação booleana
40 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de edição
A distância de edição entre strings s1 e s2 é o número mı́nimo
de operações básicas para transformar s1 em s2
Distância de Levenshtein: operações básicas são inserção,
remoção e substituição
Recuperação booleana
40 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de edição
A distância de edição entre strings s1 e s2 é o número mı́nimo
de operações básicas para transformar s1 em s2
Distância de Levenshtein: operações básicas são inserção,
remoção e substituição
distância de Levenshtein doa-do: 1
Recuperação booleana
40 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de edição
A distância de edição entre strings s1 e s2 é o número mı́nimo
de operações básicas para transformar s1 em s2
Distância de Levenshtein: operações básicas são inserção,
remoção e substituição
distância de Levenshtein doa-do: 1
distância de Levenshtein caro-carro: 1
Recuperação booleana
40 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de edição
A distância de edição entre strings s1 e s2 é o número mı́nimo
de operações básicas para transformar s1 em s2
Distância de Levenshtein: operações básicas são inserção,
remoção e substituição
distância de Levenshtein doa-do: 1
distância de Levenshtein caro-carro: 1
distância de Levenshtein pato-pata: 1
Recuperação booleana
40 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de edição
A distância de edição entre strings s1 e s2 é o número mı́nimo
de operações básicas para transformar s1 em s2
Distância de Levenshtein: operações básicas são inserção,
remoção e substituição
distância de Levenshtein doa-do: 1
distância de Levenshtein caro-carro: 1
distância de Levenshtein pato-pata: 1
distância de Levenshtein vôa-avô: 2
Recuperação booleana
40 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de edição
A distância de edição entre strings s1 e s2 é o número mı́nimo
de operações básicas para transformar s1 em s2
Distância de Levenshtein: operações básicas são inserção,
remoção e substituição
distância de Levenshtein doa-do: 1
distância de Levenshtein caro-carro: 1
distância de Levenshtein pato-pata: 1
distância de Levenshtein vôa-avô: 2
distância de Damerau-Levenshtein cat-act: 1
Recuperação booleana
40 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de edição
A distância de edição entre strings s1 e s2 é o número mı́nimo
de operações básicas para transformar s1 em s2
Distância de Levenshtein: operações básicas são inserção,
remoção e substituição
distância de Levenshtein doa-do: 1
distância de Levenshtein caro-carro: 1
distância de Levenshtein pato-pata: 1
distância de Levenshtein vôa-avô: 2
distância de Damerau-Levenshtein cat-act: 1
Damerau-Levenshtein inclui transposição como operação
básica: vôa - avô: 1
Recuperação booleana
40 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de Levenshtein
c
a
t
s
0
1
2
3
4
Recuperação booleana
f
1
1
2
3
4
a
2
2
1
2
3
s
3
3
2
2
2
t
4
4
3
2
3
41 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de Levenshtein
distanciaLevenshtein(s1 , s2 )
1 for i ← 0 to |s1 |
2 do m[i, 0] = i
3 for j ← 0 to |s2 |
4 do m[0, j] = j
5 for i ← 1 to |s1 |
6 do for j ← 1 to |s2 |
7
do if s1 [i] = s2 [j]
8
then m[i, j] = min{m[i-1, j]+1, m[i, j-1]+1, m[i-1, j-1]}
9
else m[i, j] = min{m[i-1, j]+1, m[i, j-1]+1, m[i-1, j-1]+1}
10 return m[|s1 |, |s2 |]
Operações: inserir (custo 1), remoção (custo 1), substituir (custo
1), cópia (custo 0)
Recuperação booleana
42 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de Levenshtein
distanciaLevenshtein(s1 , s2 )
1 for i ← 0 to |s1 |
2 do m[i, 0] = i
3 for j ← 0 to |s2 |
4 do m[0, j] = j
5 for i ← 1 to |s1 |
6 do for j ← 1 to |s2 |
7
do if s1 [i] = s2 [j]
8
then m[i, j] = min{m[i-1, j]+1, m[i, j-1]+1, m[i-1, j-1]}
9
else m[i, j] = min{m[i-1, j]+1, m[i, j-1]+1, m[i-1, j-1]+1}
10 return m[|s1 |, |s2 |]
Operações: inserir (custo 1), remoção (custo 1), substituição
(custo 1), cópia (custo 0)
Recuperação booleana
43 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
distância de Levenshtein: Algoritmo
distanciaLevenshtein(s1 , s2 )
1 for i ← 0 to |s1 |
2 do m[i, 0] = i
3 for j ← 0 to |s2 |
4 do m[0, j] = j
5 for i ← 1 to |s1 |
6 do for j ← 1 to |s2 |
7
do if s1 [i] = s2 [j]
8
then m[i, j] = min{m[i-1, j]+1, m[i, j-1]+1, m[i-1, j-1]}
9
else m[i, j] = min{m[i-1, j]+1, m[i, j-1]+1, m[i-1, j-1]+1}
10 return m[|s1 |, |s2 |]
operações: inserção (custo 1), remoção (custo 1), substituição
(custo 1), cópia (custo 0)
Recuperação booleana
44 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de Levenshtein: Algoritmo
distanciaLevenshtein(s1 , s2 )
1 for i ← 0 to |s1 |
2 do m[i, 0] = i
3 for j ← 0 to |s2 |
4 do m[0, j] = j
5 for i ← 1 to |s1 |
6 do for j ← 1 to |s2 |
7
do if s1 [i] = s2 [j]
8
then m[i, j] = min{m[i-1, j]+1, m[i, j-1]+1, m[i-1, j-1]}
9
else m[i, j] = min{m[i-1, j]+1, m[i, j-1]+1, m[i-1, j-1]+1}
10 return m[|s1 |, |s2 |]
operações: inserção (custo 1), remoção (custo 1), substituição
(custo 1), cópia (custo 0)
Recuperação booleana
45 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de Levenshtein
distanciaLevenshtein(s1 , s2 )
1 for i ← 0 to |s1 |
2 do m[i, 0] = i
3 for j ← 0 to |s2 |
4 do m[0, j] = j
5 for i ← 1 to |s1 |
6 do for j ← 1 to |s2 |
7
do if s1 [i] = s2 [j]
8
then m[i, j] = min{m[i-1, j]+1, m[i, j-1]+1, m[i-1, j-1]}
9
else m[i, j] = min{m[i-1, j]+1, m[i, j-1]+1, m[i-1, j-1]+1}
10 return m[|s1 |, |s2 |]
operações: inserção (custo 1), remoção (custo 1), substituição
(custo 1), cópia (custo 0)
Recuperação booleana
46 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de Levenshtein
f
c
a
t
s
Recuperação booleana
0
1
1
2
2
3
3
4
4
1
1
2
2
3
3
4
4
5
a
1
2
1
2
2
3
3
4
4
2
2
2
1
3
3
4
4
5
s
2
3
2
3
1
2
2
3
3
3
3
3
3
2
2
3
2
4
t
3
4
3
4
2
3
2
3
2
4
4
4
4
3
2
3
3
3
4
5
4
5
3
4
2
3
3
47 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Cada célula da matriz de Levenshtein
custo de chegar aqui a
partir do vizinho superior
esquerdo (cópia ou substituição)
custo de chegar aqui a
partir do vizinho superior
(remoção)
custo de chegar aqui a
partir do vizinho da esquerda (inserção)
o mı́nimo entre os três
possı́veis “movimentos”:
o jeito mais barato de
chegar aqui
Recuperação booleana
48 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de Levenshtein
f
c
a
t
s
Recuperação booleana
0
1
1
2
2
3
3
4
4
1
1
2
2
3
3
4
4
5
a
1
2
1
2
2
3
3
4
4
2
2
2
1
3
3
4
4
5
s
2
3
2
3
1
2
2
3
3
3
3
3
3
2
2
3
2
4
t
3
4
3
4
2
3
2
3
2
4
4
4
4
3
2
3
3
3
4
5
4
5
3
4
2
3
3
49 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Programação dinâmica (Cormen et al.)
Recuperação booleana
50 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Programação dinâmica (Cormen et al.)
Subestrutura ótima: a solução ótima para o problema contém
suas subsoluções i.e., soluções ótimas para os subproblemas
Recuperação booleana
50 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Programação dinâmica (Cormen et al.)
Subestrutura ótima: a solução ótima para o problema contém
suas subsoluções i.e., soluções ótimas para os subproblemas
Subsoluções sobrepostas: essas subsoluções podem ser
recomputadas repetidamente quando o algoritmo é de
força-bruta
Recuperação booleana
50 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Programação dinâmica (Cormen et al.)
Subestrutura ótima: a solução ótima para o problema contém
suas subsoluções i.e., soluções ótimas para os subproblemas
Subsoluções sobrepostas: essas subsoluções podem ser
recomputadas repetidamente quando o algoritmo é de
força-bruta
Subproblema é o caso da distância de edição: “cálculo da
distância de edição entre dois prefixos”
Recuperação booleana
50 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Programação dinâmica (Cormen et al.)
Subestrutura ótima: a solução ótima para o problema contém
suas subsoluções i.e., soluções ótimas para os subproblemas
Subsoluções sobrepostas: essas subsoluções podem ser
recomputadas repetidamente quando o algoritmo é de
força-bruta
Subproblema é o caso da distância de edição: “cálculo da
distância de edição entre dois prefixos”
Subsoluções sobrepostas: precisamos da maior parte das
distâncias de prefixos 3 vezes – que corresponde a mover à
direita, na diagonal e abaixo
Recuperação booleana
50 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de edição ponderada
Recuperação booleana
51 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de edição ponderada
Como antes, mas ponderação depende dos caracteres
envolvidos
Recuperação booleana
51 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de edição ponderada
Como antes, mas ponderação depende dos caracteres
envolvidos
Adequado para capturar erros de teclado, e.g., m é mais
provável de ser escrito errado como n que como q.
Recuperação booleana
51 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de edição ponderada
Como antes, mas ponderação depende dos caracteres
envolvidos
Adequado para capturar erros de teclado, e.g., m é mais
provável de ser escrito errado como n que como q.
Portanto, substituir m por n é uma distância de edição menor
que por q.
Recuperação booleana
51 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de edição ponderada
Como antes, mas ponderação depende dos caracteres
envolvidos
Adequado para capturar erros de teclado, e.g., m é mais
provável de ser escrito errado como n que como q.
Portanto, substituir m por n é uma distância de edição menor
que por q.
Agora necessita-se de uma matriz de pesos como entrada
Recuperação booleana
51 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Distância de edição ponderada
Como antes, mas ponderação depende dos caracteres
envolvidos
Adequado para capturar erros de teclado, e.g., m é mais
provável de ser escrito errado como n que como q.
Portanto, substituir m por n é uma distância de edição menor
que por q.
Agora necessita-se de uma matriz de pesos como entrada
Modificar programação dinâmica para manipular pesos
Recuperação booleana
51 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Usando distância de edição para correção ortográfica
Recuperação booleana
52 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Usando distância de edição para correção ortográfica
Dada uma consulta, primeiro enumeramos todas as sequências
de caracteres dentro de uma pré-determinada (possivelmente
ponderada) distância de edição
Recuperação booleana
52 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Usando distância de edição para correção ortográfica
Dada uma consulta, primeiro enumeramos todas as sequências
de caracteres dentro de uma pré-determinada (possivelmente
ponderada) distância de edição
Intersecção desse conjunto com nossa lista de palavras
“corretas”
Recuperação booleana
52 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Usando distância de edição para correção ortográfica
Dada uma consulta, primeiro enumeramos todas as sequências
de caracteres dentro de uma pré-determinada (possivelmente
ponderada) distância de edição
Intersecção desse conjunto com nossa lista de palavras
“corretas”
Então sugerir termos na intersecção ao usuário
Recuperação booleana
52 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Exercı́cio
1
Computar a matriz da distância de Levenshtein para oslo –
snow
2
Quais são as operações de edição de Levenshtein que
transformam cat em catcat?
Recuperação booleana
53 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
Distância de edição
n
1
2
o
2
3
Correção ortográfica
Soundex
w
3
4
4
54 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
Distância de edição
n
1
2
?
2
o
2
3
Correção ortográfica
Soundex
w
3
4
4
55 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
Distância de edição
n
1
2
1
2
o
2
3
Correção ortográfica
Soundex
w
3
4
4
56 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
Distância de edição
n
1
2
1
2
2
2
o
2
3
?
3
Correção ortográfica
Soundex
w
3
4
4
57 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
Distância de edição
n
1
2
1
2
2
2
o
2
3
2
3
Correção ortográfica
Soundex
w
3
4
4
58 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
Distância de edição
n
1
2
1
2
2
2
o
2
3
2
3
2
3
Correção ortográfica
Soundex
w
3
4
?
4
4
59 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
Distância de edição
n
1
2
1
2
2
2
o
2
3
2
3
2
3
Correção ortográfica
Soundex
w
3
4
2
4
4
60 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
Distância de edição
n
1
2
1
2
2
2
o
2
3
2
3
2
3
Correção ortográfica
Soundex
w
3
4
2
4
4
3
4
5
?
61 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
Distância de edição
n
1
2
1
2
2
2
o
2
3
2
3
2
3
Correção ortográfica
Soundex
w
3
4
2
4
4
3
4
5
3
62 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
Distância de edição
n
1
2
1
2
?
2
2
2
o
2
3
2
3
2
3
Correção ortográfica
Soundex
w
3
4
2
4
4
3
4
5
3
63 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
Distância de edição
n
1
2
1
2
1
2
2
2
o
2
3
2
3
2
3
Correção ortográfica
Soundex
w
3
4
2
4
4
3
4
5
3
64 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
Distância de edição
n
1
2
1
2
1
2
2
2
2
2
o
2
3
2
3
?
3
2
3
Correção ortográfica
Soundex
w
3
4
2
4
4
3
4
5
3
65 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
Distância de edição
n
1
2
1
2
1
2
2
2
2
2
o
2
3
2
3
2
3
2
3
Correção ortográfica
Soundex
w
3
4
2
4
4
3
4
5
3
66 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
Distância de edição
n
1
2
1
2
1
2
2
2
2
2
o
2
3
2
3
2
3
2
3
3
3
Correção ortográfica
Soundex
w
3
4
2
3
?
4
4
3
4
5
3
67 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
Distância de edição
n
1
2
1
2
1
2
2
2
2
2
o
2
3
2
3
2
3
2
3
3
3
Correção ortográfica
Soundex
w
3
4
2
3
3
4
4
3
4
5
3
68 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
Distância de edição
n
1
2
1
2
1
2
2
2
2
2
o
2
3
2
3
2
3
2
3
3
3
Correção ortográfica
Soundex
w
3
4
2
3
3
4
4
3
3
4
4
5
3
4
?
69 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
Distância de edição
n
1
2
1
2
1
2
2
2
2
2
o
2
3
2
3
2
3
2
3
3
3
Correção ortográfica
Soundex
w
3
4
2
3
3
4
4
3
3
4
4
5
3
4
3
70 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
3
4
Distância de edição
n
1
2
1
2
1
2
?
2
2
2
2
2
o
2
3
2
3
2
3
2
3
3
3
Correção ortográfica
Soundex
w
3
4
2
3
3
4
4
3
3
4
4
5
3
4
3
71 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
3
4
Distância de edição
n
1
2
1
2
1
2
2
2
2
2
2
2
o
2
3
2
3
2
3
2
3
3
3
Correção ortográfica
Soundex
w
3
4
2
3
3
4
4
3
3
4
4
5
3
4
3
72 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
3
4
Distância de edição
n
1
2
1
2
1
2
2
2
2
2
2
2
2
3
o
2
3
2
3
2
3
?
3
2
3
3
3
Correção ortográfica
Soundex
w
3
4
2
3
3
4
4
3
3
4
4
5
3
4
3
73 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
3
4
Distância de edição
n
1
2
1
2
1
2
2
2
2
2
2
2
2
3
o
2
3
2
3
2
3
2
3
2
3
3
3
Correção ortográfica
Soundex
w
3
4
2
3
3
4
4
3
3
4
4
5
3
4
3
74 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
3
4
Distância de edição
n
1
2
1
2
1
2
2
2
2
2
2
2
2
3
o
2
3
2
3
2
3
2
3
2
3
3
3
3
3
Correção ortográfica
Soundex
w
3
4
2
3
3
4
?
4
4
3
3
4
4
5
3
4
3
75 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
3
4
Distância de edição
n
1
2
1
2
1
2
2
2
2
2
2
2
2
3
o
2
3
2
3
2
3
2
3
2
3
3
3
3
3
Correção ortográfica
Soundex
w
3
4
2
3
3
4
3
4
4
3
3
4
4
5
3
4
3
76 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
3
4
Distância de edição
n
1
2
1
2
1
2
2
2
2
2
2
2
2
3
o
2
3
2
3
2
3
2
3
2
3
3
3
3
3
Correção ortográfica
Soundex
w
3
4
2
3
3
4
3
4
4
3
3
4
4
4
4
5
3
4
3
4
?
77 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
3
4
Distância de edição
n
1
2
1
2
1
2
2
2
2
2
2
2
2
3
o
2
3
2
3
2
3
2
3
2
3
3
3
3
3
Correção ortográfica
Soundex
w
3
4
2
3
3
4
3
4
4
3
3
4
4
4
4
5
3
4
3
4
4
78 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
3
4
4
5
Distância de edição
n
1
2
1
2
1
2
2
3
?
2
2
2
2
2
2
3
o
2
3
2
3
2
3
2
3
2
3
3
3
3
3
Correção ortográfica
Soundex
w
3
4
2
3
3
4
3
4
4
3
3
4
4
4
4
5
3
4
3
4
4
79 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
3
4
4
5
Distância de edição
n
1
2
1
2
1
2
2
3
3
2
2
2
2
2
2
3
o
2
3
2
3
2
3
2
3
2
3
3
3
3
3
Correção ortográfica
Soundex
w
3
4
2
3
3
4
3
4
4
3
3
4
4
4
4
5
3
4
3
4
4
80 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
3
4
4
5
Distância de edição
n
1
2
1
2
1
2
2
3
3
2
2
2
2
2
2
3
3
4
o
2
3
2
3
2
3
2
3
?
3
2
3
3
3
3
3
Correção ortográfica
Soundex
w
3
4
2
3
3
4
3
4
4
3
3
4
4
4
4
5
3
4
3
4
4
81 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
3
4
4
5
Distância de edição
n
1
2
1
2
1
2
2
3
3
2
2
2
2
2
2
3
3
4
o
2
3
2
3
2
3
2
3
3
3
2
3
3
3
3
3
Correção ortográfica
Soundex
w
3
4
2
3
3
4
3
4
4
3
3
4
4
4
4
5
3
4
3
4
4
82 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
3
4
4
5
Distância de edição
n
1
2
1
2
1
2
2
3
3
2
2
2
2
2
2
3
3
4
o
2
3
2
3
2
3
2
3
3
3
2
3
3
3
3
3
2
4
Correção ortográfica
Soundex
w
3
4
2
3
3
4
3
4
?
4
4
3
3
4
4
4
4
5
3
4
3
4
4
83 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
3
4
4
5
Distância de edição
n
1
2
1
2
1
2
2
3
3
2
2
2
2
2
2
3
3
4
o
2
3
2
3
2
3
2
3
3
3
2
3
3
3
3
3
2
4
Correção ortográfica
Soundex
w
3
4
2
3
3
4
3
4
2
4
4
3
3
4
4
4
4
5
3
4
3
4
4
84 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
3
4
4
5
Distância de edição
n
1
2
1
2
1
2
2
3
3
2
2
2
2
2
2
3
3
4
o
2
3
2
3
2
3
2
3
3
3
2
3
3
3
3
3
2
4
Correção ortográfica
Soundex
w
3
4
2
3
3
4
3
4
2
4
4
3
3
4
4
4
4
3
4
5
3
4
3
4
4
5
?
85 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
Recuperação booleana
1
1
2
1
3
3
4
4
5
Distância de edição
n
1
2
1
2
1
2
2
3
3
2
2
2
2
2
2
3
3
4
o
2
3
2
3
2
3
2
3
3
3
2
3
3
3
3
3
2
4
Correção ortográfica
Soundex
w
3
4
2
3
3
4
3
4
2
4
4
3
3
4
4
4
4
3
4
5
3
4
3
4
4
5
3
86 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
Distância de edição
n
o
Soundex
w
0
1
1
2
2
3
3
1
1
2
1
3
3
4
1
2
1
2
1
2
2
2
2
2
2
2
2
3
2
3
2
3
2
3
2
3
2
3
3
3
3
3
3
4
2
3
3
4
3
4
4
4
5
3
3
3
4
3
3
2
4
4
2
Recuperação booleana
Correção ortográfica
4 4
4 5
3 3
3 4
4 3
4 4
4 4
4 5
3
3
87 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
0
1
1
2
2
3
3
4
4
1
1
2
1
3
3
4
4
5
Distância de edição
n
1
2
1
2
1
2
2
3
3
2
2
2
2
2
2
3
3
4
o
2
3
2
3
2
3
2
3
3
3
2
3
3
3
3
3
2
4
Correção ortográfica
Soundex
w
3
4
2
3
3
4
3
4
2
4
4
3
3
4
4
4
4
3
4
5
3
4
3
4
4
5
3
Como ler as operações de edição que transformam oslo em snow?
Recuperação booleana
88 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
custo
1
0
1
1
2
2
3
3
4
4
1
1
2
1
3
3
4
4
5
operação
inserção
Recuperação booleana
Distância de edição
n
1
2
1
2
1
2
2
3
3
2
2
2
2
2
2
3
3
4
entrada
*
o
2
3
2
3
2
3
2
3
3
3
2
3
3
3
3
3
2
4
Correção ortográfica
Soundex
w
3
4
2
3
3
4
3
4
2
4 4
4 5
3 3
3 4
4 3
4 4
4 4
4 5
3 3
saı́da
w
89 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
custo
0
1
0
1
1
2
2
3
3
4
4
1
1
2
1
3
3
4
4
5
operação
(cópia)
inserção
Recuperação booleana
n
1
2
1
2
1
2
2
3
3
2
2
2
2
2
2
3
3
4
entrada
o
*
2
3
2
3
2
3
2
3
3
Distância de edição
Correção ortográfica
o
w
3 3
2 4
3 2
3 3
3 3
3 4
3 3
2 4
4 2
4 4
4 5
3 3
3 4
4 3
4 4
4 4
4 5
3 3
Soundex
saı́da
o
w
90 / 110
Revisão
Dicionários
Consultas com caracter curinga
s
o
s
l
o
custo
1
0
1
0
1
1
2
2
3
3
4
4
1
1
2
1
3
3
4
4
5
1
2
1
2
1
2
2
3
3
operação
substituição
(cópia)
inserção
Recuperação booleana
Distância de edição
Correção ortográfica
n
o
w
2 2
2 3
2 2
2 3
2 2
2 3
3 2
3 3
4 3
3 3
2 4
3 2
3 3
3 3
3 4
3 3
2 4
4 2
4 4
4 5
3 3
3 4
4 3
4 4
4 4
4 5
3 3
entrada
l
o
*
Soundex
saı́da
n
o
w
91 / 110
Revisão
Dicionários
o
s
l
o
custo
0
1
0
1
0
1
1
2
2
3
3
4
4
Consultas com caracter curinga
Correção ortográfica
s
n
o
w
1 1
1 2
2 1
1 2
3 1
3 2
4 2
4 3
5 3
2 2
2 3
2 2
2 3
2 2
2 3
3 2
3 3
4 3
3 3
2 4
3 2
3 3
3 3
3 4
3 3
2 4
4 2
4 4
4 5
3 3
3 4
4 3
4 4
4 4
4 5
3 3
operação
(cópia)
substituição
(cópia)
inserção
Recuperação booleana
Distância de edição
entrada
s
l
o
*
Soundex
saı́da
s
n
o
w
92 / 110
Revisão
Dicionários
o
s
l
o
custo
1
0
1
0
1
0
1
1
2
2
3
3
4
4
Consultas com caracter curinga
Correção ortográfica
s
n
o
w
1 1
1 2
2 1
1 2
3 1
3 2
4 2
4 3
5 3
2 2
2 3
2 2
2 3
2 2
2 3
3 2
3 3
4 3
3 3
2 4
3 2
3 3
3 3
3 4
3 3
2 4
4 2
4 4
4 5
3 3
3 4
4 3
4 4
4 4
4 5
3 3
operação
remoção
(cópia)
substituição
(cópia)
inserção
Recuperação booleana
Distância de edição
entrada
o
s
l
o
*
Soundex
saı́da
*
s
n
o
w
93 / 110
Revisão
Dicionários
Consultas com caracter curinga
c
c
a
t
0
1
1
2
2
3
3
Recuperação booleana
1
0
2
2
3
3
4
Distância de edição
a
1
2
0
1
1
2
2
2
2
1
0
2
2
3
t
2
3
1
2
0
1
1
3
3
2
2
1
0
2
Correção ortográfica
c
3
4
2
3
1
2
0
4
3
3
3
2
2
1
a
4
5
3
4
2
3
1
5
5
4
3
3
3
2
Soundex
t
5
6
4
5
3
4
2
6
6
5
5
4
3
3
6
7
5
6
4
5
3
94 / 110
Revisão
Dicionários
c
a
t
custo
1
1
1
0
0
0
0
1
1
2
2
3
3
Consultas com caracter curinga
Correção ortográfica
Soundex
c
a
t
c
a
t
1 1
0 2
2 0
2 1
3 1
3 2
4 2
2 2
2 3
1 1
0 2
2 0
2 1
3 1
3 3
3 4
2 2
2 3
1 1
0 2
2 0
4 4
3 5
3 3
3 4
2 2
2 3
1 1
5 5
5 6
4 4
3 5
3 3
3 4
2 2
6 6
6 7
5 5
5 6
4 4
3 5
3 3
operação
inserção
inserção
inserção
(cópia)
(cópia)
(cópia)
Recuperação booleana
Distância de edição
entrada
*
*
*
c
a
t
saı́da
c
a
t
c
a
t
95 / 110
Revisão
Dicionários
c
a
t
custo
0
1
1
1
0
0
0
1
1
2
2
3
3
Consultas com caracter curinga
Correção ortográfica
Soundex
c
a
t
c
a
t
1 1
0 2
2 0
2 1
3 1
3 2
4 2
2 2
2 3
1 1
0 2
2 0
2 1
3 1
3 3
3 4
2 2
2 3
1 1
0 2
2 0
4 4
3 5
3 3
3 4
2 2
2 3
1 1
5 5
5 6
4 4
3 5
3 3
3 4
2 2
6 6
6 7
5 5
5 6
4 4
3 5
3 3
operação
(cópia)
inserção
inserção
inserção
(cópia)
(cópia)
Recuperação booleana
Distância de edição
entrada
c
*
*
*
a
t
saı́da
c
a
t
c
a
t
96 / 110
Revisão
Dicionários
c
a
t
custo
0
0
1
1
1
0
0
1
1
2
2
3
3
Consultas com caracter curinga
Correção ortográfica
Soundex
c
a
t
c
a
t
1 1
0 2
2 0
2 1
3 1
3 2
4 2
2 2
2 3
1 1
0 2
2 0
2 1
3 1
3 3
3 4
2 2
2 3
1 1
0 2
2 0
4 4
3 5
3 3
3 4
2 2
2 3
1 1
5 5
5 6
4 4
3 5
3 3
3 4
2 2
6 6
6 7
5 5
5 6
4 4
3 5
3 3
operação
(cópia)
(cópia)
inserção
inserção
inserção
(cópia)
Recuperação booleana
Distância de edição
entrada
c
a
*
*
*
t
saı́da
c
a
t
c
a
t
97 / 110
Revisão
Dicionários
c
a
t
custo
0
0
0
1
1
1
0
1
1
2
2
3
3
Consultas com caracter curinga
Correção ortográfica
Soundex
c
a
t
c
a
t
1 1
0 2
2 0
2 1
3 1
3 2
4 2
2 2
2 3
1 1
0 2
2 0
2 1
3 1
3 3
3 4
2 2
2 3
1 1
0 2
2 0
4 4
3 5
3 3
3 4
2 2
2 3
1 1
5 5
5 6
4 4
3 5
3 3
3 4
2 2
6 6
6 7
5 5
5 6
4 4
3 5
3 3
operação
(cópia)
(cópia)
(cópia)
inserção
inserção
inserção
Recuperação booleana
Distância de edição
entrada
c
a
t
*
*
*
saı́da
c
a
t
c
a
t
98 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Conteúdo
1
Revisão
2
Dicionários
3
Consultas com caracter curinga
4
Distância de edição
5
Correção ortográfica
6
Soundex
Recuperação booleana
99 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica
Recuperação booleana
100 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica
Agora que sabemos computar a distância de edição: como
usá-la para correção ortográfica de palavras isoladas
Recuperação booleana
100 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica
Agora que sabemos computar a distância de edição: como
usá-la para correção ortográfica de palavras isoladas
ı́ndices k-grams para correção ortográfica de palavras isoladas.
Recuperação booleana
100 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica
Agora que sabemos computar a distância de edição: como
usá-la para correção ortográfica de palavras isoladas
ı́ndices k-grams para correção ortográfica de palavras isoladas.
Correção ortográfica sensı́vel a contexto
Recuperação booleana
100 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índices de k-gramas indexes para correção ortográfica
Recuperação booleana
101 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índices de k-gramas indexes para correção ortográfica
Enumerar todos k-gramas no termo de consulta
Recuperação booleana
101 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índices de k-gramas indexes para correção ortográfica
Enumerar todos k-gramas no termo de consulta
Exemplo: ı́ndice bigram, palavra errada bordroom
Recuperação booleana
101 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índices de k-gramas indexes para correção ortográfica
Enumerar todos k-gramas no termo de consulta
Exemplo: ı́ndice bigram, palavra errada bordroom
Bigramas: bo, or, rd, dr, ro, oo, om
Recuperação booleana
101 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índices de k-gramas indexes para correção ortográfica
Enumerar todos k-gramas no termo de consulta
Exemplo: ı́ndice bigram, palavra errada bordroom
Bigramas: bo, or, rd, dr, ro, oo, om
Use o ı́ndice k-grama para recuperar palavras “corretas” que
correspondem ao termo k-grams
Recuperação booleana
101 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índices de k-gramas indexes para correção ortográfica
Enumerar todos k-gramas no termo de consulta
Exemplo: ı́ndice bigram, palavra errada bordroom
Bigramas: bo, or, rd, dr, ro, oo, om
Use o ı́ndice k-grama para recuperar palavras “corretas” que
correspondem ao termo k-grams
Limite o número de k-gramas que correspondem
Recuperação booleana
101 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índices de k-gramas indexes para correção ortográfica
Enumerar todos k-gramas no termo de consulta
Exemplo: ı́ndice bigram, palavra errada bordroom
Bigramas: bo, or, rd, dr, ro, oo, om
Use o ı́ndice k-grama para recuperar palavras “corretas” que
correspondem ao termo k-grams
Limite o número de k-gramas que correspondem
E.g., somente termos do vocabulário que diferem em até 3
k-gramas
Recuperação booleana
101 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Índices k-gramas para correção ortográfica: bordroom
bo
- aboard
- about
or
- border
-
rd
- aboard
- ardent
Recuperação booleana
lord
- boardroom - border
- morbid
- sordid
- boardroom - border
102 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica sensı́vel a contexto
Recuperação booleana
103 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica sensı́vel a contexto
Exemplo: esteroide caiu terra
Recuperação booleana
103 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica sensı́vel a contexto
Exemplo: esteroide caiu terra
Podemos corrigir esteroide?
Recuperação booleana
103 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica sensı́vel a contexto
Exemplo: esteroide caiu terra
Podemos corrigir esteroide?
Ideia: correção ortográfica baseada em número de resultados
Recuperação booleana
103 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica sensı́vel a contexto
Exemplo: esteroide caiu terra
Podemos corrigir esteroide?
Ideia: correção ortográfica baseada em número de resultados
Recuperar termos “corretos” mais próximos a cada termo de
consulta
Recuperação booleana
103 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica sensı́vel a contexto
Exemplo: esteroide caiu terra
Podemos corrigir esteroide?
Ideia: correção ortográfica baseada em número de resultados
Recuperar termos “corretos” mais próximos a cada termo de
consulta
para asteroide caiu terra: de esteroide para asteroide, de caiu
para caio, de terra para terá
Recuperação booleana
103 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica sensı́vel a contexto
Exemplo: esteroide caiu terra
Podemos corrigir esteroide?
Ideia: correção ortográfica baseada em número de resultados
Recuperar termos “corretos” mais próximos a cada termo de
consulta
para asteroide caiu terra: de esteroide para asteroide, de caiu
para caio, de terra para terá
Agora tente todas as frases resultantes para consultas com
uma palavra “corrigida” por vez
Recuperação booleana
103 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica sensı́vel a contexto
Exemplo: esteroide caiu terra
Podemos corrigir esteroide?
Ideia: correção ortográfica baseada em número de resultados
Recuperar termos “corretos” mais próximos a cada termo de
consulta
para asteroide caiu terra: de esteroide para asteroide, de caiu
para caio, de terra para terá
Agora tente todas as frases resultantes para consultas com
uma palavra “corrigida” por vez
Consulte “asteroide” “caiu” “terra”
Recuperação booleana
103 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica sensı́vel a contexto
Exemplo: esteroide caiu terra
Podemos corrigir esteroide?
Ideia: correção ortográfica baseada em número de resultados
Recuperar termos “corretos” mais próximos a cada termo de
consulta
para asteroide caiu terra: de esteroide para asteroide, de caiu
para caio, de terra para terá
Agora tente todas as frases resultantes para consultas com
uma palavra “corrigida” por vez
Consulte “asteroide” “caiu” “terra”
Consulte “esteroide” “caio” “terra”
Recuperação booleana
103 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica sensı́vel a contexto
Exemplo: esteroide caiu terra
Podemos corrigir esteroide?
Ideia: correção ortográfica baseada em número de resultados
Recuperar termos “corretos” mais próximos a cada termo de
consulta
para asteroide caiu terra: de esteroide para asteroide, de caiu
para caio, de terra para terá
Agora tente todas as frases resultantes para consultas com
uma palavra “corrigida” por vez
Consulte “asteroide” “caiu” “terra”
Consulte “esteroide” “caio” “terra”
Consulte “esteroide” “caiu” “terá”
Recuperação booleana
103 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica sensı́vel a contexto
Exemplo: esteroide caiu terra
Podemos corrigir esteroide?
Ideia: correção ortográfica baseada em número de resultados
Recuperar termos “corretos” mais próximos a cada termo de
consulta
para asteroide caiu terra: de esteroide para asteroide, de caiu
para caio, de terra para terá
Agora tente todas as frases resultantes para consultas com
uma palavra “corrigida” por vez
Consulte “asteroide” “caiu” “terra”
Consulte “esteroide” “caio” “terra”
Consulte “esteroide” “caiu” “terá”
A consulta correta “asteroide caiu terra” tem maior número de
resultados
Recuperação booleana
103 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica sensı́vel a contexto
Exemplo: esteroide caiu terra
Podemos corrigir esteroide?
Ideia: correção ortográfica baseada em número de resultados
Recuperar termos “corretos” mais próximos a cada termo de
consulta
para asteroide caiu terra: de esteroide para asteroide, de caiu
para caio, de terra para terá
Agora tente todas as frases resultantes para consultas com
uma palavra “corrigida” por vez
Consulte “asteroide” “caiu” “terra”
Consulte “esteroide” “caio” “terra”
Consulte “esteroide” “caiu” “terá”
A consulta correta “asteroide caiu terra” tem maior número de
resultados
Suponha que temos 7 alternativas para terra, 20 para caiu e 3
para esteroide, quantas consultas “corrigidas” teremos?
Recuperação booleana
103 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica sensı́vel a contexto
Recuperação booleana
104 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica sensı́vel a contexto
O algoritmo baseado em número de resultados não é eficiente
Recuperação booleana
104 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Correção ortográfica sensı́vel a contexto
O algoritmo baseado em número de resultados não é eficiente
Alternativa mais eficiente: usar coleção de consultas e não
documentos
Recuperação booleana
104 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Problemas gerais na correção ortográfica
Recuperação booleana
105 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Problemas gerais na correção ortográfica
Interface de usuário
Recuperação booleana
105 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Problemas gerais na correção ortográfica
Interface de usuário
Correção automática vs. correção sugerida
Recuperação booleana
105 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Problemas gerais na correção ortográfica
Interface de usuário
Correção automática vs. correção sugerida
Você quis dizer: somente uma sugestão
Recuperação booleana
105 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Problemas gerais na correção ortográfica
Interface de usuário
Correção automática vs. correção sugerida
Você quis dizer: somente uma sugestão
E múltiplas correções possı́veis?
Recuperação booleana
105 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Problemas gerais na correção ortográfica
Interface de usuário
Correção automática vs. correção sugerida
Você quis dizer: somente uma sugestão
E múltiplas correções possı́veis?
Balanço: interface simples ou detalhista
Recuperação booleana
105 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Problemas gerais na correção ortográfica
Interface de usuário
Correção automática vs. correção sugerida
Você quis dizer: somente uma sugestão
E múltiplas correções possı́veis?
Balanço: interface simples ou detalhista
Custo
Recuperação booleana
105 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Problemas gerais na correção ortográfica
Interface de usuário
Correção automática vs. correção sugerida
Você quis dizer: somente uma sugestão
E múltiplas correções possı́veis?
Balanço: interface simples ou detalhista
Custo
Correção ortográfica é potencialmente cara
Recuperação booleana
105 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Problemas gerais na correção ortográfica
Interface de usuário
Correção automática vs. correção sugerida
Você quis dizer: somente uma sugestão
E múltiplas correções possı́veis?
Balanço: interface simples ou detalhista
Custo
Correção ortográfica é potencialmente cara
Evitar executar em toda consulta
Recuperação booleana
105 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Problemas gerais na correção ortográfica
Interface de usuário
Correção automática vs. correção sugerida
Você quis dizer: somente uma sugestão
E múltiplas correções possı́veis?
Balanço: interface simples ou detalhista
Custo
Correção ortográfica é potencialmente cara
Evitar executar em toda consulta
Talvez somente em consultas com poucos documentos
Recuperação booleana
105 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Problemas gerais na correção ortográfica
Interface de usuário
Correção automática vs. correção sugerida
Você quis dizer: somente uma sugestão
E múltiplas correções possı́veis?
Balanço: interface simples ou detalhista
Custo
Correção ortográfica é potencialmente cara
Evitar executar em toda consulta
Talvez somente em consultas com poucos documentos
Correção ortográfica dos maiores buscadores é eficiente para
ser realizada em toda consulta
Recuperação booleana
105 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Conteúdo
1
Revisão
2
Dicionários
3
Consultas com caracter curinga
4
Distância de edição
5
Correção ortográfica
6
Soundex
Recuperação booleana
106 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Soundex
Recuperação booleana
107 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Soundex
Soundex é a base para encontrar alternativas fonéticas (e não
ortográficas)
Recuperação booleana
107 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Soundex
Soundex é a base para encontrar alternativas fonéticas (e não
ortográficas)
Exemplo: chebyshev / tchebyscheff
Recuperação booleana
107 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Soundex
Soundex é a base para encontrar alternativas fonéticas (e não
ortográficas)
Exemplo: chebyshev / tchebyscheff
Algoritmo:
Recuperação booleana
107 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Soundex
Soundex é a base para encontrar alternativas fonéticas (e não
ortográficas)
Exemplo: chebyshev / tchebyscheff
Algoritmo:
Transformar cada token indexado em uma forma reduzida de
4-caracteres
Recuperação booleana
107 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Soundex
Soundex é a base para encontrar alternativas fonéticas (e não
ortográficas)
Exemplo: chebyshev / tchebyscheff
Algoritmo:
Transformar cada token indexado em uma forma reduzida de
4-caracteres
Faça o mesmo com termos de consulta
Recuperação booleana
107 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Soundex
Soundex é a base para encontrar alternativas fonéticas (e não
ortográficas)
Exemplo: chebyshev / tchebyscheff
Algoritmo:
Transformar cada token indexado em uma forma reduzida de
4-caracteres
Faça o mesmo com termos de consulta
Construir e procurar em um ı́ndice de formas reduzidas
Recuperação booleana
107 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Algoritmo Soundex (inglês)
1
2
3
Reter a primeira letra do termo
Mudar todas as ocorrências das letras seguintes para ’0’ (zero): A, E,
I, O, U, H, W, Y
Mudar letras para dı́gitos da seguinte forma:
B, F, P, V para 1
C, G, J, K, Q, S, X, Z para 2
D,T para 3
L para 4
M, N para 5
R para 6
4
5
6
7
Remover repetidamente um de cada par de dı́gitos idênticos
Remover todos os zeros da string resultante
Completar a string resultante com zeros
Retornar as quatro primeiras posições, que consistirão de uma letra
seguida por três dı́gitos
Recuperação booleana
108 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Exemplo: Soundex de HERMAN
Recuperação booleana
109 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Exemplo: Soundex de HERMAN
Reter H
Recuperação booleana
109 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Exemplo: Soundex de HERMAN
Reter H
ERMAN → 0RM0N
Recuperação booleana
109 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Exemplo: Soundex de HERMAN
Reter H
ERMAN → 0RM0N
0RM0N → 06505
Recuperação booleana
109 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Exemplo: Soundex de HERMAN
Reter H
ERMAN → 0RM0N
0RM0N → 06505
06505 → 06505
Recuperação booleana
109 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Exemplo: Soundex de HERMAN
Reter H
ERMAN → 0RM0N
0RM0N → 06505
06505 → 06505
06505 → 655
Recuperação booleana
109 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Exemplo: Soundex de HERMAN
Reter H
ERMAN → 0RM0N
0RM0N → 06505
06505 → 06505
06505 → 655
Retornar H655
Recuperação booleana
109 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
Exemplo: Soundex de HERMAN
Reter H
ERMAN → 0RM0N
0RM0N → 06505
06505 → 06505
06505 → 655
Retornar H655
Note: HERMANN gerará o mesmo código
Recuperação booleana
109 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
O quão útil é Soundex?
Recuperação booleana
110 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
O quão útil é Soundex?
Não muito – para ORI
Recuperação booleana
110 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
O quão útil é Soundex?
Não muito – para ORI
Ok para tarefas de “alta recuperação” em aplicações
especı́ficas (e.g., Interpol)
Recuperação booleana
110 / 110
Revisão
Dicionários
Consultas com caracter curinga
Distância de edição
Correção ortográfica
Soundex
O quão útil é Soundex?
Não muito – para ORI
Ok para tarefas de “alta recuperação” em aplicações
especı́ficas (e.g., Interpol)
Zobel e Dart (1996) sugerem alternativas para busca fonética
em ORI
Recuperação booleana
110 / 110