MINISTERUL EDUCAIEI, TINERETULUI I SPORTULUI AL REPUBLICII MOLDOVA

UNIVERSITATEA TEHNIC DIN MOLDOVA

CATEDRA INFORMATIC, CALCULATOARE I MICROELETRONIC

MANAGEMENT INFORMAIONAL

Lucrare de curs La Procesarea informaiei nestructurate

Tema: Metode de cutare a informaiei

Elaborat de:

Burlacu Vasilii, st. gr. MI-131

Verificat de:

Popescu Anatol, lector superior,

confereniar, profesor universitar

CHIINU 2015

2

Cuprins

Cuprins ................................................................................................................... 2

1. Introducere ....................................................................................................... 3

2. Metode de cutare a informaiei ...................................................................... 5

2.1. Metoda boolean. Metoda boolean standard .............................................. 5

2.1.1 O prim ncercare de a crea un index inversat ....................................... 8

2.1.2 Procesarea interogrilor Booleene ....................................................... 11

2.1.3 Metoda boolean extins vs. cutarea clasat ...................................... 15

2.2 Metoda propabilistic ................................................................................. 18

2.2.1 Teoria probabilitii de baz ................................................................ 18

2.2.2 Principiul probabilitii dup rating (PRP) .......................................... 19

2.2.3 Cazul 1/0 .............................................................................................. 19

2.2.4 PRP cu costuri de cutare .................................................................... 20

3. Motoare de cutare ........................................................................................ 21

4. Concluzii ........................................................................................................ 23

5. Bibliografie .................................................................................................... 24

3

1. Introducere

Informaia reprezint totalitatea datelor noi pe care le analizm, le prelucrm i le

gestionm n raport cu un lucru pe care il cunoatem deja sau e ceva nou pentru noi.

Informaia poate fi orice. Luai buletinul Dvs. din portmoneu i trecei cu vederea

asupra lui. Citii numele i prenumele deintorului. Aceasta este deja o informaie.

Cutarea informaiei reprezint o aciune pe care o ntreprindem cu scopul de a

gsi date adiionale sau noi despre un anumit lucru. Putem cuta i obine informaie

nou fie de la alte persoane, bibliotec sau internet.

De cele mai multe ori cutm informaia n documente stocate fie pe calculatorul

personal sau pe alte servere, adic, documente digitale.

Cutarea informaiei este o activitate pe care o ntreprindem cu scopul de a obine

resurse relevante pentru informaia dorit dintr-o multitudine de resurse cu informaie.

Cutarea poate fi bazat pe metadate sau pe texte ntregi indexate.

O cutare ncepe atunci cnd o persoan introduce o interogare n sistemul de

cutare. Interogrile sunt declaraii oficiale a necesitilor de informare, de exemplu

iruri de cutare n motoarele de cutare web. n cutarea de informaii, o interogare

poate s identifice nu numai o singur resurs dintr-o colecie. n schimb, mai multe

resurse pot s coincid cu interogarea efectuat. Resursa este o entitate de informaii

pstrat ntr-o baz de date. Cele mai multe sisteme de cutare calculeaz un scor

anume prin care se reprezint ct de bine fiecare resurs coincide cu interogarea

efectuat.

Metodele pe care le folosesc aceste sisteme de cutare sunt:

- Metoda boolean

- Metoda probabilistic (statistic)

Modelul probabilistic de cutare se bazeaz pe principiul probabilitii ratingului,

care prevede c un sistem de informaii de cutare ar trebui s aranjeze documentele n

4

baza probabilitii lor de relevan pentru interogarea efectuat, avnd n vedere toate

documentele disponibile.

Trebuie de menionat c nu toat informaia este structurat i clar pentru

computerele pe care ruleaz sistemele de cutare. Din aceast cauz, este necesar s se

structurizeze un anumit set de date, s se nvee maina de calcul n ceea ce privete

limbajul omului.

n lucrarea dat se va analiza procesul de indexare a informaiei, metodele de

cutare a informaiei, unele momente specifice ale motoarelor de cutare i cteva

reguli pentru o cutare eficient.

5

2. Metode de cutare a informaiei

Urmtoarele metode majore au fost dezvoltate pentru a prelucra informaii:

metoda Boolean, metoda statistic (probabilistic), care includ spatiul vectorial i

modelul de regsire probabilistic, precum i metode lingvistice i modelele bazate pe

cunotine. Primul model este adesea menionat ca "potrivire exact"; cel din urm ar

