Pretraživanje - definisanje Bulovog upita-
|
|
|
Čime je definisan zahtjev za pronalaženje informacija?
Zahtev IR sistemu za pretraživanjem indeksa definisan
je upitom.
|
Postoji više tipova upita, a mi ćemo razmotriti tzv. Bulov upit (engl.
Boolean query), nazvan po istoimenoj Bulovoj logici na
čijim principima se zasniva.
Bulov upit definisan je logičkim izrazom koji se sastoji od
operatora i operanada.
Operand se posmatra kao primitivan upit (nedeljiv, tipa jedna reč) ili
podupit (tipa drugi Bulov upit, između zagrada). Osnovni
operatori su konjunkcija, disjunkcija i negacija.
Bulov upit moguće je izvršiti na par načina, konkretno sa ili bez
normalizacije izraza. Ovdje je objašnjen postupak bez normalizacije.
Bez upotrebe normalizacije, ugnježdeni upiti se prvi izvršavaju te se
njihovi rezultati posmatraju kao rezultati primitivne pretrage i onda se
spajaju sa ostatkom upita.
Ova funkcionalnost trivijalno se može implementirati rekurzivnim
algoritmom.
Rezultati primitivnog upita je ništa više do lista
dokument identifikatora, opcionalno sa pratećim meta podacima,
npr. na koliko mesta u dokumentu se upit pronalazi.
Ovi meta podaci koriste se za rangiranje i pretraživanje fraza. U ovom
kontekstu može se smatrati da je za svaki operand upita dobavljena po
jedna lista identifikatora, koja se u slučaju primitivnih operanada
jednostavno učitava iz invertovane datoteke.
|
Nakon što se operandi obrade, izvršavaju se operatori
između njih i nastaje nova lista dokumenata koja predstavlja rezultat
upita. Prvo se svi operandi grupišu u tri grupe: obavezni,
poželjni i nedozvoljeni.
|
Ove grupe su optimalniji način predstavljanja upita od klasičnog Bulovog
izraza.
Na primer, umesto: foo A bar A - foobar A (java V python)
Lakše je: +foo +bar +(java python) -foobar
U drugom slučaju, svi operandi koji počinju sa znakom “plus” članovi su
obavezne grupe i njihove liste dokumenata se presecaju. Izračunavanjem
preseka pojedinačnih listi pronalazi se lista dokumenata zajednička za
sva tri operanda. Na primer, ako su dva operanda u grupi sa listama 1,
3, 5, 7 i 3, 4, 7, 9 onda je presek lista 3, 7.
Operandi koji ne počinju znakom minus ili plus su tipa “poželjni ali
neobavezni”, tako da se između njihovih listi pravi unija. Na primer,
unija prethodnih listi je 1, 3, 4, 5, 7, 9. Glavna svrha poželjnih
operanada jeste da se da nagoveštaj pretraživaču prilikom rangiranja,
ali i kao obična disjunkcija (u smislu java ili python).
I poslednje, operandi koji počinju sa znakom minus su nedozvoljeni i
između njih se takođe izvršava unija, čime se dobija lista nedozvoljenih
(čvrsto nepoželjnih) dokumenata.
|
Ove tri grupe (od kojih neke mogu biti i prazne) se
spajaju u konačan rezultat upita. Tu postoje posebni slučajevi.
Kada su sve tri grupe neprazne, rezultat je:
|
|
Formula izgleda suvišno zakomplikovana jer se čini da
je R = O \ N.
Ipak, prilikom izračunavanja preseka i unije ne proizvodi se samo lista
dokument identifikatora, već se uz svaku dokumentld vrednost čuva i
ocena. Ocena se pozitivno menja ukoliko se u dokumentu nalaze poželjne
reči.
Ukoliko ne postoje obavezni operandi, onda: R = P\N.
Slučaj u kom je neprazan jedino skup nedozvoljenih operanada
nije praktičan i obično se ne implementira. Ukoliko je ipak
potreban, onda se omogućava dodavanjem posebnog termina u svaki dokument
te izračunavanjem negacije u odnosu na listu svih dokumenata koja se
dobija upitom u taj poseban termin. Time se dobija “skup svih
dokumenata”.
Optimalna implementacija ovog algoritma podrazumeva pametno
izračunavanje preseka, iterativno, te
kvalitetno izračunavanje ocene u toku izvršavanja.
Algoritam traženja unije ubrzava se upotrebom strukture heap (prev.
gomila). Ukoliko se traži unija od m listi sa ukupno n elemenata,
konstruiše se heap kapaciteta m. Pronalaženje sledećeg člana unije je
prvi član heap-a, te je složenost te operacije konstantna.
Međutim, pošto je ažuriranje heap-a logm operacija, onda je konačna
složenost O(nlogm).
|
Primjer kreiranja invertovanog indeksa na osnovu sadržaja
tri dokumenta
Nakon što upit izračuna konačnu listu,
potrebno je iz skladišta učitati odgovarajuće dokumente, te prezentovati
ih korisniku, na način koji odgovara korisniku IR sistema.(analiziraj
sliku topika Faze kreiranja indeksa).
|
|
copyright M2M
BL-2011/14
|