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

Nastavljamo seriju članaka o pretraživačima, a posebno o Google-u - kao mašini za pretragu broj jedan u ovom trenutku. U prošlim brojevima smo videli kako je zaista komplikovano projektovati dobar softver za pretragu i rangiranje rezultata, i kako je to tvorcima Google-a pošlo za rukom. Međutim, svaki koncept pretrage ima svoje slabe tačke, jer koliko god da izradite dobru tehnologiju pretrage, morate prvo podatke da dobavite u baze podataka pa tek da ih onda pretražujete, a onda prilikom njihovog prikazivanja i - rangirate. Kako to Google radi ?

Crawling / spidering – pametni pauci

Crawling je, ustvari, vrlo komplikovan deo posla, jer se komunicira sa velikim brojem web i name servera. (crawling je objašnjen u prethodnim člancima). U Google tehnologiji, jedan URL server prosleđuje listu adresa određenom broju crawler-a (najčešče 3). URL server kao i crawler-i su implementirani u Phyton tehnologiji. Svaki crawler održava 300 konekcija odjednom, radi povećanja brzine, i ako sva tri rade u isto vreme, može se posetiti preko 100 stranica u sekundi ! Ovakva brzina se postiže, pre svega, zahvaljujući DNS lookup-u. Radi se o tome da svaki crawler poseduje sopstveni DNS cache, tako da nije potrebno svaki put raditi DNS lookup za svaki dokument koji se posećuje. Inače, svaka konekcija može biti jedno od sledećih stanja crawler-a: DNS lookup, konektovanje sa hostom, slanje zahteva ili primanje odgovora. Sve ovo čini crawler kompleksnim i zato se koristi asinhroni ulaz/izlaz kao i FIFO strukture (redovi za čekanje) za promenu stanja.
Naravno, mesta za grešku uvek ima, pa je poznat slučaj kad je Google, krstareći Internetom uz pomoć svojih crawler-a pokušao da indeksira jednu on-line igricu. Ljudi koji su je tada igrali videli su gomilu poruka sa greškom. Naravno Google je posle ispravio neke bagove, ali uvek može da se pojavi nešto novo za šta je potrebno vreme da se izvrše korekcije, jer je nemoguće tako lako testirari crawler, upravo zbog ogromnog broja varijacija web servera koje on posećuje i koji mu mogu (ili on njima) zadati probleme. Mnogo bezazlenije anegdote se dešavaju zbog neznanja web dizajnera. Kažu da je vrlo čest slučaj da kad vlasnici sajtova u statistikama poseta vide da ih je Google posetio, napišu mail zahvalnosti Google-u uz pitanje: "Kako vam se svideo naš sajt?"
Ono što je vrlo bitno je da Google prilikom indeksiranja nekog sajta, indeksira samo oko prvih 100 Kb sadržaja, a meta tagove, odnosno keywords i description, uopšte ne konstatuje. Ovo je vrlo bitna činjenica koju svaki web dizajner mora imati na umu.

PageRank – svakom po zasluzi