fi "cele mai bune" rezultate care coincid.

2.1 Metoda boolean. Metoda boolean standard

Vom explica aceast metod utiliznd un exemplu.

S lum cartea Shakespeares Collected Works. S presupunem c Dvs. Dorii

s gsii care piese de teatru conin cuvintele Brutus AND Caesar AND NOT

Calpurnia. O metod ar fi s citii toat cartea i s notai unde se ntlnete Brutus i

Caesar i nu este Calpurnia.

Desigur c acest process va lua mult timp.

Pentru un computer, ns, nu va fi att de greu din considerentul modernizrii i

caracteristicilor puternice ce cresc n fiecare an. Un computer va scana fiecare

document i va procesa informaia. Acest process este cunoscut ca grepping printre

texte. Aceast metod este foarte eficient lund n consideraie performana

calculatoarelor cotidiene. Cu calculatoare moderne, pentru interogarea simpl de

colecii modeste (dimensiunea lucrrilor lui Shakespeare colectate, un pic sub un

milion de cuvinte de text n total), ntr-adevr nu trebuie nimic mai mult.

Dar, pentru mai multe scopuri, este nevoie de ceva mai mult:

1. Procesarea rapid a coleciilor mari de documente. Cantitatea de date

online a crescut la fel de repede cum a crescut performanaa

calculatoarelor, i de aceea am dori ca acestea s fie capabile s proceseze

trilioane de cuvinte din mai multe colecii.

6

2. Flexibilitatea operaiunilor de cutare. De exemplu, este imposibil de

realizat interogarea Romands NEAR countrymen cu grepping, unde

NEAR poate fi definit ca n 5 cuvinte sau n aceeai propoziie.

3. Clasarea cutrii. De multe ori se dorete cele mai bune rezutlate printre

documentele care conin cuvintele asemntoare din interogare.

O cale pentru a evita scanarea textelor din fiecare document la fiecare interogare

este indexarea documentelor n prealabil. Vom folosi n continuare colecia lui

Shakespeare i vom explica bazele metodei booleene pentru cutarea informaiei.

S presupunem c nregistrm pentru fiecare document o pies de teatru de

Shakespeare acesta conine fiecare cuvnt din toate cuvintele folosite de

Shakespeare (Shakespeare a folosit aproximativ 32.000 cuvinte diferite). Rezultatul

este un document cu o matrice de inciden binar, ca n figura 1.1. Termenii sunt

unitile indexate; acestea sunt, de obicei, cuvinte.

Acum, n dependen dac privim la coloanele sau rndurile tabelei, noi putem

avea un vector pentru fiecare termen, care arat documentele care apar n colecie, sau

un vector cu toate documentele i termenii care apar n document.

Pentru a rspunde la Brutus AND Caesar AND NOT Calpurnia, vom lua

vectorii pentru Brutus, Caesar i Calpurnia, o completm pe ultima i apoi facem p

legtur:

110100 AND 110111 AND 101111 = 100100

Metoda boolean de ctuare a informaiei este o metod de cutare n care noi

putem cuta orice interogare cu termenii speciali, care sunt AND, OR i NOT. Aceast

metod vizualizeaz fiecare document ca un set de cuvinte.

Acum considerm o situaie mai realistic, simultan utiliznd posibilitatea de a

introduce careva notaii i terminologii. Prespunem c avem N = 1 milion de

documente.

7

Prin documente avem n vedere orice unitate pe care vrem s dezvoltm un

sistem de cutare. Ele pot fi secvene din agenda personal sau coleci de crii din

bibliotec. Noi ne vom referi la acele documente prin care nelegem utilizarea unor

colecii. Presupunem fiecare document are lungimea de circa 1000 cuvinte. Dac

presupunem c fiecare cuvnt ar avea 6 bii, inclusive spaiul i semnele de punctuaie,

atunci un document ar avea aproximativ 6Gb. Tipic, pot fi M = 500.000 termeni

distinci n acest document. Nu este nimic special n numerele selectate. Ele pot fi

diferite. Dar, ele ne du o idee despre dimensiunile tipurilor de problem pe care noi

trebuie s le rezolvm.

Un sistem de cutare are ca scop s aduc la cunotin documentele cu coleciile

relevante unei informaii necesar i arbitrar, comunicat sistemului de ctre sensurile

din interogare. O informaie necesar,este o tem despre care utilizatorul dorete s

