Course code CTU14
Course title Data Compression
Institution Czech Technical University in Prague
Course address Faculty of Information Technology, Department of Theoretical Computer Science, CTU in Prague, Thakurova 9, 160 00 Prague 6, Czech Republic
City Prague
Minimum year of study 4th year
Minimum level of English Good
Minimum level of French None
Key words Data compression, entropy, coding of integers, statistical methods, dictionary methods, context methods
Language English
Professor responsible Jan Holub
Telephone 420 224 359 814
Fax 420 224 359 819
Email jan.holub@fit.cvut.cz
Participating professors
Number of places Minimum: 10, Maximum: 15, Reserved for local students: 0
Objectives Modern technologies require processing of larger and larger amount of data while on the other hand smaller and smaller devices appear. These two contradictory requirements lead to increasing importance of data compression.
The course presents principles of data compression. The basic data compression methods are presented followed by most popular and frequently used compression algorithms. Students will learn properties of various data compression methods which is very important when designing new information and communication systems.
Programme to be followed Five 3-hour lectures:
1. Introduction, entropy, basic methods, coding of integers, Elias codes, Fibonnaci codes
2. Statistical methods, Shannon-Fano, Huffman, and arithmetic coding
3. Dictionary methods, LZ77, LZ78, LZW
4. Context methods, PPM, DCA (Antidictionaries), ACB
5. Burrow-Wheeler transformation, searching in compressed text, word-based compression
Four 3-hour seminars with demonstrations:
1. Entropy, basic methods, coding integers, Elias codes, Fibonnaci codes
2. Statistical methods, Shannon-Fano, Huffman, and arithmetic coding
3. Dictionary methods, LZ77, LZ78, LZW
4. Context methods, PPM, DCA (Antidictionaries), ACB, Burrow-Wheeler transformation, test
Prerequisites Sets, relations, oriented graphs, finite automata.
Course exam Written exam with the duration of 1 hour. Evaluation of the results.
Back