AUTONOMOUS, DISTRIBUTED AND PERVASIVE SYSTEMS-2

La necessità di archiviare i dati in forma compressa sta diventando sempre più importante a causa della quantità sempre crescente di dati prodotti. Per poter archiviare ed indicizzare i dati in maniera efficiente, la compressione dei dati è una scelta di design obbligatoria per fornire una buona qualità del servizio nelle applicazioni concrete.

Questo corso presenta alcuni degli algoritmi fondamentali di compressione dei dati -- tutti ampiamente adottati da strumenti che utilizziamo ogni giorno, come file systems, reti di computer, motori di ricerca, e basi dati. Questi algoritmi sono ormai diventati conoscenza indispensabile in molti campi dell’informatica, tra cui Information Retrieval, l’apprendimento automatico, l’elaborazione del linguaggio naturale, la fisica applicata, e la bioinformatica.

Alla fine del corso, lo studente sarà in grado di:
- comprendere ad analizzare i principali algoritmi di compressione lossless per interi e sequenze di interi.
- saper scegliere consapevolmente una buona tecnica di compressione per la specifica applicazione pratica.

Conoscenze base di notazione O-grande, architettura dei calcolatori, e teoria delle probabilità.

1. Introduzione
- Cos'è e perché la compressione dei dati?
- Modello Base e Limiti
- Compromessi tra spazio e tempo
- Domande fondamentali, indecidibilità
- Dati, Informazione, Ridondanza, Limitazioni Tecnologiche

2. Il problema della codifica statica di numeri interi
- Decodificabilità unica
- Codice Unario, Binario, Binario Minimo, Gamma, Delta, Golomb, Rice, Golomb Esponenziale, Fibonacci, Variable-Byte
- Efficacia
- Contenuto informativo, entropia, distribuzioni
- Codici di ridondanza minima, disuguaglianza di Kraft-McMillan

3. Elenco compressori
- Il problema della codifica di liste ordinate
- Limite inferiore
- Approcci "a blocchi", PForDelta, "Simple", Elias-Fano, Elias-Fano partizionato, Rank & Select su vettori binari, codice interpolante, codice ad indirizzamento direttamente, metodi ibridi

4. Compressori statistici
- Il problema della codifica statistica e di ridondanza minima
- Assegnazione di codici canonici prefix-free
- Shannon-Fano
- Huffman, Huffman canonico
- Codifica aritmetica
- Sistemi numerici asimmetrici

5. Compressori basati su dizionario
- Il problema della codifica basata su dizionario
-LZ77, LZSS, gzip, LZ78, LZW
- Varianti, panoramica dei compressori

- Robert Sedgewick and Kevin Wayne. 2011. Algorithms. Four-th edition. Addison-Wesley Professional, ISBN 0-321-57351-X.
- David Salomon. 2007. Variable-Length Codes for Data Compression. Springer Science & Business Media, ISBN 978-1-84628-959-0.
- Alistair Moffat and Andrew Turpin. 2002. Compression and Coding Algorithms. Springer Science & Business Media, ISBN 978-1-4615-0935-6.
- Gonzalo Navarro. 2016. Compact Data Structures. Cambridge University Press, ISBN 978-1-107-15238-0.
- Articoli di ricerca indicati nel materiale didattico

A scelta tra le seguenti opzioni:
1. Implementazione (corretta!) di un algoritmo di compressione dei dati e discussione.
2. Studio un articolo di ricerca e discussione.
3. Contribuzione al corso: preparazione di alcune slides su un nuovo argomento. (L'insegnante ti darà un elenco di argomenti.)
4. Studio di un problema di ricerca (può portare a una pubblicazione con l'insegnante).

orale

Didattica frontale, slides, lavagna per dimostrazioni non presenti nelle slide.