Algoritmi per Internet e web: compressione di testi

Paolo Ferragina      Tel. 0502212764

Nozioni di base di teoria della probabilità, aver seguito il corso di Algoritmica.

Esporre le basi teoriche, gli algoritmi e le strutture dati su cui si fonda il progetto dei moderni metodi per la compressione dei dati testuali.

Il corso affronterà i seguenti temi: compressori statistici (Huffman e Arithmetic), compressori gerarchici (PPM), compressori basati su dizionario (Lempel-Ziv-like) e su ordinamento di suffissi (Burrows-Wheeler). Si discuteranno inoltre metodi per la compressione di sequenze di numeri interi e si esaminerà la loro applicazione ai motori di ricerca: quali Altavista e Google. Verranno infine presentati alcuni algoritmi per la ricerca di pattern all'interno di file compressi.

We deal with the following topics: statistical compressors (Huffman and Arithmetic), hierarchical compressors (PPM), dictionary-based compressors (Lempel-Ziv-like) and block-sorting compressors (Burrows-Wheeler). We also present algorithms to effectively compress sequences of integers and address the use of all this machinery to implement Web search-engine: like Altavista and Google. Finally, we will describe some of the most recent advances in the string-matching field about the design of algorithms for searching patterns into compressed texts.

1. Entropia: definizione e Teorema della codifica in assenza di rumore
2. Compressione di sequenze di interi
3. Run-length encoding and MTF-coding
4. Algoritmo di Huffman e Aritmetico
5. Famiglia degli algoritmi di Lempel-Ziv: compress e gzip
6. Burrows-Wheeler: bzip2
7. Algoritmi di ricerca su file compressi
8. Strutture dati per l'indicizzazione di file compressi
9. Compressione e motori di ricerca: Altavista e Google

1. I. H. Witten e A. Moffat e T. C. Bell, Managing Gigabytes, Morgan Kaufmann, 1999. 2. Materiale distribuito a lezione.

Scritto e orale