PageRank (TM) je tehnologija kompletno razvijena od Google-a u cilju rangiranja rezultata. Da bi shvatili kako on radi, pretpostavimo da web strana A ima T1,T2,T3... do Tn stranica koje ukazuju na nju (linkovane su na nju). I neka je C(A) broj linkova koje izlaze iz strane A. Onda se PageRank strane A računa kao:
PR(A) = (1-d) + d(PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
gde je d damping fakor koji se kreće u granicama od 0 do 1, i njegova vrednost je najčešće 0,85. Primetite da je PageRank povinovan Normalnoj raspodeli (web strana), tako da suma svih PageRank-ova iznosi 1. Takođe vidimo da je izraz relativno linearan (iako rekurzivan) i može se izračunati sa jednostavnim iterativnim algoritmom, tako da se PageRank 30 miliona strana može izračunati u roku od par sati na workstation-u srednje veličine.
Šta sve ovo u praksi znači ? Pa, evo, PageRank možete zamisliti kao prosečnog korisnika interneta: data mu je slučajna stranica i on klikće na njene linkove, nikad ne kliknuvši na "back" dugme browser-a, ali eventualno se umori, pa sve počinje ispočetka ali na drugoj slučajnoj strani. Verovatnoća da slučajan posetilac poseti stranicu A je njen PageRank tj PR(A). Onda je faktor d verovatnoća da će se slučajni posetilac "umoriti" od kliktanja na toj strani i sve započeti od početka ali na drugoj slučajnoj strani.
Ako vam ni sad nije baš najjasnije probajmo ovo: ako želimo da naša stranica ima dobar PageRank onda je potrebno da veliki broj stranica ukazuju (budu linkovane) na nju, ili - da postoje 2-3 stranice koje pokazuju na nju, ali da one imaju dobar PageRank. Naravno, najbolje bi bilo da oba zahteva budu ispunjena u isto vreme.(slika 1)

Slika 1: Postizanje istog Page rank-a

Pa i intuitivno je zaista tako: ako na neku stranicu ukazuje mnoštvo linkova širom sveta, onda je ona vredna posete. Sa druge strane, dovoljno je da na neku stranicu pokazuje jedna koja ima odličan PageRank, kao npr Yahoo! – onda je takođe vredna posete. Ako je stranica lošeg kvaliteta sigurno je da je Yahoo neće postaviti link ka njoj. PageRank ovo sve uzima u obzir i iz toga izvlači zaključke o posećenosti web strana.

Link propagation

Međutim, ovaj izum ne bi bio toliko dobar, da nije izrađen u korespodenciji sa arhitekturom samog pretraživača. Odnosno, još jedna dodatna stvar ga čini odličnim, a to je način na koji se tretira tekst linkova (anchor text). Ostali pretraživači povezuju tekst linkova sa samim stranicama na kojima se ti linkovi nalaze, međutim, Google ide korak dalje – on osim toga povezuje tekst linkova sa stranicama na koje ti linkovi vode. Ovaj način tretiranja linkova naziva se "link propagation" i ima dosta prednosti. (slika 2). Na primer, sami linkovi ponekad nose više informacija o stranicama nego one same, ili, linkovi mogu da postoje za dokumente koji nisu tekstualnog karaktera (slike, programi, baze podataka). Navedeni način tretiranja tekst linkova omogućava da se u rezultatima pretrage pojave i stranice koje crawler još nije ni posetio! (a to je zato što je posetio stranice koje imaju linkove koji ukazuju na datu stranicu koja nije posećena crawler-om ali je izašla u rezultatima pretrage).

Slika 2: Značaj "link propagation" tehnologije

Sad bi svi pomislili kako to i nije baš pametno, jer stranicu koju još nije obišao crawler nije moguće proveriti u smislu validnosti, ili na primer - ta stranica možda i ne postoji više, ali link još uvek vodi ka njoj. Ali, zahvaljujući PageRank-u njena popularnost je vrlo mala, ili skoro jednaka nuli, pa prema tome, u rezultatima pretrage pojaviće se na kraju (poslednjoj stranici) ili se upošte neće pojaviti! Zar ste sumnjali u tvorce Google-a? Znači PageRank omogućava Gogle-u ne samo da rangira rezultate, već i da prikazuje strane koje nije posetio crawler.
Naravno, kao i uvek u ovako kompleksnim proračunima u "letu" potreban je dobar hardware sa odličnim procesorskim vremenom koji bi to mogao bez problema uraditi. Npr, za 2 milijarde stranice treba indeksirati preko 20 milijardi tekst linkova !

Teoretski idealno, ali u praksi ...?

Da bi bilo što jasnije gde problemi nastaju, hajde da još jednom rekapituliramo čitavu stvar. Znači, PageRank je proračun u čijim se činiocima nalaze samo brojevi strana i linkova. Sam sadržaj stranica se nigde ne pominje. Sadržaj se samo uzima u obzir kada se vrši konkretna pretraga, ali ga u samom PageRank-u nema. Pa kako možemo verovati Google-u da se samo važni i vrlo kvalitetni sajtovi rangiraju više, zahvaljujući PageRank-u ? Jer, ispada da se samo na osnovu linka sa strane A prema strani B se određuje važnost strane B. Ali, mnogo je razloga zašto bi neko linkovao stranu B sa strane A:
* vlasnik strane A želi da promoviše stranu B jer je deo njegovog sajta
* vlasnik strane A želi da promoviše stranu B jer se ona nalazi na drugom sajtu koga on takođe poseduje
* vlasnik strane B plaća za link na strani A
* vlasnici recipročno razmenjuju linkove da bi imali što bolji PageRank
* vlasnik strane A učestvuje finansijski u sajtu strane B i ima procenat od prodaje
* strana A sadrži vesti, novosti (dobre ili loše, svejedno) o sajtu strane B
Znači, link ka strani B nema puno veze sa njenim kvalitetom. Ili, još gore, tu je umešan običan komercijalni interes, tako da PageRank pomaže biznis i čini ga unosnijim. Kompanija koja se bavi prodajom na Internetu će logično imati jak PageRank, upravo zbog plaćenih reklama i linkova, tako da kompanija koja recimo, pruža informacije, ili nešto besplatno nudi, mora biti osuđen na propast zbog niskog PageRanka koji je prouzrokovan neisplatljivošću ulaganja u reklamu jer praktično i ne očekuje nikakvu dobit. I ponovo su pobednici velike korporacije i nelojalna konkurencija. Znači, malim kompanijama je vrlo teško da prikažu svoje usluge i proizvode na Internetu, a zahvaljujući Google-u i njegovom PageRanku – nikad teže.
Naravno, Google tvrdi da u pretrazi podjedanko utiču i PageRank strane i njen sadržaj, ali da li je baš tako? U realnom svetu, očigledno je da PageRank ima mnogo veći uticaj jer se upravo zahvaljujući njemu relevantni rezultati, samo po linkovima a ne po sadržaju, smeštaju među prvih 20 rezultata pretrage, a upravo je to neki maksimim do kog prosečan posetilac ide u svojoj pretrazi. Pođite od sebe, kada nešto tražite u bilo kom pretraživaču, uglavnom pregledavate do prvih pet strana pretrage, mada zbog hronične lenjosti surfera (zato je faktor d=0,85) sumnjam da taj broj prelazi 3 strane, a kako po jednoj strani ima obično 10 rezultata, to iznosi 30 rezultata po jednoj pretrazi. A možda se baš relevantni rezultat nalazi, kao 39-i, na primer. Većina posetilaca Google-ove pretrage se ne trudi to da sazna.
Sve ovo ne znači da prilikom pretrage treba preskočiti prvih 30-tak rezultata, nego jednostavno treba sve rezultate razmotriti. Očigledno je onda da takva mašina za pretagu i nije baš efektivna, jer takva pretraga oduzima mnogo vremena.
Osim toga, zahvaljujući (nepravednom) PageRank-u, često dolazi do teških grešaka u rezultatima pretrage. Naime, dešava se da se među prvih 10 rezultata nađe i neki koji po sadržaju nema ama baš nikakve veze sa traženim podacima. Ovo zapravo dokazuje da PageRank neke strane ima mnogo veći uticaj kod prikazivanja rezultata pretrage, nego njen sadržaj. Kao primer za to, kada u Google ukucate termin: free Web page, posle Yahoo-a, Tripod-a i Angelfire-a, kao četvrti rezultat dobijate Digits.com, a to je sajt koji nudi servis broja posećenosti strane (page counter service). Dobro, jedna od reči koje smo uneli je i page, ali šta se dešava ako unesemo konkretnu frazu sa znacima navoda: "free Web page" ? Rezultat je isti, iako nigde na stranici digits.com ne postoji takva sintagma! Ali ona očigledno postoji u nekom linku koji vodi do nje, što ilustruje gore pomenuti "link propagation", odnosno važnost tekstualnog dela linka. Naravno ovaj konkretan primer važi za maj 2003, jer se Google-ov index stalno menja, tako da ovo ne mora važiti u budućnosti.

Zaključak

Znači PageRank onako kako ga Google vidi ne obećava puno. Već su se pojavili radovi na Univerzitetu u Stenfordu u vezi sa uticajem sadržaja strane i linkova na PageRank i njihovoj kombinaciji, koji obećavaju puno. Dok se ova poboljšanja ne dokažu na delu, Google ima domaći zadatak: da poveća značaj pretrage po celoj frazi, da poveća značaj ključnih reči koje se nalaze u tekstu strana a da smanji značaj teksta linka, da smanji značaj PageRank-a prilikom pretrage, i na kraju, da smanji značaj sadržaja <TIITLE> taga sa kojim se očigledno može vrlo lako manipulisati.
Bilo kako bilo, Google je trenutno najbolji pretraživač, a ovo što ste upravo pročitali, bio je krtički osvrt koji treba pretragu da dovede do savršenstva.

Verzija za štampu