Dušan Ječmenica Pretraživači (II deo)

U prošlom broju smo započeli priču o pretraživačima. Pošto smo se upoznali sa osnovnim stvarima vezanim za ovu problematiku hajde da malo da zavirimo "ispod haube" i da vidimo kako jedan, od trenutno najboljih pretraživača u trenutku pisanja ovog teksta - Google, radi. Ovo je priča koja može biti interesantna običnom "surferu" koji pretražuje Interent, ali mnogo više koristi može doneti web dizajnerima koji se trude da njihovi sajtovi budu visoko rangirani na listama pretrage.

Za početak – malo istorije

Ovde ne možete a da ne primetite, sličnost sa Bil Gates-om i njegovim studentskim danima.

1995. Sergey Brin i Larry Page su bila dva studenta na Univerzitetu Stenford (Stanford University) kada su se upoznali i rešili da naprave do tad neviđeno – najbolji pretraživač. Ovde ne možete a da ne primetite, sličnost sa Bil Gates-om i njegovim studentskim danima. Već 1997. gore pomenuta dvojica studenata su već napravili svoj prvi pretraživač koji je nosio ime BackRub i bio je preteča Googlea. Već 1998. osnivaju svoju firmu na nagovor ko-osnivača Yahoo-a, David Filo-a.
1999. se sele u University Avenue, Palo Alto, gde imaju preko pola miliona upita dnevno, a potom se sele u Mountain View, California. Rad Hat je postao njihov prvi zvanični klijent. Krajem iste godine imaju 39 zaposlenih i 3 miliona upita na dan! Na zapadu se obično kvalitet lako prepozna i nagradi, pa je Google dobio na desetine nagrada renomiranih računarskih časopisa. Već u 2000. god imaju 60 miliona upita na dan, i osposobljeni su za WAP tehnologiju. Tada plasiraju Google Toolbar™, plugin za browser koji pretragu čini lakšom. 2001. imaju 100 miliona upita dnevno i 10 jezički lokalizovanih verzija pretrage. Tu se onda mešaju mnoge kompanije poput Novell-a, AT&T, Lycos itd., pa 2002. god imaju 150 miliona upita dnevno, 3 milijarde indeksiranih web strana, 400 miliona slika, 1 milion PDF dokumenata, i dostupni su na 74 jezika, od kojih je jedan i – srpski. Tada patentiraju PageRank, jednistvenu tehnologiju za rangiranje rezultata pretrage. Preko 300 portala i pretraživača u preko 30 zemalja sveta se u tom trenutku oslanjalo na Google. Sada je taj broj daleko veći jer je Google postao broj jedan u svetu pretraživača. Na adresi http://labs.google.com/ možete se poigrati sa nezvaničnim najnovijim Google-ovim tehnologijama koje su još u beta-fazi testiranja.
Zbog izuzetnih dostignuća, Larry Page i Sergey Brin, su se našli na InfoWorld "Top Ten Technology Innovators" listi.

Ko mu nadenu takvo ime ?

Ime Google, predstavlja igru slova od reči GOOGOL koja označava broj 1 praćen sa 100 nula. Tu reč je izmislio devetogodišnji nećak matematičara Edward Kasner-a. Kasner mu je postavio zadatak da smisli ime za neki mnogo veliki broj - i eto šta sve može dečja mašta. Inače "googolplex" je "10 na googol." Ove reči se prvi put pominju 1940. god u knjizi Edward Kasner-a i James Newman-a: "Mathematics and the Imagination." Inače, indikativno je da za dobar marketing na internetu treba imati što otkačenije ime. To se vidi i na primeru Yahoo-a.

Arhitektura Google-a

Svaki dokument se konvertuje u skup reči koji se zovu hit-ovi.

Većina izvornog koda Google-a je napisana u C ili C++ i izvršava se kombinovano na Linuxu i Solarisu. Crawling ( spidering) se izvršava sa više uporednih spider-a. Postoji jedan URL server koji šalje listu URL-ova spider-ima da je posete. Strane koje su posećene se šalju posebnoj mašini koja se zove "store-server". On ih potom kompresuje i ostavlja ih u "skladište". Svakoj web strani koja je skladištena je pridružen jedan indentifikacioni broj(docID). Indeksiranje se vrši sa indexer-om i sort-erom. Indexer posećuje "skladište", dekompresuje elemente i rastavlja ih. Svaki dokument se konvertuje u skup reči koji se zovu hit-ovi. Oni sadži podatke o reči , njenu poziciju u dokumentu , veličinu fonta i tzv. kapitalizaciju (da li su velika ili mala slova). Indexer razdeljuje ove hit-ove u skup Barrel-a (buradi, bačvi), kreirajući delimično sortiranog preteču indexa (listinga). Indexer takođe radi još jednu bitnu funkciju: on izdvaja linkove sa web strana i smešta ih u jedan specijalan fajl.

Slika 1: Arhitektura Google-a

