Priču o web pretraživačima nastavljamo drugim korakom indeksiranjem.Indeksiranje predstavlja proces parsiranja, skladištenja i indeksiranja podataka u cilju brzog i tačnog pronalaženja Bez indeksiranja web pretraživač bi morao da prolazi kroz svaki pojedinačan dokument u skladištu što bi zahtevalo mnogo vremena i računarske snage. Dok se indeksiranih 1000 dokumenata može pretražiti u milisekundi dotle pretraga ne obrađenih 1000 dokumenta može trajati satima a toliko vremena ni jedan korisnik pretraživača nije spreman da čeka.

Arhitektura Google sistema

Proces indeksiranja započinje prosleđivanjem dokumenta preuzetog od strane spajdera serveru baze podataka. Server baze kompresuje i snima celokupni dokument u bazu dodeljujući mu pri tome jedinstveni identifikator DocID. Proces indeksiranja se dalje nastavlja parsiranjem svakog dokumenta i izdvajanjem svih reči i njihovog broja pojavljivanja na posmatranom dokumentu.

Sve reči koje se nađu u dokumentu proveravaju se sadržajem tabele Lexicon. Ukoliko reč ne postoji ona se ubacuje i dodeljuje joj se novi Id. Tabela Lexicon je veoma bitna jer kada korisnik unese reč u polje za pretragu, najpre se proverava da li unesena reč postoji u tabeli. Ukoliko upit pokaže da reč ne postoji u Lexicon-u korisniku se automatski vraća rezultat upita da ne postoji ni jedan dokument sa njom.

Sva pojavljivanja reči se potom sortiraju forward indeks algoritmom i smeštaju u novu tabelu (na slici Barrel). Indekser pored toga izvršava još jedan bitan zadatak: parsira sve linkove koji se nalaze na strani i smešta ih u posebnu tabelu, gde se ponovo vrši sortiranje ovog puta inverted index algoritmom. U nastavku teksta biće detaljnije objašnjeni procesi parsiranja i sortiranja elemenata dokumenta.

Parsiranje dokumenta

Parsiranje predstavlja proces deljenja dokumenta na komponente (reči). Ovaj proces se još naziva tokenizam jer svaka pojedinačna reč predstavlja poseban token.

Parsiranje je veoma bitan proces jer za razliku od ljudi koji bez problema mogu identifikovati reči u rečenici, za računare to je samo niz bajtova. Računari ne znaju da karakter blanko u sekvenci deli dve reči u dokumentu. Zbog toga se prave specijalni programi (parseri ili lexeri) koji omogućavaju deljenje dokumenta na pojedinačne reči.

Tokom parsiranja zadatak parsera je da identifikuje sekvence karaktera koje predstavljaju reči. Pored reči parser prepoznaje pravopisne znakove, nizeve brojeva, binarne znakove, prazna mesta ali i entitete kao što su email adrese, telefonske brojeve ili URL adrese. Parseri boljih web pretraživača pored samih tokena pamte i da li su oni bili posebno naglašeni (italic, bold) ili su se nalazili u specijalnim regionima stranice (naslov stranice, u okviru <H1>,<H2> ili <H3> taga…).

Iz svakog dokumenta koji se parsira izbacuju se one reči koje se nalaza na takozvanoj stop listi. Stop lista predstavlja reči koje web pretraživač ignoriše prilikom pretrage. To su one reči koje se prečesto pojavljuju na dokumentima kao što su (za englesko govorno područje)
•    The
•    It
•    She
•    And
•    Or
Ove reči web pretraživač ignoriše jer ukoliko bi one bile sastavni deo upita znatno bi se povećao broj rezultata upita, a kvalitet bi opao.

Svaka reč koja se pronađe prilikom parsiranja ubacuje se u token niz zajedno sa pozicijom reči u dokumentu. Primer token niza (struktura slična listi) za primer “It’s a dog eat dog world”.

Token lista

Svaki čitalac koji imalo poznaje bazu podataka i pojam normalizacije primetiće da je ovakav način čuvanja podataka redundantan jer se reč dog ponavlja 2 puta. Da bi se otarasili ove redundantnosti web pretraživači u bazi podataka koriste tabelu Lexicon, gde je svaka reč predstavljena jedinstvenim ključem.

Primer Lexicon tabele

Pronalaženjem ključa za svaku reč u tabli Lexicon i pozicije ključa u dokumentu nastaje hash tabela  koja se dalje prosleđuje na sledeći korak u procesu: sortiranje.

Hash tabela

Sortiranje

Sorter je veoma bitan element web pretraživača koji hash listu sa svim rečima i njihovim pozicijama na dokumentu provlači kroz dva različita algoritma sortiranja. Kao finalni rezultat ovog procesa jeste snimljena lista svih reči u bazi pretraživača maksimalno prilagođena brzom pronalaženju svih dokumenata koji imaju traženu reč.

Forward index struktura

Forward index struktura

Forward index algoritam transformiše hash listu u tabelu  koja za svaki dokument pamti koliko se koja reč puta pojavila na njemu (Eng. Number of hits). Za neke web pretraživače ovakva struktura je završni proces indeksiranja dokumenta. Međutim, cilj web pretraživača jeste da optimizuju brzinu dobijanja rezultata za upit: nađi sve dokumente na kojim se pojavljuje reč X. Ukoliko se takav upit izvršava na strukturi dobijenoj primenom forward index algoritma vreme potrebno za dobijanje rezultata biće dugo jer upit mora da sekvencijalno prođe kroz svaki red tabele i da proveri da li trenutni dokument sadrži traženu reč.

Inverted Index struktura

Inverted Index struktura

Inverted index  dalje transformiše podatke dobijene forward index-om da bi ih dodatno optimizovao za pretragu. Umesto liste svih reči po dokumentu, dobija se lista svih dokumenata koje sadrže posmatranu reč . Tako dobijena struktura je u potpunosti prilagođena upitu: pronađi sve dokumente koje sadrže reč X i predstavlja finalni produkt indeksiranja