corso

Algoritmi per internet e web: indicizzazione di testi

Roberto Grossi

Tel. 0502212793

Ultima versione disponibile: programma da confermare per l’a.a. 2007/2008

Introduzione al corso. Anatomia di un motore di ricerca e tecniche di indicizzazione.
Indici "word-based" di motori di ricerca: Liste invertite e algoritmi di interrogazione.
Pattern matching esatto: automi, Knuth-Morris-Pratt, Boyer-Moore-Horspool, Aho-Corasick.
Pattern matching con espressioni regolari: automi non-deterministici e scansione del testo.
Pattern matching approssimato: distanze di Hamming e di edit, tabella di programmazione dinamica.
Algoritmi di ricerca testuale con paradigma shift-and (agrep).
Indici "full-text": trie, ternary search tree, suffix tree e suffix array.
Tecniche algoritmiche per Web Spidering e classificazione di pagine Web mediante PageRank e HITS.

[Gr02b] R. Grossi, Dispense del corso (in parte), file Postscript compresso con gzip, 2002.
[GI98] R. Grossi, G. F. Italiano, Rassegna su suffix tree (in parte), file PDF, 1998.
[Gu02] A. Gullì. Web crawling e ranking. Lucidi powerpoint (2004), rassegna PDF(2002).
[Gu97] D. Gusfield, Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Capitoli 5 e 7 (suffix tree e suffix array), Cambridge University Press, 1997.

Altro materiale reso disponibile durante il corso (contattare il docente).