The need for storing data in compressed form is becoming more and more important due to the ever-growing rate of data produced on a daily basis. To keep up with this data deluge, 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 by tools that we use every day, like filesystems, computer networks, search engines, and databases. These algorithms have now become indispensable knowledge across many fields in computing, including Information Retrieval, Machine Learning, Natural Language Processing, Applied Physics, and Bioinformatics.
Introduction
Integer Codes
List Compressors
Statistical Compressors
Dictionary-based Compressors
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.
G. E. P. and Rossano Venturini. 2020. Techniques for Inverted Index Compression. ACM Computing Surveys. 53, 6, Article 125 (November 2021), 36 pages. https://doi.org/10.1145/3415148
Alistair Moffat. 2019. Huffman Coding. ACM Computing Surveys. 52, 4, Article 85 (July 2020), 35 pages. https://doi.org/10.1145/3342555
Giulio Ermanno Pibiri (jermp)