cunoasc mai multe, i este diferit de ctre o interogare, ceea ce utilizatorul ncearc s

comunice calculatorului prin interogarea scris n sistemul de cutare. Un document

este important dac acesta conine informaie apropiat i util pentru interogarea

efectuat de utilizator. Exemplul nostru de mai sus este unul mai mult abstract,

fiindc, de obicei utilizatorul caut ceva de genul scurgerea conductelor i ar dori s

gseasc documente relevante cu aceast tem i care conin cuvinte din aceeai sfer,

sau explic aceeai tem, cum ar fi ruperea conductelor.

8

Pentru a sesiza eficiena sistemului de cutare, utilizatorul ar dori s tie dou

momente statistice despre rezultatele oferite de ctre sistemul de cutare:

Precizia ce coefficient din rezultatele oferite sunt relevante ctre informaia

necesar ?

Retragerea ce coefficient din documentele relevante din colecie au fost retrase

de sistem ?

Ideea de baz n cutarea informaiei este indexarea inversat.

Aceast denumire este puin tautologic: un index ntodeauna merge napoi de la

termeni la prile de document unde ei apar. Cu toate acestea, indexarea inversat, sau

uneori un fiier inversat, a devenit un termen standard n cutarea de informaii.

Conceptul de baz a unui index inversat este artat n Figura 1.3.

Se ine un dicionar cu termeni (uneori este numit i vocabular sau lexicon, noi

utilizm dicionar pentru datele structurate i vocabular pentru un set de termeni). Pe

urm, pentru fiecare din termeni avem o list de nregistrri cu documentele n care

apar termenii. Fiecare element din list care nregistrri a crui termen a aprut n

document (i,mai trziu, mai des, poziia n document) este convenional numit

postare. Lista este pe urm numit o list de postri ( sau o list inversat), i toate

listele cu postri luate mpreun sunt referite ca pstri. Dicionarul din Figura 1.3 este

sortat alfabetic i fiecare list cu postri este sortat dup ID-ul documentului.

2.1.1 O prim ncercare de a crea un index inversat

Pentru a obine beneficii n viteza de indexare, trebuie s construim indexarea din

timp. Principalele etape ale acestei indexri sunt:

1. Colectarea documentelor care urmeaz sa fie indexate.

2. Transformarea fiecrui document ntr-o list de tokens.

9

3. Preprocesarea lingvistic, producnd o lista de tokens normalizate, numite

termeni de indexare.

4. Indexarea documentelor n care fiecare termen provine din crearea unui

index inversat format din dicionar i nregistrri.

n continuare vom defini i discuta etapele anterioare de prelucrare.

Vom precuta construirea unui index inversat de baz cu indexarea bazat pe

sortare.

ntr-o colecie de documente, vom presupune c fiecare document are un numr

de serie unic, cunoscut sub numele de identificator de documente (docId). n timpul

construciei index, putem atribui pur i simplu numere ntregi succesive la fiecare

document nou atunci cnd este ntlnit prima dat. Intrarea spre indexare constituie o

list de tokens normalizate pentru fiecare document, pe care o putem primi i ca o list

de termeni i docId-uri. Etapa de baza n indexare este sortarea listei, astfel ca termenii

s fie n ordine alfabetic. Apariiile multiple ale aceluiai termen ntr-un document

sunt apoi combinate. Exemplele de ntilnire a unuia i aceluiai termen sunt apoi

grupate, iar rezultatele se mpart ntr-un dicionar i postri. Deoarece un termen

anume apare ntr-o serie de documente, aceast stocare a datelor reduce cerinele de

10

stocare a indecelui. Dicionarul nregistreaz, de asemenea, unele statistici, cum ar fi

numrul de documente care conin fiecare termen. Aceast informaie nu este vital

pentru un motor de cutare de baz de tip Boolean, dar ne permite de s mbuntim

eficiena motorului de cutare n timp de interogare, i este o statistic utilizat ulterior

n mai multe modele de recuperare clasate pe locuri. Postrile sunt sortate secundar

dup docId. Acest lucru ofer baza pentru prelucrarea eficient a interogrii.

Noi dorim ca rezultatul indexrii s fie depozitat n dicionar, ct i n liste de

nregistrri. Dicionarul este frecvent pstrat n memorie, iar listele cu nregistrri sunt

inute pe disc. Ce structur de date trebuie s fie folosit pentru o list de nregistri?

Tabloul de lungime fixat ar fi o risip deoarece unele cuvinte apar n mai multe

