Pagina documente » Informatica, Matematica » Motor de cautare pe web

Cuprins

lucrare-licenta-motor-de-cautare-pe-web
Aceasta lucrare poate fi descarcata doar daca ai statut PREMIUM si are scop consultativ. Pentru a descarca aceasta lucrare trebuie sa fii utilizator inregistrat.
lucrare-licenta-motor-de-cautare-pe-web


Extras din document

Cuprins
Introducere
Partea I
Prezentarea conceptelor implicate
1.1 INTERNET
1.1.1 ARPANET
1.1.2 NSFNET
1.1.3 Internet-ul
1.1.4 Adrese IP
1.2 WORLD WIDE WEB
1.2.1 Prezentarea WWW
1.2.2 HTML si URI
1.3 UNIX
1.3.1 Introducere
1.3.2 Istoria UNIX
Partea II
Proiectarea si implementarea
motorului de cautare
2.1 SPECIFICAREA CERINTELOR
2.1.1 Abstractizarea cerintelor
2.1.2 Limitari ale posibilitatilor de realizare a obiectivelor si probleme care trebuiesc solutionate
2.1.3 Observatii privind alegerea cerintelor aplicatiei curente
2.1.4 Specificarea propriu zisa a cerintelor
2.2 STRATEGIILE ALESE IN IMPLEMENTARE
2.2.1. Spider-ul
2.2.2 Observatii asupra bazei de date
2.3 IMPLEMENTAREA
2.3.1 Alegerea strategiilor de implementare
2.3.2 Spider-ul
Bibliografie

Alte date

?Motor de cautare pe WEB pg: {p}

?Introducere

Pana in 1990 Internetul a fost folosit cu precadere de catre cercetatori din domeniul academic, guvernamental si industrial. Cateva aplicatii (de exemplu e-mail*, telnet, ftp) erau intr-adevar de interes mai larg. Dar ceea ce a facut ca popularitatea sa sa creasca fara precedent, in randul a milioane de utilizatori din toate domeniile, a fost o aplicatie noua, WWW (World Wide Web - sau mai simplu : WEB). Acesta aplicatie, inventata de fizicianul Tim Berners Lee de la CERN, nu a modificat nici una din facilitatile existente, in schimb le-a facut mai usor de folosit. Impreuna cu programul de navigare Mosaic, scris la Centrul National pentru Aplicatiile Supercalculatoarelor, WWW-ul a facut posibil ca un sit sa puna la dispozitie un numar de pagini de informatii continand text, imagini, sunet si chiar imagini video in miscare, in fiecare pagina existand legaturi (referinte) catre alte pagini, lagaturi care puteau referi orice alta informatie din WWW. Printr-un sinplu “clic” cu mouse-ul pe o legatura, utilizatorul este imediat “transportat” la pagina indicata de legatura, oriunde in lume. De exemplu multe firme au pe WEB o pagina principala cu intrari care trimit la pagini cu informatii asupra produselor, liste de preturi, reduceri, suport tehnic (online), comunicare cu angajatii, informatii despre actionari, etc. Pagina poate contine si referinte la paginile altor sucursale (departate geografic) ale aceleiasi firme, toate putand fi accesate ca un tot unitar.

Intr-un timp foarte scurt au aparut alte tipuri de pagini: hartio, tabele de cotatii la bursa, cataloage de biblioteca, programe radio inregistrate si chiar pagini continand textele complete ale unor carti carora le-au expirat drepturile de autor (Mark Twain, Charles Dickens, etc). De asemenea multi oameni au pagini personale (home pages).