URLresolver analizira pomenuti fajl sa linkovima i konvertuje apsolutne linkove u relativne i onda ih pridružuje docID-ovima(Slika 1). On takođe smešta tekst iz linkova u gore pomeutu preteču index-a, i pridružuje je docID-ovima na koje pokazuju linkovi. Posle toga generiše bazu podataka sa linkovima koji odgovoaraju docID-ovima. Ta baza se koristi za izračunavanje PageRank-a i vrlo je bitna.
Sorter uzima barrel-e, koji su sortirani po docID-ovima, i ponovo ih sortira po wordID-ovima da generiše takozvani "obrnuti index" (inverted index). Sorter takođe generiše lisu wordID-ova i pridružuje ih obrnutom index-u. Program poznat kao DumpLexicon, uzima ovu listu i zajedno sa listom koja je nastala kao rezultat indexera, odgovara na zadati query tj. upit.

Document index i Lexicon

Ovaj deo pretraživača sadrži informacije o svakom dokumentu. Informacije u svakom zapisu sadrže trenutni status dokumenta, pokazivač na "skladište", rezime dokumenta i razne druge dodatne statističke podatke. Lexicon je ustvari rečnik koji sadrži preko 14 miliona reči ( od kojih su neke vrlo retke ). On se sastoji iz dva dela: liste reči i heš tabele pokazivača. (Heširanje je preslikavanje (mapiranje) ključeva u adrese podataka. To je postupak za traženje podataka izvođenjem neke aritmetičke operacije nad ključem za dobijanje adrese. Kod heširanja uvodi se koncept tabele. Ako sa k označimo ključ nekog podatka, mi primenjujemo neku transformaciju ključa h(k) i ona nam daje poziciju u tabeli gde se nalazi sam podatak ili informaciju o lokaciji (adresi) tog podatka.)

Hit list

Ovo je ujedno i najbitniji deo same baze podataka koji je trebalo projektovati da zauzme što manje prostora i da može veoma brzo da se pretraži. Nemojte ni sumnjati da je baš to i urađeno. Naime, u samoj hit listi se čuvaju podaci o rečima , njihovoj poziciji i kapitalizaciji i fontu. U samo procesu generisanja, Google inženjeri su mogli da krenu u optimizaciju na 3 različita načina: jednostavno kodiranje (sa tripletima celih brojeva), kompaktno kodiranje (ručno raspoređivanje bitova) ili Huffman-ovo kodiranje. (o Huffman-ovom kodu ste mogli pročitati u prošlom broju u članku "Kako radi Zip" kolege Marka Pertovića). Ali tvorci Goole-a su se ipak odlučili za varijantu broj 2, jer donosi mnogo više uštede u prostoru nego varijanta 1, a i dosta manje manipulacija sa bitovima nego Huffman-ov kod - što zahteva manje procesorskog vremena.

Slika 2: Raspored bitova u hit-u

To radi, otprilike, ovako: svaki hit zaizima 2 bajta u memoriji.(Slika 2) Postoje dve vrste hit-ova: plain (obični, sirovi) i fancy (ukrašeni). Fancy sadrže informacije o dodatnim hit-ovima (podhitovima): URL-u, title-u (naslovu HTML dokumenta), tekst samog linka (anchor hit) i META tag (ako ga ima). Plain hit-ovi sadrže sve ostalo: bit kapitalizacije (da li su slova velika ili mala), veličinu fonta i poziciju reči u dokumentu (sve preko 4095 se označava kao 4096). Veličina fonta se predstavlja kao relativna u odnosu na ostatak dokumenta i zauzima 3 bita (ustvari, samo je 7 vrednosti iskorišćeno, jer kombinacija "111" označava da se radi o fancy hit-u). Inače, fancy hit se satoji od 1 bita kapitalizacije, veličine fonta 7 (kombinacija "111" da se označi da je u opitanju fancy hit, 4 bita da se kodira vrsta fancy hit-a (koji je od gore 4 navedena), i 8 bita za poziciju – što sve ponovo iznosi 16 bita , tj 2 bajta.
Što se tiče anchor hit-ova, njihovih 8 bita pozicije su podeljeni na po 4 bita za poziciju u samom anchor-u i još 4 bita za heš docID-a na koji anchor pokazuje. To donekle ograničava "phrase search" – pretragu čitave fraze. Inače, relativna veličina fonta se koristi zato što kada pretražujete, ne želite da vam se identični dokumenti rangiraju različito samo zato što jedan ima veći font, ili obratno. Komplikovano, zar ne?

Stabilno, nema šta...

Kao što vidite, Google je projektovan da bude stabilna mašina za pretragu , i kao takav, ne samo što je engine kodiran dobro, nego i zapošljava mnogo tehničkog osoblja koje svojim znanjem stalno unapređuje pretragu i pruža odličnu tehničku podršku svima koji se oslanjaju na Googe sistem pretraživanja.
U sledećem broju i dalje ćemo se baviti Google pretragom i, između ostalog, videti kako se rangiraju rezultati. Do tada - googlirajte...

Verzija za štampu