documente, iar altele foarte rar. Pentru memorarea listelor de nregistrri, dou

alternative bune sunt listele individual legate sau reelele de lungime variabil. Listele

individual legate permit nserarea uoar a documentelor n lista de nregistrri ,i ,n

mod normal, se ntlnesc pe strategii de indexare mai avansate . Masivele de lungimi

variabile ctig n cerinele de spaiu prin evitarea indicilor de deasupra i micorarea

de timp, deoarece utilizarea continue a memoriei crete viteza de procesare. Indicii

suplimentari pot fi codificai n liste ca compensai. Dac actualizrile sunt relativ

rare, lungimea matricei variabile va fi mult mai compact i mai uor de parcurs.

Putem folosi, de asemenea, un sistem hibrid cu o list legat de tablouri de lungime

fix pentru fiecare termen. Cnd listele de nregistrri sunt stocate pe disc , acestea

sunt stocate ca nregistrri fr indici explicit, astfel nct pentru a minimiza

dimensiunea listelor de nregistrri i numrul pe disc se caut i se citete o list

dintr-o memorie.

11

Table 1.0 Caracteristicile definitorii ale metodei booleene standard i lista de

avantaje i dezavantaje ale acesteia.

2.1.2 Procesarea interogrilor Booleene

Cum procesm o interogare utiliznd indexarea invers i metoda Boolean de

cutare a informaiei ? Se consider procesarea unei interogri conjuctive simple:

Brutus AND Calpurnia

utiliznd indexarea invers parial din figura 1.3 :

1. Gsim pe Brutus n dicionar

2. Recptm postrile acestuia

12

3. Gsim Calpurnia n dicionar

4. Recptm postrile acestuia

5. Intersectm aceste dou postri aa cum este afiat n figura 1.5.

Operaia de inresectare este una crucial: este necesar ca interesectarea postriloe

s fie eficient, astfel nct s fie posibil cutarea rapid a documentelor care conin

ambii termeni. (aceast operaiune este cteodat numit ca fuziunea listelor cu postri:

acest nume puin contraintuitiv reflect termenul fuziunea algoritmului pentru o

familie general de algoritmi ce combin mai multe liste sortate lsnd pointeri

avansai n fiecare din acestea)

Exist o metod simpl i efectiv de intersectare a listelr de postri utiliznd

algoritmul fuziunii (figura 1.6): se rein pointerii n fiecare din liste i se merge prin

ambele lsite de postri simultan, ntr-un timp liniar din numrul total de postri

nregistrate.

13

La fiecare pas se compar docID-ul fixat de ambii pointeri. Dac sunt la fel, se

memoreaz acest docID n lista cu rezultate, se avanseaz ambii pointeri. n caz

contrar se avanseaz pointerul ce fixeaz docID-ul cel mai mic. Dac lungimile listelor

de postri sunt x i y, intersecia ia forma O(x+y) de operaii. Formal, complexitatea

interogrii este O(N), unde N este numrul de documente n colecie.

Metodele de indexare obin doar o constant, nu o diferen n complexitatea

timpului O comparat la o scanarea liniar, dar n practic aceast constant este foarte

mare. Pentru a utiliza acest algoritm, este foarte important ca postrile s fie sortate

dup un singur metod global. Utilizarea unei sortri numerice dup docID este una

din cele mai simple metode pentru a atinge acest scop.

Se poate de extins operaia de intersectare utiliznd un proces mult mai complicat

cu interogarea: (Brutus OR Caesar) AND NOT Calpurnia.

Optimizarea interogrii este un proces de a selecta cum s organizm lucrul

pentru o interogare n aa mod nct s fie un lucru ct mai puin pentru sistem pentru

a gsi rezultatul. Un element important al acesteia pentru interogrile Booleene este

ordinea n care listele postrilor sunt accesate. Care este cea mai bun ordine pentru

procesarea interogrilor? S considerm o interogare n care este un AND de t

termeni, pentru nceput: Brutus AND Caesar AND Calpurnia.

Pentru fiecare din t termeni, trebuie s obinem postrile acestora, apoi s le unim

mpreun cu AND. Euristica principal este de a procesa termenii n ordinea creterii

frecvenei documentului: dac se ncepe cu intersectarea a 2 cele mai mici postri,

atunci toate rezultatele intermediare nu trebuie s fie mai mare ca cea mai mic

postare, i astfel putem s facem un lucru ct mai puin posibil. Deci, pentru lista de

