| | | corso | | | | |
Algoritmi per Internet e web: compressione di testi
Codice: | AA047 | Crediti: | 3 | Semestre: | 1 | Sigla: | AIW | |
|
Settore disciplinare: | INF/01 - Informatica |
Docente
Paolo Ferragina
Tel. 0502212764Prerequisiti
Nozioni di base di teoria della probabilità, aver seguito
il corso di Algoritmica.
Obiettivi di apprendimento
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.
Descrizione
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.
English Description
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.
Programma
- Entropia: definizione e Teorema della codifica in assenza di rumore
- Compressione di sequenze di interi
- Run-length encoding and MTF-coding
- Algoritmo di Huffman e Aritmetico
- Famiglia degli algoritmi di Lempel-Ziv: compress e gzip
- Burrows-Wheeler: bzip2
- Algoritmi di ricerca su file compressi
- Strutture dati per l'indicizzazione di file compressi
- Compressione e motori di ricerca: Altavista e Google
Bibliografia
1. I. H. Witten e A. Moffat e T. C. Bell, Managing Gigabytes, Morgan
Kaufmann, 1999.
2. Materiale distribuito a lezione.
Modalità di esame
Scritto e orale