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