postri din figura 1.3 noi putem executa interogarea de mai jos ca: (Calpuria AND

Brutus) AND Caesar.

14

Aceasta este o prim justificare pentru a ine frecvena termenilor n dicionar: ea

ne permite s lum aceast decizie de sortare bazat pe datele din memoria intern

nainte de a accesa oricare list de postri.

S considerm acum o optimizare a unei interogri mult mai generale, cum ari fi:

madding OR crowd) AND (ignoble OR strife) AND (killed OR slain).

Ca i mai nainte, se va lua fecvena tuturor termenilor, dup care se poate de

estimat mrimea fiecrui OR prin suma fiecrei frecvene a disjuncilor lui. Dup

aceasta se poate de procesat interogarea n ordinea crescnd a mrimii fiecrui termen

disjunctiv.

Pentru interogrile booleene arbitrare, avem de a evalua i stoca temporar

rspunsurile pentru exprimarea intermediar ntr-o expresie complex. Cu toate

acestea, n multe situaii, fie din cauza naturii limbajului de interogare, sau doar pentru

c acest lucru este cel mai comun tip de interogare care utilizatorii o prezint, o

interogare este pur i simplu conjunctiv. n acest caz, mai degrab dect vizualizarea

listelor postrilor fuzionate ca o funcie cu dou intrri i o ieire distinct, este mai

eficient s se intersecteze fiecare list cu postri cu rezultatul curent intermediar n

memorie, unde am iniializat rezultatul intermediar ncrcnd lista de postri a

termenului mai puin frecvent. Acest algoritm este afiat n figura 1.7. Operaia de

intersecie este asimetric: rezultatele listelor intermediare sunt n memorie atta timp

ct lista este citit de pe disk. Mai mult ca att, lista rezultatelor este ntodeauna cel

puin att de scurt ca i alte liste, i n multe cazuri este n ordinea mrimilor mai

mici. Interseciile postrilor nc pot fi efetuate dup algoritmul din figura 1.6, dar

cnd se face diferena dintre lungimile listelor este foarte mare, oportunitatea de a

utiliza alte tehnici devine realitate.

15

Intersecia pote fi calculat altfel modificnd substanial sau marcnd ca nevalid

itemii din lista rezultatelor intermediare. Sau intersecia poate fi calculat ca o

secven de cutri binare n lista postrilor mari pentru fiecare postare din lista

rezultatelor intermediare. Alt posibilitate este s se pstreze lista postrilor mari ntr-

un hastable, astfel nct un item membru rezultatele intermediare s fie calculat ca o

constant dect liniar sau log time. Cu toate acestea, astfel de tehnici sunt dificile de

combinat cu lista postrilor compresate. Mai mult aca att, operaiile de interesecatre a

listelor cu postri standarde rmn necesare cnd ambii termeni a unei interogri sunt

comune.

2.1.3 Metoda boolean extins vs. cutarea clasat

Metoda boolean extins se confrunt cu metodele de cutare clasate, cum ar fi

metoda vectorului n spaiu, n care utilizatorul utilizeaz pe larg interogrile cu texte

mari, ceea ce este, de fapt, tiprirea a unuia sau mai multe cuvinte neinnd cont de

limb i fr operatori pentru a crea o interogare bun; sistemul de cutare decide care

documente satisfac cel mai bine interogarea. Pentru o perioad foarte ndelungat,

metoda booleana fost singura utilizat de oamenii de tiin i implementat de ctre

companiile ce ofereau informaie. Dar, acestea nu utilizatu metoda boolean simpl.

Metoda simpl limiteaz foarte mult rezultatele oferite de ctre sistemul de cutare.

Din aceast cauz, oamenii nu primeau ca rezultat informaia necesar la interogarea

efectuat de ei.

16

De aceea, aceste sisteme au fost mbuntite cu ali operatori, cum ari fi

proximitatea itemilor. Un operator proximatic este o metod de specificare ntr-o

interogare c doi termeni trebuie s fie asemntor unul cu cellalt ntr-un document,

unde asemnarea poate fi msurat prin limitarea numrului cuvintelor interogate sau

prin referina la unei uniti structurale cum ar fi o propoziie sau un paragraf.

Vom ncerca s explicm proximitatea utiliznd un exemplu.

Cutarea boolean comercial Westlaw: este cel mai mare serviciu de cutare

legal, cu mai mult de jumtate de milion de utilizatori ce efectueaz milione de cutri