In primul an de la lansarea Mosaic-ului, numarul de servere WWW a crescut de la 1000 la 7000. Aceasta enorma crestere va continua, fara indoiala, in urmatorii ani si va reprezenta, probabil, forta care va conduce tehnologia si utilizarea Internet-ului in mileniul III. Informatia de pe WEB se mareste in fiecare secunda, noi si noi posibilitati deschizandu-se. Dar dupa o era de explozie a informatiei trebuie in mod necesar sa apara si o era de structurare a sa. Multe pagini WEB au inca o structura haotica, libertatea de legare a paginilor ducand deseori la structuri greu de urmarit si inteles. Pe langa acest aspect caruia in ultimul timp i se acorda o mai mare atentie, volumul mare de informatii creeaza inca o problema : problema gasirii si regasirii informatiei dorite. Daca pentru regasirea informatiei fiecare utilizator isi poate creea “Bookmarks-uri” cu diferite structuri, cautarea unei informatii este o sarcina mult mai grea. Adeseori cere experienta si chiar noroc. Din punct de vedere al structurii, WEB-ul reprezinta un graf cu o mare conectivitare (se poate avansa conjectura ca 90% din el este un graf conex, langa care coexista insulite mici neconectate). Astfel ca teoretic, pornind de la o pagina situata in aceste cel mai mare subgarf conex, poti parcurge 90% din informatia de pe Web, de fapt cvasitotalitatea informatiei de larg interes. Algoritmi de parcurgere si cautare intr-un graf conex exista. Dar problema nu este gasirea unui algoritm de parcurgere, ci timpul necesar acestei cautari, datorita dimensiunii grafului. Se pot imagina automate care sa caute pe Internet (pe nivele de exemplu, cautarea in adancime avand un grad prea mare de recursivitate), dar parcurgerea informatiilor intregului Web - datorita si vitezei conexiunilor - este o sarcina practic imposibila.

