Newsgroup: it.comp.lang.c
Titolo: Indicizzazione di pagine web

Buongiorno a tutti,
devo fare un programma per un esame, e mi trovo in difficoltà.
Lo scopo del programma è quello di indicizzare il contenuto di siti web (
elencati in un file di testo ).
In particolare il programma dovrà:
 - Indicizzare un insieme di siti Web.
 - Permettere la ricerca veloce all'interno dei siti elencati per parole
chiave ( vedi motori attuali, Google e affini).
L'implementazione è libera. Io pensavo di fare 2 eseguibili: un
indicizzatore che prende in input il file di testo, scandisce le pagine web
e scrive il file di dati che verrà usato dal programmino motore di ricerca
per effettuare la ricerca.
Per quanto riguarda la parte dei socket non ho problemi.
Il problema è sulla struttura del file di dati: non ho la più pallida idea
di come realizzarlo. Se usassi una funzione hash per l'inserimento e la
ricerca di parole dovrei gestire le probabili collisioni, e soprattutto
dovrei scrivere nei byte del file che cominciano con l'offset dato dalla
funzione tutti i siti che contengono tale parola... un casino.
Mi chiedo se qualcuno possa aiutarmi indicandomi la strada da seguire.
Grazie
Alessandro

...


 per effettuare la ricerca.
Mi sembra una scelta giusta.
Ma il "programmino motore di ricerca" e' un processo server che sta sempre
attivo? Quanti dati devi indicizzare? E' plausibile tenere tutto in memoria?
Bisogna per forza fare accesso ai file? Si puo' usare la shared memory?
Ci sono diverse possibilita' (e sicuramente ce ne sono altre, tipo
appoggiarsi ad un db come mysql, etc...), che uno sceglie in base alle
proprie conoscenze.
Le prime opzioni che mi vengono in mente a livello di strutture dati sono:
(1) una cosa tipo gli indici a lista dei dbms, ovvero, x ogni parola chiave
uno si tiene la lista dei siti da essa indicizzati.
(2) una matrice a 2 dimensioni con le parole chiave su una dimensione e i
siti sull'altra; un flag in una cella della matrice indica che il sito e'
indicizzato dalla parola chiave
(3) La matrice al punto 2) potrebbe essere implementata tipo gli indici
binari dei data warehouse in cui praticamente il flag e' un bit; ad ogni
parola chiave si associa un vettore di bit (l'indice) lungo quanti sono i
siti; i siti vanno numerati progressivamente; il bit i-simo=1 significa che
la parola chiave indicizza il sito associato al numero i
Questa cosa dei binari e' utile se devi rispondere a interrogazioni con and
e or perche' trasformi gli and/or in operazioni bit a bit tra gli indici
Se puoi tenere tutto in memoria, direi che ciascuna delle soluzioni e'
valida.
Se devi salvare le strutture dati su file:
(1) Questa struttura si salva in modo naturale in un file di testo, per
righe. Ovviamente sarebbe complicato dover tenere il file ordinato in
qualche modo. Se i dati sono pochi, va bene comunque.
Altrimenti uno potrebbe pensare di salvare un file per parola chiave, e
lasciare quindi la fase di 'ricerca della chiave' al file-system...
(2) Una volta dato un ordine ai siti e alle parole chiave, nel file salvi
per riga qualcosa tipo
xxxvxvvv...
vxvxxvxv ...
dove x e v indicano se il flag e' settato o meno
(3) Analogamente al caso (2) devi salvare delle liste di bit
00010111...
10100101...
meglio sarebbe salvarli non in un file di testo (e quindi come serie di
caratteri '0' e '1'), ma in un file binario (e quindi, tanto per intenderci
in formato esadecimale:
0x17...
0xA5...
)
Spero di non aver complicato le cose.
Ciao,
Ema