Hours:
20 hours (5 credits)
Room:
Aula Riunioni del Dipartimento di Ingegneria dell’Informazione, Via G. Caruso 16, Pisa - Ground Floor
To register to the course, click here
Short Abstract:
The need of storing data in compact form is increasingly important for the ever-growing rate of data produced on a daily basis. To keep up with this data explosion phenomenon, data compression is a mandatory step to deliver good quality of service in concrete applications. In this introductory course you will learn about fundamental data compression algorithms that are all widely adopted in practice by tools that we use every day, like filesystems, computer networks, search engines, databases, and so on. These algorithms have now become indispensable knowledge across many fields in computing, including Information Retrieval, Machine Learning, Natural Language Processing, Applied Physics, and Bioinformatics. To better grasp the beauty behind data compression, we will also learn how to implement some of these algorithms in C++ through several "hands-on" sessions.
Course Contents in brief:
- Introduction
- What is and Why Data Compression?
- Motivations
- Technological Limitations: Memories and Hierarchies
- Applications
- Basic Notions: Entropy, Information-Content, Data-Redundancy, Compression-Ratio
- Integer Codes
- Basic Notions: Distributions, Kraft-McMillan Inequality
- Run-Length Encoding, Gamma, Delta, Golomb, Rice, Zeta, Fibonacci, Variable-Byte
- Encoding/Decoding of Prefix-Free Codes
- Lab Session 1 on Integer Codes
- Sequence Compressors
- Basic Notions: Combinatorial Lower Bound
- Binary Packing, Simple, PForDelta, Elias-Fano, Interpolative, Directly-Addressable, Hybrid
- Inverted Indexes and Social Networks
- Lab Session 2 on Sequence Compressors
- Statistical Compressors
- Shannon-Fano, Huffman, Arithmetic Coding, Asymmetric Numeral Systems
- Dictionary-Based Compressors
- LZ77, LZ78, LZW, variants: gzip, LZO, Zstd
Schedule:
11-15 April 2022, 14:00 - 18:00