pe zi prin zei de terabii de date. Westlaw a fost creat n 1992 cu metoda boolean

simpl, iar mai trziu s-a adugat i proximitatea.

Iat cteva exemple de interogri:

Informaia necesar: Informaii privind teoriile juridice implicate n prevenirea

divulgarri de secrete comerciale de angajai care au fost angajai de o companie

concurent. Interogare: "trade secret"/s disclos! /s prevent/s

employe!

Informaie necesar: Cerine pentru persoanele cu handicap pentru a putea accesa

un loc de munc. Interogare: disab! /p access! /s work-sitework-place

(employment/3 place)

Informaie necesar: Cazuri despre responsabilitatea unei gazde pentru oaspei

beai. Interogare: host! /p (responsib! liab!) /p (intoxicat! drunk!)

/p guest

Atragei atenie la interogrile lungi, precise i utilizarea operatorilor de

proximitate, ambele mai puin frecvente n cutare pe web. Interogrile transmise au n

mediu 10 cuvinte lungime. Spre deosebire de conveniile de cutare web, un spaiu

ntre cuvinte reprezint disjuncie (operatorul de legtur mai strns), & este AND i

/s, /p, i /k pentru asemnri n aceeai propoziie, acelai paragraf sau n k cuvinte

respectiv. Ghilimelele duble semnific cutarea n fraz (sau cuvinte consecutive).

17

Semnul de exclamare (!) ofer o interogare wild card suplimentar; astfel liab!

potrivete toate cuvintele incepand cu liab. n plus work-site se potrivete cu

oricare din worksite, work-site sau work site. Interogri expert tipice sunt de

obicei atent denite i dezvoltate treptat pn cnd acestea obin ceea ce ar fi rezultat

bun pentru utilizator.

Muli utilizatori, n special profesioniti, prefer metoda interogrii booleene.

Interogrile booleene sunt precise: un document corespunde fie interogrii de

cutare sau nu. Acest lucru ofer utilizatorului un control mai mare i transparena

peste ceea ce este adus. i unele domenii, precum materialele juridice, permit un

mijloc eficient de clasare a documentelor n cadrul unui model Boolean: Westlaw

ntoarce documentele n ordine cronologic invers, care este n practic destul de

eficient. n 2007, majoritatea librriilor despre legi nc par s recomande termeni i

conectori pentru cutri, i majoritatea utilizatorilor juridici cred c obine un control

mai mare de folosindu-le. Cu toate acestea, acest lucru nu nseamn c interogrile

booleene sunt mult mai eficiente pentru cuttorii profesionali. ntr-adevr,

experimentarea pe o subcolecie n Westlaw, Turtle (1994) a gsit c interogrile de

text liber produse au rezultate mai bune dect interogrile booleene pregtite de pe

Westlaw de bibliotecari pentru majoritatea nevoilor de informare n experimentele

sale. O problem general cu interogrile booleene este c folosind operatorii AND

tinde s produc nalt precizie dar numr sczut de cutri, n timp ce se folosete

operatorul OR se ofer precizie sczut, dar numr mare de cutri, i este dificil sau

imposibil alegerea unui rezultat satisfctor.

18

2.2 Metoda propabilistic

Pentru a cuta informaie, utilizatorii ncep cu aceea c au nevoie de informaie,

transpus n reprezentri de intertogare. n mod similar, sunt documente transpuse n

reprezentri de documente (acele din urm difer prin aceea c textul deja are

tokenuri,dar poate conine mai puin informaie fundamental atunci cnd se folosete

poziionarea neindexat).

Bazat pe acestea, un sistem de cutare ncearc s determine ct de bine satisfac

documentele interogarea scris. n metoda boolean sau a spaului vectorial,

asemnarea este mai mult formal, dar semantic imprecise din cauza calculului

termenilor indexai. Avnd n vedere doar o singur interogare, sistemul de cutare nu

nelege cu desvrire ce informaie se dorete. De asemenea, sistemul de cutare nu

gsete cu mare precizie documentul cu informaia necesar dup interogarea i

documentul dat. Pentru un rezultat mai bun i cu certitudine, metoda probabilistic

ofer o baz de raionament. n continuare vom cerceta cu ajutorul acestei metode cu

ct documentul este relevant pentru interogarea data.

Exist mai multe modele de cutare a informaie bazate pe ceast metod, dar n

contiuare vom explica Principiul Probabilitii Ratingului.

2.2.1 Teoria probabilitii de baz

