Algoritmi per Internet e Web
“Compressione di Testi”

A.A. 2003/2004

Informazioni generali:

· Docente: Prof. Paolo Ferragina, Dipartimento di Informatica, Pisa.

· Impegno: 20 ore, per un totale di 3 CFU.

· Orario delle lezioni: Lunedì 14-16 (B) e Mercoledì 14-16 (B), primo semestre (fino al primo compitino).

· Per esercitarsi sugli argomenti del corso è disponibile ora una pagina sul Web.

Obiettivi del corso: Studio, progetto e analisi di algoritmi per la compressione di dati testuali. Dopo una breve introduzione sui fondamenti della Teoria dell'Informazione, si descriveranno dettagliatamente svariati algoritmi: Huffman, Huffword, Aritmetico, LZ77, LZ78 e LZW (con Gzip), Move-To_front, Run-Length-Encoding, trasformata BW (con Bzip). L'obiettivo di questa carrellata e' di fornire allo studente un quadro sufficientemente esteso, ma chiaramente non esaustivo, delle tecniche e degli algoritmi oggi disponibili per la memorizzazione compressa di archivi testuali. Si investigheranno inoltre alcune tecniche per la compressione degli interi, particolarmente utili per la realizzazione efficiente dei moderni Motori di Ricerca.

Modalità di esame: scritto + prova  orale.

Durante la prova scritta gli studenti NON possono consultare i propri appunti o libri. Le date degli appelli sono consultabili via Web all'indirizzo della nostra Segreteria Didattica. Gli studenti che superano la prova scritta, nel caso vogliano incrementare il voto ottenuto devono sostenere la prova orale nello stesso appello. La data e il luogo dell'orale vengono comunicati dal docente durante la prova scritta. E' possibile tentare al massimo QUATTRO prove durante tutto l'anno accademico; si considera "un tentativo" anche il ritiro durante la prova scritta.

Testi di esame:

• 19 Dic 01,
• 23 Gen 02, 12 Feb 02, 27 Mag 02, 21 Giu 02, 12 Lug 02, 13 Sett 02, 5 Nov 02,
• 7 Gen 03, 5 Feb 03, 29 Mag 03, 20 Giu 03, 7 Lug 03, 16 Sett 03, 5 Nov 03,
• 16 Gen 04, 6 Feb 04, 1 Giu 04, 22 Giu 04, 13 Lug 04, 17 Set 04,

Libro di testo:

[MG] Managing Gigabytes. I.H. Witten e A. Moffat e T.C. Bell. Morgan Kaufmann, 1999.

Programma del corso (registro elettronico delle lezioni)

• Panoramica sugli algoritmi di compressione: storia, struttura algoritmica e  alcune curiosita'.

• T. Bell e I.H. Witten e J.G. Cleary, Modeling for text compression, ACM Comp. Surv., 21(4), 1989. (link)
• D.A. Lelewer e D.S. Hirschberg, Data Compression, ACM Computing Surveys, 1987. (link)

• Terminologia e nozioni di base: Distribuzione di probabilità, Variabili aleatorie, Media, Sorgenti ergodiche, Entropia.

• G. Gestri, Teoria dell'Informazione, ETS Editrice, 1991. cap. 1 e 2

• Teorema della codifica in assenza di rumore.

• C. E. Shannon, A Mathematical Theory of Communication, The Bell System Tech. Journal, 1948. Sezioni 2--7, appendici 2 e 3 (copia)

• Codici univocamente decifrabili e codici prefissi.

• G. Gestri, Teoria dell'Informazione, ETS Editrice, 1991. cap. 3

• Algoritmo di Shannon-Fano

• Algoritmo di Huffman: descrizione, dimostrazione di ottimalità e proprietà ([WMB]: 2.1, 2.2, 2.3, 9.1)

• Algoritmo di Huffman canonico

• Algoritmo di Huffman dinamico (appunti distribuiti dal docente)

• Arithmetic coding ([WMB]: 2.4)

• Algoritmo PPM ([WMB]: 2.5)

• Codici prefissi per numeri interi: Unary, Gamma e Delta code, Byte-aligned, Golomb code ([WMB]: 3.3)

• H. Williams e J. Zobel, Compressing integers for fast file access, The Computer Journal, 42(3), 1999. (link)

• Move-to-front coding.

• J.L. Bentley et al., A locally adaptive data compression scheme, Comm. ACM, 29(4), 1986. (link)

• Run-length encoding

• Algoritmo di Burrows-Wheeler: bzip2 ([WMB]: 2.5)

• P. Fenwick, Block Sorting Text Compression -- The final report, TR 130, April 1996. [Fe] (copia)
• M. Burrows e D.J. Wheeler, A block-sorting lossless data compression algorithm, TR Digital 124, 1994. [BW] (copia)

• Famiglia di algoritmi Lempel-Ziv: LZ77, LZ78, LZW ([WMB]: 2.6, 2.7)

• Confronto tra le prestazioni degli algoritmi descritti ([WMB]: 2.8,9.2)

Argomenti integrativi:

• Parsing ottimo per metodi basati su dizionario

• Y. Matias e C. S. Sahinalp. On the optimality of parsing in dynamic dictionary based data compression, IEEE Data Compr. Conf., 1999. (link)

• Metodi computazionalmente efficienti per estendere la finestra nei metodi LZ

• J. Bentley e D. McIlroy. Data Compression Using Long Common Strings, IEEE Data Compr. 1999. [BMc] (link)

• Compressione e motori di ricerca

• U. Manber, A Text Compression Scheme That Allows Fast Searching Directly in the Compressed File, TR University of Arizona, 1993.  (link)
• E. de Moura et al.. Fast and flexible word searching on compressed texts. ACM Trans. on Inf. Systems, 18(2): 113-139, 2000. [MNZB] (copia)
• U. Manber e S. Wu, GLIMPSE: A tool to search entire file systems, TR 93-34, Univ. Arizona, 1993. [MW] (copia)

• Compressione e Steganografia

• P. Wayner. Crittografia Invisibile: Informazioni segrete. McGraw-Hill Italia, 1997.
• Uso delle tecniche di compressione per il progetto di algoritmi di prefetching
• K. Curewitz, P. Krishnan e J.S. Vitter. Practical Prefetching via Data Compression. ACM SIGMOD, 1993. [CKV] (copia)

• Compressione e crittografia

• J.L. Massey. Some applications of source coding to cryptography. European Trans. on Communic., vol. 5, 1994. (copia)