Sistemas de
Recuperação da
Informação
Parte III
Consultas
Consultas
Principais modelos de recuperação da informação:
• Pesquisa em textos
• Modelos clássicos
•Consultas Booleanas
• Modelo vetorial
• Modelo probabilístico
• Modelos avançados
• Booleano estendido e modelo fuzzy
• Vetorial estendido e análise semântica latente
• Outros modelos probabilísticos – redes Bayesianas
Consultas
Pesquisa em textos :
Problema: encontre as ocorrências de um termo em uma fonte
Termo e Fonte são cadeias de caracteres
Aplicações:
• Pesquisa por stop-words
• Detecção de radicais, afixos, sufixos
• Pesquisa por frases
• Pesquisa por termos compostos
Principais algoritmos:
• Ingênuo
• Knuth-Morris-Pratt
• Boyer-Moore
• Shift-or
• Karp-Rabin
• frases
Consultas
Algoritmo ingênuo:
Dado um termo t de comprimento m e
uma fonte d de comprimento n
Algoritmo:
Dado t com tam(t)=m e d com com tam(d) = n
para i=1 até n-m {
k=i;
para (j=1; j<=m & t[j] ==d[k]; j++) k++;
se (j>m) então imprima(“t ocorre na posição i de d”);
}
Complexidade: O(n.m)
EXEMPLO: d = “a aba do abajour abriu abaixo”
t = “abaixo”
Consultas
Algoritmo de Knuth-Morris-Pratt:
Dependendo da estrutura do termo t a cada diferença
entre t e o substring da fonte d pode-se dar um passo
maior para a próxima comparação
Definição do passo:
passo(j)=max{ i / t[k] = t[j-i+k], k=1,..,i-1 e t[i]  t[j]}
a b a i x o
1 2 1 2 3 4
EXEMPLO: d
Complexidade: 2n
= “a aba do abajour abriu abaixo”
t = “abaixo
abaixo
abaixo
abaixo
abaixo
Consultas
Algoritmos de Boyer-Moore:
Compara da direita para a esquerda
Pesquisa um termo
ou vários termos
Alg1: Compare da direita para a esquerda
Em um descasamento em d(i) procure d(i) em t e fixe o deslocamento, k
EXEMPLO: d
k=6
k=1
k=6
Complexidade: n + r m
= “a la embaixo abajour”
t = “abaixo
abaixo
abaixo
abaixo
Consultas
Algoritmos Shift-Or:
Se baseia em automatas e usa operações entre bitstrings
VANTAGENS:
• simplicidade: operações binárias
• tempo real: tempo fixo para processar cada letra
• sem buffering: não precisa armazenar o texto integral
Alg: - crie uma assinatura para cada caractere do alfabeto
- crie um estado inicial D0 = 11111
- para cada caractere lido, aplique a fórmula Di = shift-left(Di-1) | T[corrente]
- pare quando o primeiro bit do estado for ‘0’
Complexidade: O(nm/w) w=tamanho do byte
Consultas
Algoritmos Shift-Or:
t = “a b a b c”
T(a)
1 0 1 0 0
T(b)
0 1 0 1 0
T(c)
0 0 0 0 1
T(d)
0 0 0 0 0
EXEMPLO: d
= “abdabababc”
t = “ababc”
=
=
=
=
11010
10101
01111
11111
Operação sobre os estados:
D0 = 11111
Di = shift-left(Di-1) | T[corrente]
texto = “a
b
d
(‘|’ é o ou lógico)
a
b
a
b
a
b
c”
D0 = 11111
T(x)
Di
=
=
Variante
Di
=
11010 10101 11111 11010 10101 11010 10101 11010 10101 01111
11110 11101 11111 11110 11101 11010 10101 11010 10101 01111
c
11110 11101 11111 11110 11101 11010 10101 01010
Consultas
Frases:
• Procure o símbolo menos frequente na consulta
• localize-o no texto
• analise a vizinhança (exata ou aproximada)
EXEMPLO: d
= “ser ou não ser, eis a questão”
frequência das letras:
freq(‘s’) = 4 -> “er ou não er, ei a quetão”
freq(‘e’) = 4 -> “r ou não r, i a qutão”
freq(‘r’) = 2 -> “ ou não i a qutão”
freq(‘o’) = 3 -> “u nã i a qutã”
Freq(‘u’) = 2 -> “nã i a qtã”
freq(‘n’) = 1 -> “ã i a qtã”
Freq(‘a) = 3 -> “iqt”
OBS.: pode-se
freq(‘i’) = freq(q) = freq(t) = 1 -> “”
trocar a
letra por um n-grama
Consultas
Consultas Booleanas
•Em bancos de dados podemos fazer uma consulta:
SELECT nome, idade FROM pessoa
WHERE idade > 18
Em RI os dados não têm semântica.
Para um 18 não sabemos que representa uma idade e nem de
quem
Em Recuperação da Informação só podemos procurar pela
existência ou não de um termo em um documento.
Esta existência pode ser precisa, aproximada, importante
Consultas Booleanas
•Uma consulta booleana é uma combinação lógica de palavras-chave.
Pode ser oriunda de
• Uma expressão em linguagem natural interpretada
• Uma interface que permite a declaração de expressões Booleanas
EXEMPLO:
Quais documentos falam de 'recuperação' e de
'informação' mas não de 'teoria'?
'recuperação' AND 'informação' AND NOT('teoria')?
Consultas
Consultas Booleanas
EXPRESSÕES BOOLEANAS (EB):
Dado um conjunto de termos t = {t1, ..., tn} e duas EBs e1 e e2:
• Um termo é uma expressão booleana (EB)
• (e1 AND e2) é uma EB
• NOT(e1) é uma EB.
Definimos
• (e1 OR e2)  NOT(NOT(e1) AND NOT(e2))
• (e1 XOR e2)  (e1 OR e2) AND NOT(e1 AND e2)
Consultas Booleanas
EXECUÇÃO DE EXPRESSÕES BOOLEANAS:
1ª solução: GREPPING
• Seja U = {D1, .., Dn} um conjunto de documentos
• Dada a consulta “'recuperação' AND 'informação' AND NOT('teoria')”
• realizar uma pesquisa em texto em cada documento e
responder a consulta
Consultas Booleanas
EXECUÇÃO DE EXPRESSÕES BOOLEANAS:
• Dado um conjunto de termos t = {t1, ..., tn}
• Dado um conjunto de documentos U, seja
Di  U o subconjunto de U que contém ti, para i=1,..n
Dado uma expressão Booleana e, denotamos U(e) ou
simplesmente (e) o resultado da aplicação de e a U. Temos:
• (ti) = Di – (p.ex. da lista invertida)
•
•
(ei AND ej) = Di  Dj
(NOT(ei)) = U - Di.
PROPOSIÇÃO:
•(ei OR ej) = Di  Dj
Consultas Booleanas
EXECUTAR EXPRESSÕES BOOLEANAS significa:
• Encontrar listas (de documentos)
• Operar listas
OPERAÇÕES PRIMITIVAS SOBRE LISTAS
• intercala(l1,l2): forma lista com todos elementos de ambas as listas
• todos(l): elimina duplicatas
• comuns(l): mantém uma entrada de cada elemento duplicado
• uns(l): só mantém os elementos que ocorrem uma vez na lista
Consultas Booleanas
OPERAÇÕES
BOOLEANAS EM FUNÇÃO DAS PRIMITVAS
• a OR b = todas(intercala(a,b))
• a AND b = comuns(intercala(a,b))
• a XOR b = uns(intercala(a,b))
• NOT(a) = ?
• a AND NOT(b) = a – b = uns(intercala(a, a AND b)
Consultas Booleanas
EXEMPLO:
Seja (T1) = {D1, D3)
(T2) = {D1, D2}
(T3) = (D2, D3,D4}
Calculemos ( (T1 OR T2) AND NOT(T3) )
Intercala(T1,T2) =
{D1,D1,D2,D3}
T1 OR T2 =
{D1,D2,D3}
Intercala( (T1 OR T2), T3) = {D1,D2,D2,D3,D3,D4}
( (T1 OR T2) AND T3 ) =
{D2,D3}
Intercala ( (T1 OR T2),( (T1 OR T2) AND T3) ) =
{D1,D2,D2,D3,D3}
(T1 OR T2) AND NOT(T3) =
{D1}
Consultas Booleanas
OTIMIZAÇÃO:
DADO:
a AND b AND c
Ordenar a, b, c e processar primeiro os pares
com menor frequência.
Consultas Booleanas
Além de consultas por palavras-chave:
• casamento parcial (consultas-AND longas e consultas-OR longas)
• ranking dos resultados
• frases
• proximidade entre termos
(‘informação’ ANTES ou PERTO_DE ‘recuperação’)
• importância dos termos (frequência, idf)
• termos compostos, conceitos (sinonímia, mero-,hiper- e hyponímia)
• documentos semi-estruturados
(dividido em ‘TÍTULO’, ‘AUTOR’, ‘RESUMO’, ‘PALAVRAS CHAVE’,
RESTO composto por CAPÍTULOS, ... Ex. encontre livros com AUTOR
contendo ‘Baeza-Yates’ e um capítulo sobre ‘signature files’)
• agrupamento de documentos
Consultas Booleanas Estendidas
Modelos: Mixed Min-Max (MMM), Paice e P-norma
Modelo MMM é baseado na teoria de conjuntos fuzzy:
Sejam termos ‘a’ e ‘b’
• dega é o grau de pertinência de ‘a’ a um certo conjunto (documento)
• degab = min(dega, degb)
• degab = max(dega, degb)
Dado consultas COR = (a1 OR a2 OR ... OR an)
e CAND = (a1 AND a2 AND ... AND an), e um documento D, define-se:
• sim(COR,D) = kor1*max(dega1,...degan) + kor2*min(dega1,..,degan)
• sim(CAND,D) = kand1*min(dega1,...degan) + kand2*max(dega1,..,degan)
• os ‘k’s são coeficientes reguladores, sendo
kor1 = 1 – kor2 e kand1 = 1-kand2. Bons resultados ocorrem com
kor1 > 0.2 e kand1 [0.5,0.8]
Consultas Booleanas Estendidas
Modelos: Mixed Min-Max (MMM), Paice e P-norma
Modelo de Paice:
Similar ao MMM mas, ao invés de considerar os max e min
de todos termos da consulta, leva todos pesos em
consideração.
Modelo de P-norma:
Neste modelo tanto os termos da consulta como os termos
nos documentos são ponderados.
Detalhes sobre estes dois modelos em:
• Frakes&Baeza-Yates, “Information Retrieval – Data Structures & Algorithms”
Prentice-Hall (1992)
• Kowalski “Informationh Retrieval – Theory and Implementation” Kluwer (1997)
Consultas Booleanas
• a OR b = todas(intercala(a,b))
• a AND b = comuns(intercala(a,b))
• a XOR b = uns(intercala(a,b))
• a AND NOT(b) = a – b = uns(intercala(a, a AND b)
EXERCÍCIO
• a OR NOT(b) = ??
Seja (T1) = {D1, D3)
(T2) = {D1, D2}
(T3) = (D2, D3,D4}
Calcular (NOT(T3) OR (T1 AND T2 AND T3))
Modelo Vetorial
Considera um dicionário com n termos como um
espaço com n dimensões.
• assim, os k termos que indexam um documento D formam um
vetor com k dimensões no espaço n-dimensional;
• o valor de do vetor de D na dimensão k é o peso de k em D,
p(k,D)
• todos m documentos de uma base de documentos formam m
vetores;
• os termos de uma consulta C também formam um vetor com
pesos p(k,C)
• procura-se os vetores de documentos mais próximos do vetor da
consulta
Modelo Vetorial
Vantagens sobre o modelo Booleano:
• considera termos ponderados
• recupera documentos que não casam com todos termos da
consulta
• permite rankeamento do resultado;
Modelo Vetorial
Temos então dois vetores:
n = número de termos
dk = k-ésimo documento
pci = peso do i-ésimo termo na consulta
pki = peso do i-ésimo termo no documento dk
• c = <pc1,pc2,...,pcn>
• dk = <pk1,pk2,...,pkn>
• A proximidade é dada pelo coseno do ângulo entre os vetores c e d
• sim(c,dk) = (c  d) / (|c| X |dk|) =
i=1..n pki X pci
= ______________________________________
 i=1..n pki2 x  i=1..n pci2
sim(c,dk)
Modelo Vetorial
Obtenção dos pesos:
tf = freq (k,D) (freqüência do termo k no documento D)
idf = log (N / nk) (inverse document frequency), onde N
é o número de documentos na coleção e nk número de
documentos em que o termo ocorre.
tfidf = freq (k,S) log (N / nk) (inverse document frequency),
é o peso do termo k no documento D
Modelo Vetorial
EXEMPLO:
um novo documento d2 contém as
palavras
na base de 2048 documentos ocorrem:
– ‘petróleo’ em 128 deles
– ‘petróleo’ 18 vezes
– ‘Brasil’ em 16 deles
– ‘refinaria’ 8 vezes
– ‘ refinaria’ em 1024 deles
teríamos os cálculos:
Vetor com tf : <‘petróleo’: 18, ‘ refinaria’: 8>
cálculo com tfitf (‘petróleo’)= 18*log(2048/128) = 18*1,2 = 21,6
tfitf (‘Brasil’)= 0
tfitf (‘refinaria’)= 8*log(2048/1024) = 8*0,3 = 2,4
Logo temos o vetor d2 = <21.6, 0, 2.4>
Modelo Vetorial
EXEMPLO:
um novo documento d3 contém as
palavras
– ‘petróleo’ 10 vezes
– ‘Brasil’ 10 vezes
na base de 2048 documentos ocorrem:
• ‘petróleo’ em 128 deles
• ‘Brasil’ em 16 deles
• ‘ refinaria’ em 1024 deles
teríamos os cálculos:
Vetor com tf : <‘petróleo’: 10, ‘Brasil’: 10>
cálculo com tfitf (‘petróleo’)= 10*log(2048/128) = 10*1,2 = 12
tfitf (‘Brasil’)= 10*log(2048/16) = 10*2,1 = 21
Logo temos o vetor d3 = <12, 21, 0>
Modelo Vetorial
temos os vetores
EXEMPLO:
d1 = <4.8, 16.87, 3>
Seja a consulta com
d2 = <21.6, 0, 2.4>
tf : <‘petróleo’: 1, ‘Brasil’: 1, ‘ refinaria’: 1>
d3 = <12, 21, 0>
c = <1.2, 2.1, 0.3>
i=1..n pki X pci
•
= ______________________________________= (1.2x4.8 + 2.1x16.87+0.3x3)
 i=1..n pki2 x  i=1..n pci2
(23.04+284.6+9) x (1.44+4.41+0.09)
sim(c,d1)
sim(c,d1) = (5.76+ 35.43+0.9) / 316.64 x 5.94) = 42.09 / (17.794x2.44) = 42.1/43.4=0.97
Modelo Vetorial
temos os vetores
EXEMPLO:
d1 = <4.8, 16.87, 3>
Seja a consulta com
d2 = <21.6, 0, 2.4>
tf : <‘petróleo’: 1, ‘Brasil’: 1, ‘ refinaria’: 1>
d3 = <12, 21, 0>
c = <1.2, 2.1, 0.3>
i=1..n pki X pci
•
= ______________________________________= (1.2x21.6 + 2.1x0+0.3x2.4)
 i=1..n pki2 x  i=1..n pci2
(466.56+5.76) x (1.44+4.41+0.09)
sim(c,d2)
sim(c,d2) = (25.95+0.72) / 472.32 x 5.94) = 26.67 / (21.73x2.437) = 26.67/52.956=0.50
Modelo Vetorial
temos os vetores
EXEMPLO:
d1 = <4.8, 16.87, 3>
Seja a consulta com
d2 = <21.6, 0, 2.4>
tf : <‘petróleo’: 1, ‘Brasil’: 1, ‘ refinaria’: 1>
d3 = <12, 21, 0>
c = <1.2, 2.1, 0.3>
i=1..n pki X pci
•
= ______________________________________= (1.2x12 + 2.1x21)
 i=1..n pki2 x  i=1..n pci2