Explicaiile ce urmeaz presupun c cititorul deja are bazele despre teoria

probabilitilor.

O variabil A reprezint un eveniment. Echivalent se poate de notat subsetul de

de evenimente prin o variabil random, ce este o funcie a rezultatelor aleatoare a

numerelor reale; subsetul este domeniul n care variabila A are anumite valori.

Deseori, nu vom cunoate dac un evenient este real i posibil n viaa real. Noi

putem ntreba probabiltiatea unui eveniment 0 P(A) 1. Pentru dou evenimente A

i B, intersecia evenimentelor nu este altceva dect probabilitatea interseciilor

19

evenimentelor A i B, adic P(A|B). Probabilitatea condiionat P(A|B) nu este

altceva dect probabilitatea evenimentului A astfel nct evenimentul B va avea loc.

Relaia fundamental dintre intersecia i probabilitatea condiionat este redat de

regula lanului:

P(A, B) = P(A B) = P(A|B)P(B) = P(B|A)P(A).

Fr a face orice presupuneri, probabilitatea unui eveniment comun este egal cu

probabilitatea de unuia dintre evenimente nmulit cu probabilitatea altui eveniment

condiionat de cunoaterea c primul eveniment sa ntmplat.

Scriind P(A) pentru a completa un eveniment, vom obine:

P(A, B) = P(B|A)P(A)

Teorie probabilitilor are o regul numit regula partiiilor, care spune: dac un

eveniment B este este divizat n mai multe subdiviziuni, atunci probabilitatea lui B

este nimic altceva dect suma probabilitilor acestor subdiviziuni. Un caz special al

acestei regule ne spune c:

P(B) = P(A, B)+ P(A, B)

De aici noi putem obine regula lui Bayes pentru a inversa probailitatea

condiionat:

2.2.2 Principiul probabilitii dup rating (PRP)

2.2.3 Cazul 1/0

Presupunem un program de cutare une este o colecie de documente, utilizatorul

scrie o interogare i este returnat o list ntreag de rezultate posibile. Pentru o

interogare q i un document d din colecie, presupunem Rq,d este un indicator de o

20

variabil aleatoare ce ne spune dac d este relevant cu certitudine fa de interogarea q.

Acestea fiind, aceast variabil ia valoarea 1 dac documentul este relevant i 0 n caz

contrar. n continuare, de cele mai multe ori vom folosi doar R n loc de Rq,d.

Utiliznd metode probabilistic, forma corect de prezentare a documentelor

utilizatorului este de a da o not (rating) pentru fiecare document n conformitate cu

informaia relevant pe care o deine util utilizatorului: P(R = 1|d, q). Aceasta este

baza principiului probabilitii bazae pe rating (PRP).

n cel mai simplu caz de PRP, nu exist costuri de cutare sau altceva ce ar strica

aciunile sau ar produce erori. Dvs. pierdei sau pentru ntoarcerea a unui documente

nerelevant, sau pentru euarea de ntoarcere a unui document relevant (aceasta este o

situaie n care suntei evaluai pentru acurateea Dvs. este numit pierderea 1/0).

Scopul este de a returna cele mai bune k documente n topul listei, pentru orice valoare

k utilizatorii aleg. n acest caz, simplu PRP spune s se fac rating la toate

documentele n ordine cresctoare a P(R = 1|d, q). Dac exist o list de rezultate

pentru a fi afiate, mai degrab o ordine, regula deciziei optimale a lui Bayes, decizia

ce minimizeaz riscul pierderii, este simplu de a returna documentele care sunt cel mai

aproape posibil relevante dect nerelevante:

d is relevant if P((11.6) R = 1|d, q) > P(R = 0|d, q)

Teorem. PRP este optimal n sensul n care el minimizeaz riscul pierderii (

cunoscut ca i riscul lui Bayes ) n ceea ce privete pierderile 1/0.

2.2.4 PRP cu costuri de cutare

S presupunem c lum un model de cutare cu costuri. S presupunem c C1

este costul pentru returnarea unui rezultat (document) relevant cutrii, i C0 pentru

costul n cazul n care se returneaz un rezultat irelevant. Atunci, PRP spune c, dac

pentru un anume document d i pentru toate documentele d nepreluate (neprelucrate)

C0 P(R = 0|d) C1 P(R = 1|d) C0 P(R = 0|d) C1 P(R = 1|d)

21

atunci d este documentul ce trebuie prelucrat. Un astfel de model ofer un cadru

