Recuperação de Informação em Bases de Texto
Aula 4
1
Recuperação de Informação em Bases de Texto
• Correcção de erros:
– Nos documentos
– Nas pesquisas
– Palavra a palavra
• análise ortográfica
– “siêntifico” -> “ciêntifico”
– Na contexto da frase ou expressão
• análise sintáctica e semântica
– “O concelho científico reuniu...” -> “O
conselho científico reuniu...
2
Recuperação de Informação em Bases de Texto
• Correcção de erros:
– Metodologia para as pesquisas:
• Corrigir automaticamente e de uma forma
“transparente” para o utilizador;
• Interagir com o utilizador e propôr
alternativas
3
Recuperação de Informação em Bases de Texto
• Correcção de erros:
– Metodologia:
• Necessário existir um léxico de palavras
“correctas”:
– dicionário externo
– palavras existentes em colecções de
dados (web...)
4
Recuperação de Informação em Bases de Texto
• Correcção de erros:
– Metodologia:
• Dada uma palavra e um léxico obter uma
lista das palavras mais “próximas” dessa
palavra:
– distância Levenshtein
– distância “pesada”
– n-gramas comuns
• Normalmente, calcula-se a lista das palavras
dos léxico a uma distância menor do que “k”
da palavra da pesquisa
5
Recuperação de Informação em Bases de Texto
• Correcção de erros:
– distância Levenshtein
• nº mínimo de operações (sobre caracteres)
necessário para converter uma palavra na
outra:
– inserções; remoções; alterações; trocas
de posição
• Ex:
– siêntifico -> ciêntifico – 1 (alteração)
– ciêntiifco -> ciêntifico – 2 (alteração)
– ciêntiifco -> ciêntifico – 1 (troca)
6
Recuperação de Informação em Bases de Texto
• Correcção de erros:
– distância Levenshtein
• Implementação
– O(n1 * n2), sendo n1 e n2 o tamanho das
duas palavras (s1 e s2) a calcular a
distância
– Recorre a programação dinâmica e
necessita de uma matriz de n1*n2
inteiros.
– m[i,j] -> distância entre os primeiros i
caracteres de s1 e os primeiros j
caracteres de s2
7
Recuperação de Informação em Bases de Texto
• distância Levenshtein(s1, s2) =
– int m[strlen(s1),strlen(s2)]; // inicializado a 0;
– for i = 1 to strlen(s1) do m[i,0] = i;
– for j = 1 to strlen(s2) do m[0,j] = j;
– for i = 1 to strlen(s1)
• for j = 1 to strlen(s2)
– m[i,j] = min(m[i-1, j]+1, m[i, j-1]+1,
m[i-1,j-1]+(s1[i]==s2[j]?0:1));
– return(m[strlen(s1),strlen(s2)]
8
Recuperação de Informação em Bases de Texto
""
""
p
r
a
t
o
g
0
1
2
3
4
5
a
1
t
2
a
3
s
4
5
9
Recuperação de Informação em Bases de Texto
""
""
p
r
a
t
o
g
0
1
1 2,1,2
2
3
4
5
a
t
2
a
3
s
4
5
10
Recuperação de Informação em Bases de Texto
""
""
p
r
a
t
o
g
0
1
2
3
4
5
a
1
2
1 2,2,3
t
a
3
s
4
5
11
Recuperação de Informação em Bases de Texto
""
""
p
r
a
t
o
g
0
1
1
1
2 3,2,2
3
4
5
a
t
2
2
a
3
s
4
5
12
Recuperação de Informação em Bases de Texto
""
""
p
r
a
t
o
g
0
1
2
3
4
5
a
1
2
1
2
2 3,2,3
t
a
3
s
4
5
13
Recuperação de Informação em Bases de Texto
""
""
p
r
a
t
o
g
0
1
2
3
4
5
a
1
1
2
3
4
5
t
2
2
2
2
3
4
a
3
3
3
3
2
3
s
4
4
4
3
3
3
5
5
5
4
4
4
14
Recuperação de Informação em Bases de Texto
• Correcção de erros:
– distância “pesada”
• o peso das operações depende dos
caracteres envolvidos:
– a troca de um “m” por um “n” tem um
peso menor do que um “m” por um “a”
• implementação semelhante à distância de
Levenshtein, com adaptações para ter em
conta o peso das operações.
15
Recuperação de Informação em Bases de Texto
• Correcção de erros:
– n-gramas comuns
• Fase 0: Criar um índice “n-gramas ->
termos” que, para cada n-grama, aponta
para a lista das palavras do dicionário que
contêm aquele n-grama;
• Fase 1: Identificar todos os n-gramas da
palavra da pesquisa;
• Fase 2: Usar o índice “n-gramas -> termos”
para obter todas as palavras do dicionário
que têm um n-grama em comum com a
palavra da pesquisa
16
Recuperação de Informação em Bases de Texto
• Correcção de erros:
– n-gramas comuns
• Fase 3: Seleccionar as palavras do dicionário
que têm mais n-gramas comuns com a
palavra da pesquisa.
17
Recuperação de Informação em Bases de Texto
• Correcção de erros:
– n-gramas comuns
• Como definir o valor a partir do qual as
palavras estão próximas?
– Coeficiente Jaccard
» nº de n-gramas comuns / (nº de ngramas distintos)
18
Recuperação de Informação em Bases de Texto
• Correcção de erros:
– n-gramas comuns
• Exemplo, com bigramas:
– concelho -> $c; co; on; nc; ce; el; lh; ho;
o$
– conselho -> $c; co; on; ns; se; el; lh; ho;
o$
– comcelho -> $c; co; om; mc; ce; el; lh; ho;
o$
19
Recuperação de Informação em Bases de Texto
• Correcção de erros:
– n-gramas comuns
• Exemplo, com bigramas:
– concelho -> $c; co; on; nc; ce; el; lh; ho;
o$
– comcelho -> $c; co; om; mc; ce; el; lh; ho;
o$
– 7 bigramas em comum; 4 diferentes
– coeficiente de Jaccard = 7 / 11 = 0.63...
20
Recuperação de Informação em Bases de Texto
• Correcção de erros:
– n-gramas comuns
• Exemplo, com bigramas:
– conselho -> $c; co; on; ns; se; el; lh; ho;
o$
– comcelho -> $c; co; om; mc; ce; el; lh; ho;
o$
– 6 bigramas em comum; 6 diferentes
– coeficiente de Jaccard = 6 / 12 = 0.5
21
Recuperação de Informação em Bases de Texto
• Correcção de erros:
– No contexto de uma frase ou expressão:
• Obter lista de palavras “próxima” para cada
palavra da expressão
– “concelho científico”
» concelho -> concelho, conselho
» científico -> científico
22
Recuperação de Informação em Bases de Texto
• Correcção de erros:
– No contexto de uma frase ou expressão:
• Calcular combinações
– concelho científico
– conselho científico
23
Recuperação de Informação em Bases de Texto
• Correcção de erros:
– No contexto de uma frase ou expressão:
• Calcular combinações
– concelho científico
– conselho científico
24
Recuperação de Informação em Bases de Texto
• Correcção de erros:
– No contexto de uma frase ou expressão:
• Seleccionar a expressão com maior número
de “hits”!
– concelho científico – X hits
– conselho científico – Y > X
• Assume texto do corpus maioritariamente
correcto!
25