Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.sai.msu.su/~megera/postgres/talks/algebra-fts-II.pdf Äàòà èçìåíåíèÿ: Mon Jan 12 19:03:48 2009 Äàòà èíäåêñèðîâàíèÿ: Thu Jan 15 01:39:54 2009 Êîäèðîâêà: Ïîèñêîâûå ñëîâà: m 2

Algebra for full-text queries II
Oleg Bartunov, Teodor Sigaev, Mikhail Prokhorov Moscow University, Sternberg Astronomical Institute 2008


$: BEFORE (AFTER)


2 a $[n] b == i,j : pos(b)i ­ pos(a)j = n



r BEFORE ($n)




() -- a BEFORE b ( b AFTER a) c n (default is 1)


: $[m,n] ..


a $[m,n] b == i,j: m pos(b)i ­ pos(a)j n a $[n] b == i,j: pos(b)i ­ pos(a)j > n ..








$


a $ [n ] b = b $ [-n ] a !(a $[n] b) = i,j : pos(b)i ­ pos(a)j != n !!(a $[n] b) = a $[n] b a $ !b = a & ( i,j : pos(!b)i ­ pos(a)j = 1) !a $ b = b & ( i,j : pos(b)i ­ pos(!a)j = 1 ) !a $ !b = ( i,j : pos(!b)i ­ pos(!a)j = 1 ) a $ (b | c) = a $ b | a $ c (b | c) $ a = b $ a | $ a a $ (b & c) = b & & (a $ b | a $ c); (b & c) $ a = b & & (b $ a | $ a)





a $[n] b ­ b n a ( a n b) a $[n] b = b $[-n] a ­ n , -n () !(a $[n] b) ­ b n a !!(a $[n] b) = a $[n] b ­ $











a $ !b ­ a b !a $ b ­ b a !a $ !b ­ a, b






$ AND OR


a $ (b | c) ­ a b (b | c) $ a ­ b a a $ (b & c) ­ a b (. ) (b & c) $ a ­ b a (. )











a $[n] b == i,j : pos(b)i ­ pos(a)j = n



a $[n] b == a & b & ( i,j : pos(b)i ­ pos(a)j = n)



: (a b),


$


!(a $[n] b) == i,j : pos(b)i ­ pos(a)j != n



a $[n] b == !a | !b | ( i,j : pos(b)i ­ pos(a)j != n )



: (a b),


$ &


$ &: a $ (b & c) : a $ (b & c) = (a $ b) & (a $ c) ­ a $ b a $ a $ (b & c) = b & & (a $ b | a $ c) ­ b a: (a $ b | a $ c) 'some' $ 'telefonsvarer' => 'some' $ ('telefon' & 'svar') 2-







a $ !b ­ . . . ab . . . ab . . . aab . . . ab . . . X X X a $[2] !b ­ ... abb ... acb ... aabb ... azb ... a $[<3] !b ­ ... ... acb ... aabb ... azb ...





X aX bb

X

X



!a $ b ­ . . . ab . . . ab . . . aab . . . ab . . . X X X !a $ !b ­ . . . ab . . . ab . . . ax . . . xb . . . xy . . . X X X X n 0 -> aaa...aaabbb...bbb <- m0






$


a [xyz] b <=> a $ (x | y | z) $ b a.b <=> a $[2] b





a . . . b <=> a $[4] b a .* b <=> a $[1,] b





a [xy]{1,2} b <=> a $ (x | y | x$x | x$y | y$x | y$y) $ b


(>2 )
: 1) a ... b ... ... b ... d ... . . . ... x - 2)
$ $[4] $[<3] $[3,7] $[n] ... $[m] -

: posL ­ posR ­

*) posL posR **) $ $[n] posR(A)-posL(A) = ni ***) "a": posL(a)=posR(a)=pos(a)


$
= (a $ b $ ... y $ z), B = (a1 $ ... $ z1), A $[n] B == i,j : posL(B)i ­ posR(A)j = n



a $[na] b $[nb] ... x $[nx] y $[ny] z == ia,ib,...,iy,iz: pos(b)ib pos(c)ic ... pos(y)iy pos(z)iz ­ pos(a)ia = na & ­ pos(b)ib = nb & ­ pos(x)ix = nx & ­ pos(y)iy = ny



A == (a1 $[na] b1 ... y1 $[ny] z1) ==
ia,ib,...,iy,iz: pos(b1)ib ­pos(a1)ia=na & ... & pos(z1)iz ­ pos(y1)iy=ny

B == (a2 $[ma] b2 ... y2 $[my] z2) ==

ja,jb,...,jy,jz: pos(b2)jb ­pos(a2)ja=ma & ... & pos(z2)jz ­ pos(y2)jy=m

y

A $[k] B == i,j : posL(B)i ­ posR(A)j = k =>
posR(A) =pos(z1) & posL(B)=pos(a2) => ia,...,,iz,ja,...,jz: pos(b1)ib ­ pos(a1)ia = na & ... & pos(z1)iz ­ pos(y1)iy = n & pos(a2)ja ­ pos(z1)iz = k &

y


:
. , .


(2 +1)
(a $[n] b) $[m] c
= (a $[n] b) & & (i,j: posL(c)j ­posR("ab")i=m) => (a $[n] b) & c & (i,j: pos(c)j ­ posR("ab")i = m ) => (a & b & (k,l: pos(b)k ­ pos(a)l = n)) & c & (i,j: pos(c)j ­ posR("ab")i = m ) = =a&b&c& (k,l: pos(b)k­pos(a)l=n) & (j: pos(c)j­pos(b)k = m ) = = a & b & c & (j,k,l: pos(b)k­pos(a)l=n & pos(c)j ­pos(b)k=m) = =

a $[n] b $[m] c

: a $[n] (b $[m] c) = a $[n] b $[m] c



| $ $ | «m33» & Query: «close» $ «galaxies» => «close» $ «m33» | ( «close» $ («andromeda» $ «nebulae»)) | ( «magellanic» & «clouds» & ( «close» $ «magellanic» | «close» $ «clouds»)) |

«close» «close»

$

&

«nebulae»

«andromeda»

«magellanic»

«clouds»

$ «close»

$ «magellanic» «close» «clouds»





a $ b a $[ n] b

(n1) (nm) (mm1 & n1n)

a $[ m ] b a $[ n] b b$ca$b$c$d

a $[m1,n1] b a $[m,n] b

TRUE => TRUE ­



1: 4? 1 2 1 4? a $ b $ c $ d $ e $ f $ g $ c $ d $ h $ i $ . .. $ x $ y $ z |<------------ 3 ------------>| 2: ([1] ­ , [n] ­ ) [ 1] [ m ] [ 2] [ n] a $ b $ c $ d $ e $ f $ g $ h $ ... $ x $ y $ x 5? 1 4? 3? 2