formal unde noi putem modela diferite costuri pentru false pozitive i false negative,

chiar i probleme de performan n stajul de modelare, mai degrab dect simplu n

etapa de evaluare.

3. Motoare de cutare

Motoarele de cutare pe internet sunt cele mai frecvente i cele mai cunoscute

aplicaii ale problemei de cutare a informaiei.

Motoarele de cutare pe internet sunt sisteme software special pentru cutarea de

informaii n WWW. Rezultatele cutrii de cele mai dese ori sunt prezetate ntr-o

form de list, i pot fi att colecii de pagini web, ct i sunete audio, video, imagini

sau alte tipuri de documente.

Motoarele de cutare menin informaia up-to-date datorit roboilor i pionilor

ce cerceteaz ntreg WWW pentru actualizarea informaiei. Aceast activitate a

roboilor este numit web crawling.

Primul motor de cutare a fost denumit Archie, creat de ctre Alan Emtage, Bill

Heelan i J. Peter Deutsch, studeni n tiin la universitatea McGill din Montreal.

Acesta descrca toate fiierele directoriilor localizate n FTP-uri publice, crend o baz

de date cu denumirile fiierelor posibile de cutat. ns, Archie nu indexa coninutul

site-urilor i FTP-urilor din cauz c toato informaia de pe pagini era prea puin i

putea fi cutat manual.

Un motor de cutare funcioneaz n felul urmtor:

1. Web crawling

2. Indexare

3. Cutare

utiliznd metodele descrise mai sus.

22

Motoarele de cutare web funcioneaz prin stocarea de informaie despre mai

multe pagini de web, prelucrnd HTML de la pagini. Aceste pagini sunt preluate de un

crawler Web (un pianjen) care urmeaz dup fiecare link pe site. Proprietarul site-

ului pot exclude anumite pagini utiliznd robots.txt.

n continuare, motorul de cutare analizeaz coninutul paginilor pentru a

determina cum trebuie indexate (de exemplu, cuvintele pot fi extrase din titul paginii,

coninutul paginii, din titluri sau din taguri special numite meta-tags). Datele n cele

din urm sunt salvate ntr-o baz de date pentru utilizarea recent n interogri.

Cnd utilizatorul scrie o interogare n motorul de cutare (de obicei utiliznd

cuvinte cheie), motorul analizeaz indexii acesteia i afieaz o list ntreag de pagini

web cu cele mai apropiate potriviri i un scurt coninut al paginii unde se alf

asemnarea.

23

4. Concluzii

Cutare informaiei nu este un process dificil atta timp ct avem sursele la

ndemn i materialul este puin. ns, odat ce informaia pe care o cutm trebuie

extras din mai multe surse i din mai multe colecii, un singur om nu ar putea s

descurce cu acest misiune, utiliznd metoda manual. De aceea au fost dezvoltate

motoare de cutare ce uureaz cu mult acest process. Trebuie de menionat faptul c

pentru funcionalitatea acestor siteme de cutare s-a simit nevoia de anumte metode

de cutare.

Metodele principale pe care le folosesc aceste maini sunt metoda boolean i

probabilistic. Fiecare dintre acestea au i cteva dezvoltri, mbuntiri. Evident,

aceste metode posed att plusuri ct i minusuri n algoritmul lor de lucru. Astfel,

metoda boolean este mult mai eficient cnd se dorete ca rezultatul cu interogarea s

se asemene 100%. Ea funcioneaz mai bine cnd se caut cteva cuvinte cheie. n

cazul cnd se caut o fraz sau mbinri de cuvinte, intervine cu un rezultat mai bun

metoda probabilistic.

Pentru a oferi rezultate mai bune la interogrile utilizatorilor, majoritatea

motoarelor de cutare folosesc mai multe metode, combinate.

24

5. Bibliografie

1 - Documentare on-line pentru programe i proiecte, Lector univ. dr. Traian Turc

2 - , http://bibliofond.ru/view.aspx?id=445637

3 An introduction to informational retrieval, Christopher D.Manning, Prabhakar Raghvan,

Hinrich Schutze, Online Edition (C) 2009 Camgridge UP

4 - http://en.wikipedia.org/wiki/Information_retrieval

5 - http://comminfo.rutgers.edu/~aspoerri/InfoCrystal/Ch_2.html#2.3, Informationa Retrieval

Methods

6 - http://en.wikipedia.org/wiki/Web_search_engine