(144+441) x (1.44+4.41+0.09)
sim(c,d3)
sim(c,d3) = (14.4+44.1) / 585 x 5.94) = 58.5/ (24.187x2.437) = 58.5/58.94 = 0.992
sim(c,d1) = (5.76+ 35.43+0.9) / 316.64 x 5.94) = 42.09 / (17.794x2.44) = 42.1/43.4= 0.97
sim(c,d2) = (25.95+0.72) / 472.32 x 5.94) = 26.67 / (21.73x2.437) = 26.67/52.956= 0.50
Modelo Vetorial
Problemas com o modelo vetorial:
• mudanças na base
• os termos são independentes entre si
• Se um documento discute petróleo no Brasil e futebol na Argentina
irá atender a uma consulta sobre petróleo no futebol.
Modelo Vetorial Generalizado
Permite relacionar termos entre si
por vetores chamados minterms:
• dado um vetor de palavras chave:
•c = <p1,p2,...,pn>, para associar pc1 com pc3 ele é combinado com o minterm
•m5 = <1,0,1,0...,0> e é considerado um fator de correlação c13
este modelo é controverso suas vantagens não
são consolidadas
Feedback de relevância
Como reduzir problemas de terminologia e relevância?
• Um thesaurus (mais genérico, estático)
• Um ambiente interativo (personalizado, dinâmico)
Feedback de relevância:
itens relevantes são usados para refazer os pesos nos
termos da consulta e expandí-la
Feedback de relevância
A partir da consulta original C0 é calculada uma
nova consulta C’.
Dados
• C0 o vetor da consulta original
• r o número de itens relevantes
• DRi os vetores dos itens relevantes
• nr o número de itens irrelevantes
• DNRj os vetores dos itens irrelevantes
Temos
C` = C0 + (1/r) i=1..r DRi – (1/nr) i=1..nr DNRi
Feedback de relevância
Original
C` = C0 + (1/r) i=1..r DRi – (1/nr) i=1..nr DNRi
Variante
C` = C0 + i=1..r DRi –  i=1..nr DNRi
Feedback positvo = i=1..r DRi
Feedback negativo =  i=1..nr DNRi
Feedback de relevância
Feedback positivo
relevante
irrelevante
Feedback negativo
Feedback de relevância
temos os vetores
d1 = <5, 15, 3>
a consulta c = <1.2, 2.1, 0.3>
d2 = <20, 0, 2>
d3 = <12, 20, 0>
• Suponhamos que d3 e d2 são relevantes e d1 não
•Temos r = 2, nr = 1 e sejam  = 1,  = (1/r * 1/2) = ¼ e  = (1/nr * ¼) = ¼
Então
c’ =  C0 + (<20,0,2>+<12, 20,0) – (5,15,3>) =
= 1<1.2, 2.1, 0.3> + ¼ (<20+12, 0+20, 2+0> - ¼ (5, 15, 3>
= <1.2, 2.1, 0.3> + ¼ <27, 5, -1> = <7.95, 3.35, 0.05>
Feedback de relevância
a consulta c = <1.2, 2.1, 0.3>
temos os vetores
d1 = <5, 15, 3>
d2 = <20, 0, 2>
Obtivemos
 C’ = <7.95, 3.35, 0.05> <8, 3.4, 0.1>
d3 = <12, 20, 0>
Reaplicando:
i=1..n pki X pci
•
= ______________________________________= (1.2x12 + 2.1x21)
 i=1..n pki2 x  i=1..n pci2
(144+441) x (1.44+4.41+0.09)
sim(c,d3)
Modelo Probabilístico
Sabendo-se que, dado
uma consulta c e
uma coleção de N documentos
Existe um conjunto de Rc ou R documentos relevantes para c.
Dado um documento d considera-se
P(R|d) a probabilidade de d ser relevante (estar em R), e
P(R-1|d) a probabilidade de d não estar em R
Define-se
sim(d,c) = P(R|d) / P(R-1|d) = (P(d|R) x P(R)) / (P(d|R-1)xP(R-1))
Sendo P(d|R) a probabilidade de um d qualquer ser de R
Temos, então: sim(d,c)  P(d|R)/ P(d|R-1)
Modelo Probabilístico
Dado uma consulta c um documento d e um termo t
Podemos dividir a coleção em
R o número de documentos relevantes para c.
N o número total de documentos
nt ou n número de documentos contendo t, e
rt ou r o número de documentos não contendo t
+
-
+
r
n-r
n
-
R-r
N-n-R+r
N-n
R
N-R
N
Modelo Probabilístico
+
-
+
r
R-r
R
n-r
N-n-R+r
N-R
n
N-n
N
Fórmulas alternativas para a distribuição dos termos entre
documentos relevantes e não-relevantes, determinando o
peso wt ou w de t na consulta c:
F1:
w1 = log( (r/R) / (n/N))
F2:
w2 = log( (r/R) / ((n-r)/N-R)) )
F3:
w3 = log ( (r/((R-r)) / (N/(N-n)) )
F4:
w4 = (r/(R-r)) / ((n-r)/((N-n-R+r)) )
Experimentalmente a fórmula F4 se mostrou a mais adequada
Modelo Probabilístico
SIMILARIDADE sem necessidade de uma análise
preliminar de relevância
(revisão probabilística de F4)
sim1(c, dj) = i=1..Q(C + log((N-ni) / ni )
sim2(c, dj) = i=1..Q(C + idfi) * fij )
Sendo
Sendo
Q = o número de termos comuns
entre dj e c
fij = K + (1-K) (freqij / maxfreqj)
C = uma constante de regulagem
(p.ex. = 1)
maxfreqj = a frequência de algum
termo em dj
ni = o número de documentos contendo ti
idfi = log (N / ni) (idf de ti em D)
N = o número total de documentos
K = uma constante de ajuste (para
documentos pequenos 0.5,
senão, 0.3)
freqij = a frequência de ti em dj
Modelo Probabilístico - Exemplo
Suponhamos a base de documentos
petróleo
refinaria
Brasil
Argentina
jogo
nacional
d1
4
10
8
0
0
3
0
0
d2
0
0
5
3
0
3
0
0
d3
1
0
3
3
2
0
0
1
d4
0
0
0
8
7
0
2
4
d5
5
8
2
2
0
5
0
2
d6
0
0
4
0
6
1
5
2
c
1
1
2
1
1
0
1
0
Tot
al
10
18
22
16
15
12
7
9
A base tem 109 palavras
futebol
transporte
Modelo Probabilístico - Exemplo
Calcular
Petróleo
sim1(c, dj) = i=1..Q(C + log((N-ni) / ni )
Refinaria
Brasil
Argentina
Futebol
Transporte
Total
ni
Q=
C=1
ni =
N=
(o número de termos comuns entre dj e c)
(uma constante de regulagem (p.ex. = 1)
(o número de documentos contendo ti
(o número total de documentos)
Jogo
Nacional
freq
/
f
d1
Petróleo
refinaria
Brasil
Argentina
futebol transporte
jogo
nacio- Q
nal
4/
10/
8/
0/
0/
3/
0/
0/
d2
0/
0/
5/
3/
0/
3/
0/
0/
d3
1/
0/
3/
3/
2/
0/
0/
1/
d4
0/
0/
0/
8/
7/
0/
2/
4/
d5
5/
8/
2/
2/
0/
5/
0/
2/
d6
0/
0/
4/
0/
6/
1/
5/
2/
c
1/
1/
2/
1/
1/
0/
1/
0/
Modelo Probabilístico - Exemplo
max
-freq
ni
idfi
Q=
(o número de termos comuns entre dj e c)
N=
(o número total de documentos)
maxfreqj =
(freq do termo max. no documento)
K = 0,5
(constante de ajuste)
idfi = log (N / ni)
(idf de ti em D)
ni =
(número de documentos contendo ni)
fij = K + (1-K) (freqij / maxfreqj)
sim2(c, dj) = i=1..Q(C + idfi) * fij )
freq
/
f
d1
Petróleo
refinaria
Brasil
Argentina
futebol transporte
jogo
nacional
4/
10/
8/
0/
0/
3/
0/
0/
d2
0/
0/
5/
3/
0/
3/
0/
0/
d3
1/
0/
3/
3/
2/
0/
0/
1/
d4
0/
0/
0/
8/
7/
0/
2/
4/
d5
5/
8/
2/
2/
0/
5/
0/
2/
d6
0/
0/
4/
0/
6/
1/
5/
2/
c
1/
1/
2/
1/
1/
0/
1/
0/
Tota
l
10
18
22
16
15
12
7
9
Modelo Probabilístico - Exemplo
A base tem 109 palavras
cálculo com tfitf (‘petróleo’)= 4*log(109/10) = 4*1,2 = 4,15
tfitf (‘refinaria’)= 10*log(109/18) = 7,82
tfitf (‘Brasil’)= 8*log(109/22) = 5,56, tfitf (‘transporte’)= 3*log(109/12) = 2,87
Logo temos o vetor d1 = <4.15, 7.82, 5.56, 0, 0, 2.87, 0, 0>