77
La fase successiva al parsing è l’indexing. In questa fase i docu-
menti processati dal parser di Google vengono codificati in una serie
di indici (barrel): ad ogni URL viene associato un docID mediante
una funzione checksum, e le corrispondenze fra URL e docID vengo-
no registrate in un file apposito; allo stesso modo, ogni parola viene
convertita in un identificatore univoco (wordID) utilizzando un dizio-
nario (hash table) chiamato lexicon, “lessico”. Una volta che le parole
sono state convertite in wordID, le loro occorrenze nel documento
corrente vengono tradotte in elenchi di corrispondenze (hit list) e me-
morizzate nei barrel, ciascuno dei quali contiene un certo range di
wordID ed è ordinato per docID. Poiché questa fase del processo di
indicizzazione è svolta in parallelo da più server che condividono lo
stesso lexicon, al fine di evitare potenziali rallentamenti Brin e Page
hanno scelto di utilizzare un log dove registrare temporaneamente le
nuove parole non ancora incluse nel lexicon (le cui dimensioni sono
state fissate a 14 milioni di parole): questo permette di inserire le new
entry nel lexicon solo in un secondo momento, alla fine della fase di
indexing principale. Brin e Page sono intervenuti con ulteriori ottimiz-
zazioni, volte a ridurre il più possibile i tempi di accesso all’indice.
Tra queste, la creazione di un file (contenente le checksum degli URL
associate ai corrispondenti docID, e ordinato per checksum) usato per
convertire velocemente gli URL in docID per mezzo una semplice
funzione di ricerca binaria per checksum (che per definizione è calco-
labile a partire dall’URL): questo accorgimento permette di convertire
gli URL in docID in modalità batch facendo un merge con il file ap-
pena descritto, limitando così al minimo indispensabile gli accessi al
disco; altre tecniche di ottimizzazione vanno dalla creazione di struttu-
re dati ad hoc, progettate in modo da sfruttare ogni singolo bit a dispo-
sizione, fino all’utilizzo di un formato di compressione proprietario,
alternativo alla codifica di Huffman, appositamente studiato per la co-
difica delle hit list contenute nei barrel allo scopo di ridurre il più pos-
sibile lo spazio occupato dagli indici.
 |
 |
 |