10) Come avviene la ricerca di informazioni sul Web?
Il web è un ipertesto (un grafo) con 300.000 nodi. Esiste quindi il problema di reperire le informazioni
Esistono indici del web, ottenuti usando dei programmi che esplorano la rete raccogliendo le informazioni in un database. Programmi più diffusi: search engine
I motori di ricerca
Struttura dati tipica: vedi figura
Due fasi: ricerca e indicizzazione
Ricerca:
Algoritmi tipo breadth-first, depth-first:
- prelevare un URL
- eseguire hash URL
se hash URL presente in Tabella hash allora STOP. Altrimenti:
- aggiungere hash URL in Tabella hash
- aggiungere Puntatori a URL e a pagina in Tabella URL
- aggiungere URL e Pagina (o titolo) in Heap
- ripetere tutti i passi per ogni link presente nella pagina
Problemi:
- dimensioni del grafo web
- punto di partenza della ricerca
- tipo di ricerca: depth-first ® stack overflow, breadth-first ® dimensioni heap
- come trattare i link presenti nelle active map (CGI)
- URL obsoleti
- macchine non raggiungibili rallentano la ricerca
Indicizzazione
la procedura di indexing estrae le parole chiave da ogni pagina (o titolo) web memorizzati nell’heap nella fase di ricerca (sintesi delle pagine). Per trovare le parole chiave:
- si scartano le parole poco significative (articoli, etc.)
- si scelgono parole che nella pagina hanno la frequenza maggiore
- per ogni parola ottenuta si memorizza in una tabella la parola e l’URL che la contiene.
- alla fine della indicizzazione si ordina la tabella sulle parole e si salva su file che verrà consultato per le ricerche da parte degli utenti
problemi:
- titoli pagine spesso poco significativi
- analisi intere pagine costosa
- pagine solo video o audio, oppure active map
Ricerche e indicizzazioni cooperative: Harvest è un motore di ricerca che richiede a tutti i server www di eseguire una applicazione per indicizzare localmente la macchina. Un motore centrale raccoglie tutti i risultati.