| | | corso | | | | |
Algoritmi per internet e web: indicizzazione di testi
Codice: | AA490 | Crediti: | 6 | Semestre: | 1 | Sigla: | IND | |
|
Settore disciplinare: | INF/01 - Informatica |
Docente
Roberto Grossi
Tel. 0502212793Programma
- 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.
Bibliografia
- [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).