De aceea se cauta noi modalitati de structurare a informatiilor pe WEB. S-a inceput cu liste de pagini principale, cu o descriere sumara a ceea ce se gaseste pe respectivul sit. Aceasta a dat rezultate o vreme, dar in scurt timp listele au capatat dimensiuni enorme, trecandu-se la structurarea lor pe domenii si subdomenii. Dar si acestea s-au dovedit a nu fi in stare sa ofere o cantitate de informatii suficienta utilizatorului care vrea sa caute ceva pe WEB. Munca de intretinere a informatiilor era enorma, si chiar solutia de a lasa in sarcina realizatorului paginilor desrierea acestora si inscrierea in baza de date nu garanta veridicitatea informatiilor si controlul “expirarii” informatiei - mutare, modificare, stergere. O idee novatoare a fost inventarea unor “Motoare de cautare” (numite si “masini de cautare”, “roboti de cautare”, “web spiders”, etc). Ele au sarcina sa parcurga subarbori ai grafului Internet cu scopul de a strange informatii despre continutul paginilor gasite. Volumul de informatii este enorm, eterogenitatea lor este foarte mare, deci gasirea unui algoritm de extragere automata a informatiilor semnificative pentru o pagina nu este un lucru foarte usor. Desi majoritatea paginilor au un titlu, aceste este de cele mai multe ori prost ales, nespunand mare lucru despre pagina in sine (ex: “Pagina lui Ghiorghita”). Exista mai multe euristici de extragere a informatiilor semnificative despre o pagina. Unele motoare de cautare retin titlul, textele senzitive care duc la pagina, texte puse in evidenta. Altele incearca sa retina si cuvintele care apar mai des in pagina (exceptandu-le pe cele care nu sunt semnificativa (conjunctii, verbe). Aceasta ultima strategie are dezavantajul ca necesita un timp computational al motorului de cautare prea mare. Varianta de rulare pe fiecare sit a unui program de parcurgere a paginilor este greu acceptabila datorita problemelor de securitate care pot apare.In ultimele versiuni HTML (Hypertext Markup Language) - formatul de scriere al paginilor WEB au fost introduse TAG-uri (portiuni de text HTML care au in general ca scop sa instruiasca programul de vizualizare al paginii cum sa afiseze textul, imaginile, etc) prin care se pot specifica in mod explicit - de catre autorul paginii - descrieri ale paginii si cuvinte cheie care sa trimita la pagina respectiva. Aceasta ar fi o solutie de viitor, dar multi producatori de pagini web nu includ in paginile lor aceste TAG-uri, din necunoastere sau comoditate. O combinare a acestor strategii pare a fi solutia la momentul actual.

Alta problema este orientarea cautarii intr-un mod pragmatic. Daca un motor de cautare ar indexa (parcurge si strange referinte despre) o mare parte a Internet-ului, la sfarsitul indexarii primele pagini ar fi deja expirate (modificat continutul, mutate sau sterse). In acelasi timp ar trebui selectate informatiile de larg interes, in dauna celor personale de exemplu sau a celor de interes local. Exista TAG-uri prin care producatorii pot specifica ca paginile respective nu “merita” a fi indexate dar extrem de putini fac efortul de a le include in paginile lor, mai ales ca de obicei orice producator crede ca pagina lui este importanta. In acelasi timp, o cautare haotica poate ajunge in zone ale Internet-ului pline de pagini “abandonate” de proprietarii lor - pagini neactualizate, pagini de incercare, etc. De aceea se prefera in general sa se indexeze pe cat posibil pagini la cererea posesorului - in premisa ca cel care are ceva important de prezentat isi va da interesul sa isi promoveze produsele. In lipsa acestor cereri de indexare (care apar in general dupa ce motorul de cautare a capatat o oarecare popularitate) se poate merge recursiv pe link-urile (legaturile) externe extrase din paginile deja existente. Probabilitatea ca unj motor de cautare sa ajunga intr-un punct mort (sa termine de indexat intreg subgraful conex din care porneste) este practic nula. In afara de aceasta se pot stabili si politici de “reindexare” in ideea ca referintele deja existente despre pagini mai vechi pot fi incorecte.

In viitor ar trebui gasite si alte solutii pentru problemele care apar - volumul din ce in ce mai mare de date, supraincarcarea nodului de retea in care se face indexare, scaderea vitezei de transmitere a datelor odata cu “departarea” de nodul in care se strang informatiile. In aceste conditii, utilizarea in viitor a motoarelor de cautare tematice, regionale sau cu intercooperare este previzibila. Serverele de baze de date actuale s-ar putea dovedi ineficiente, fiind necesare noi principii de organizare si distribuire a informatiei

In conluzie, proiectarea si realizarea unui motor de cautare este o sarcina dificila, trebuind sa indeplineasca o seama de conditii ca:

* capaciate de stocare mare

* cautare rapida

* euristica bine aleasa, cu posibilitati de schimbare a ei in functie de noile tendinte de organizare a paginilor observate pe web

* posibilitati de adaugare cu efort minim a altor metode de extragere a informatiilor din pagini si de orientare a cautarii.

* posibilitatea de implementare pe numeroase platforme, pentru a beneficia de ultime noutati hardware.

* sistem de operare gazda multitasking si orientat pe tehnologia client - server.

* posibilitati de extindere a motorului de cautare la un sistem distribuit.

* posibilitati de implementare ulterioara de alte metode de cautare in baza de date deja existenta

* robustete: aplicatia trebuie sa faca fata posibilelor caderi de tensiune, blocaje in retea fara a fi nevoie interventia unui specialist pentru a o reinitializa

* posibilitati de a accesa alte tipuri de servere de baze de date

* posibilitati de coexistare in acelasi timp a mai multor tipuri de organizari a datelor, de exemplu pentru a inlocui treptat un tip de organizare cu altul.

Lucrarea de fata isi propune sa urmareasca realizarea unei aplicatii “Motor de cautare” care sa indeplineasca cat mai bine aceste cerinte. Ca sistem de operare gazda este ales UNIX-ul (sau clona sa mai recente Linux) pentru robostetea sa in gestionarea resurselor si a proceselor concurente, pentru implementarea sa puternica a socketurilor si a algoritmilor de gestionare a conexiunilor TCP/IP . In afara de aceaste, UNIX este ales si pentru faptul ca ofera o securitate foarte buna, un motor de cautare fiind susceptibil la atacuri distructive de diferite tipuri, UNIX-ul rezolvandu-si slabiciunile la foarte scurt timp de la aparitia vulnerabilitatii. Portabilitatea sa pe aproape toate tipurile de platforme hardware nededicate.

Limbajul de programare ales este C/C++, pentru flexibilitatea lui si compromisul intre facilitatile de nivel inalt si portabilitatea cu accesul larg la resursele sistemului, permitand sa se realizeze optimizari in sectiunile critice ale programului.. In acelasi timp este ales si pentru facilitatile sale de ascundere a datelor si de compilare separata pe module.

Documentatia prezenta contine doua parti, prima detaliind conceptele fundamentale care intervin in acest proiect (notiuni, protocoale, specificatii). A doua parte este dedicata proiectarii programului, urmarind specificarea cerintelor, motivatiile diferitelor solutii alese si functionarea diferitelor module. Ca anexa este prezentat codul sursa al programului.

Partea I

Prezentarea conceptelor implicate

1.1 INTERNET

1.1.1 ARPANET

La mijlocul anilor 1960, cand Razboiul Rece era in punctul culminant, DoD-ul a vrut o retea de comanda si control care sa poata supravietui unui razboi nuclear. Traditionalele retele telefonice cu comutare de circuite erau considerate prea vulnerabile, deoarece pierderea unei linii sau a unui comutator ar fi dus la distrugerea iremediabila a conexiunilor care o foloseau. Pentru a rezolva problema, DoD s-a orientat catre agentia sa de cercetare, ARPA (mai tardiu DARPA, acum ARPA din nou) : (Defence) Advanced Research Projects Agency - Agentia de Cercetare pentru Proiecte Avansate (de Aparare).

ARPA a fost un raspuns la lansarea Sputnik-ului de catre Uniunea Sovietica in 1957 si avea misiunea de a dezvolta tehnologia care putea fi utila scopurilor militare. ARPA nu avea savanti sau laboratoare, activitatea agentiei constand in furnizarea de fonduri si contracte universitatilor si firmelor care aveau idei promitatoare.

O parte din primele fonduri au mers catre universitati in vederea studierii comutarii de pachete, o idee radicala la acea vreme; idee fusese sugerata de Paul Baram intr-o serie de rapoarte ale Corporatiei RAND publicate la inceputul anilor 1960. Dupa discutii cu diversi experti, ARPA a decis ca reteaua de care avea nevoie DoD trebuia sa fie o retea cu comutare de pachete, constand intr-o subretea si din calculatoare gazda.

Subreteaua trebuia sa fie formata din minicalculatoare numite IMP-uri (Interface Message Processors - procesoare de mesaje de interfata) conectate prin linii de transmisie. Pentru o siguranta mai mare, fiecare IMP trebuia legat la cel putin alte doua IMP-uri. Subreteaua avea sa fie o subretea datagrama, astfel ca daca unele linii sau IMP-uri se defectau, mesajele puteau fi redirijate pe cai alternative.

In afara de subretea era insa nevoie de programe, asa ca Larry Roberts de la ARPA a convocat in vara anului 1969, la Snowbird, Utah, o intalnire intre cercetatori din domeniul retelelor, cei mai multi din ei proaspat absolventi de facultate. Absolventii se asteptau ca niste experti in retele sa le explice proie ctarea si software-ul retelei si ca fiecare din ei sa primeasca apoi sarcina de a scrie o parte din programe. Ei au ramas insa muti de uimire cand au constatat ca nu exista nici un expert in retele si nici o proiectare serioasa. Ei trebuiau sa-si dea seama singuri ce au de facut.

Cu toate aceste, in decembrie 1969 incepea deja sa functioneze o retea experimentala cu patru noduri, la UCLA, UCSB, SRI si Universitatea din Utah. AU fost alese aceste patru institutii, pentru ca toate aveau un numar mare de contracte cu ARPA si toate aveau calculatoare gazda diferite si complet incompatibile (doar ca sa fie treaba mai amuzanta). Pe masura ce se aduceau si instalau mai multe IMP-uri, reteaua crestea rapid; in scurt timp s-a intins pe tot spatiul Statelor Unite.

Mai tarziu, programele pentru IMP-uri au fost modificate pentru a permite terminalelor sa se lege direct la un IMP special, numit TIP (Terminal Interface Procesor - procesor de interfata a terminalelor), fara sa fie nevoie sa treaca printr-o gazda.

Pe langa ajutorul oferit pentru dezvoltarea tanarului ARPANET, ARPA a finantat de asemenea cercetari in domeniul retelelor de sateliti si retelelor radio cu pachete. Intr-o faimoasa demonstratie, un camion care circula in Californiafolosea reteaua radio pentru a trimite mesaje pentru SRI, aceste mesaje erau retransmise apoi prin ARPANET pe Coasta de Est, iar de aici mesajele erau expediate catre University College din Londra prin reteaua de sateliti. Acest lucru permitea unui cercetator din camion sa utilizeze un calculator din Londra, in timp ce calatorea prin California.

Aceste experiment a demonstrat totodata ca protocoalele ARPANET nu erau potrivite pentru a rula pe mai multe retele. Observatia a dus la noi cercetari asupra protocoalelor, culminand cu inventia modelului si protocoalelor TCP/IP. TCP/IP a fost special proiectat pentru a trata comunicatia prin inter-retele, un lucru care se dovedea din ce in ce mai important, pe masura ce noi retele se legau la ARPANET. Pentru a incuraja aceste noi protocoale, ARPA a semnat cateva contracte cu BBN si cu University of California din Berkeley pentru a integra protocoalele in Berkeley UNIX. Cercetatorii din Berkeley au dezvoltat o interfata de programare cu reteaua (soclurile) si au scris numeroase aplicatii, utilitare si programe care sa simplifice interconectarea.

Momentul era perfect. Multe universitati tocmai achizitionasera un al doilea sau al treilea calculator VAX si un LAN care sa le conecteze, dar nu aveau nici un fel de programe de interconectare. Cand a aparut 4.2BSD, cu TCP/IP, socluri si multe utilitare de retea, pachetul complet a fost adoptat imediat. Mai mult chiar, folosind TCP/IP, LAN-urile se puteau lega simplu la ARPANET, si multe LAN-uri au facut acest lucru.

In 1983, ARPANET-ul , cu 200 de IMP-uri si cu sute de gazde era stabil si se bucura de succes. In acest moment, ARPA a incredintat adiministrarea retelei Agentiei de Comunicatii a Apararii (Defense Communications Agency - DCA), pentru a o folosi ca retea operationala. Primul lucru pe care l-a facut DCA a fost sa izoleze portiunea militara (aproximativ 160 de IMP-uri din care 110 in Statele Unite si 50 in strainatate) intr-o subretea separata, MILNET, si sa prevada porti stricte intre MILNET si subreteaua de cercetare ramasa.

In timpul anilor 1980 au fost conectate la ARPANET multe alte retele, in special LAN-uri. Pe masura ce crestea dimensiunea retelei, gasirea gazdelor devenea tot mai costisitoare; de aceea a fost creat DNS (Domain Naming System - Sistemul Numelor de Domenii), care organiza masinile in domenii si punea in corespondenta numele domeniilor cu adrese IP. De atunci incoace, DNS a ajuns sa fie un sistem distribuit, generalizat, folosit pentru a memora diverse informatii referitoare la procedurile de atribuire a numelor.

In 1990 ARPANET-ul era deja surclasat de retele mai moderne carora le daduse nastere el insusi. Prin urmare, ARPANET-ul a fost inchis si demontat, dar el continua sa traiasca in inima si mintea specialistilor in retele de pretutindeni. MILNET functioneaza totusi in continuare.

1.1.2 NSFNET