Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica, Universita' di Pisa
 

Aula C2

 Abstract:

Vi è un interesse sempre maggiore nello sviluppo di strutture dati e algoritmi efficienti per problemi di ricerca su grandi collezioni testuali. Il termine "efficiente" si riferisce non soltanto ai tempi di risposta alle query poste dall'utente, ma anche allo spazio occupato dalle strutture dati utilizzate. Il motivo va ricercato nella crescita esponenziale dei dati reperibili in forma elettronica, che sorpassa la pur non indifferente crescita della capacità di memoria (centrale e di massa) dei computer attuali. La compressione può giocare un ruolo importante in questo contesto avendo benefici effetti collaterali non limitati al risparmio in spazio: anche il tempo di accesso alle strutture dati può essere ridotto in quanto minore è la quantità di dati da trasferire o minore è lo spazio su disco da percorrere. Per questo motivo, gli approcci che tendono a combinare indicizzazione e compressione stanno ricevendo attualmente sempre più attenzione. Comunque i risultati noti in letteratura sono basati essenzialmente su euristiche che ottengono trade-off sperimentali tra occupazione in spazio ed efficienza della ricerca (vedere ad es. il tool Glimpse). In questo talk descriveremo una nuova struttura dati che trae vantaggio dalla comprimibilità dei testi per ridurre lo spazio occupato, senza però pregiudicare in alcun modo l'efficienza delle ricerche eseguibili su di essa. Più precisamente lo spazio totale è funzione lineare dell'entropia della collezione di testi indicizzata, e quindi risulta ottimo nel senso della teoria dell'informazione; inoltre, la complessit$agrave in tempo della query è del tutto paragonabile a quella ottenuta dai migliori indici full-text (non compressi) sia per quanto concerne il conteggio delle occorrenze che il recupero delle stesse, se siamo in presenza di query selettive. Alla fine del talk discuteremo inoltre una possibile implementazione di questa struttura dati confrontandola con strumenti di compressione e ricerca noti: quali Zgrep, Bgrep, Suffix Array, etc.. (in collaborazione con G. Manzini)