Data compression [ KMI/KOM ]
In the course, after introduction to the topic, basic as well as advanced methods of lossless data compression are introduced. Methods of lossy compression of multimedia data are part of the course Multimedia systems.
Lectures
- Intro: Taxonomy of compression methods, data models (probabilistic, Markov).
- Intro: Required notions from information theory and coding (entropy, optimal prefix code)
- Intro: Basic techniques (RLE, MTF) and integer coding (Elias codes).
- Statistical methods: Shannon-Fano and Huffman coding, principles and implementation.
- Statistical methods: Arithmetic and QM coding, principles and implementation.
- Context-based methods: PPM and PAQ (context mixing) methods, principles and implementation.
- Context-based methods: Block sorting (Burrows-Wheeler transform, BWT), principles and implementation.
- Dictionary methods: LZ77 methods family and Deflate variation, principles and implementation.
- Dictionary methods: LZ78 methods family and LZW variation, principles and implementation.
- Other lossless methods: Grammar-based, statistical and other selected methods.
Literature
- Sayood K.: Introduction to Data Compression, Fifth Edition. Morgan Kaufmann, 2018. ISBN 978-0128094747.
- Salomon D., Motta G.: Handbook of Data Compression, 5th edition. Springer, 2010. ISBN 978-1848829022.
- McAnlis C., Haecky A.: Understanding Compression: Data Compression for Modern Developers. O'Reilly, 2016. ISBN 878-1491961537
- Mengyi Pu I.: Fundamental Data Compression. Butterworth-Heinemann, 2006. ISBN 978-0750663106.
- Salomon D.: Data Compression: The complete Reference, 4th edition. Springer, 2006. ISBN 978-1846286025.
- Hankerson D. C., Harris G. A., Johnson P. D.: Introduction to Information Theory and Data Compression, Second Edition (Applied Mathematics). Chapman and Hall/CRC, 2003. ISBN 978-1584883135.
- Sayood K.: Lossless compression handbook. Academic Press, 2003. ISBN 0126208611.