Data Compression
Semestr: Summer
Range: 2+2s
Completion:
Credits: 4
Programme type: Undefined
Study form:
Course language: English
Summary:
The course deals with the basic techniques for text compression - lossless compression. After an introduction with theoretical background we proceed with integer encoding, which is used in other compression methods. The main topics of the course are then statistical, dictionary and context compression methods.
Keywords:
Course syllabus:
1. Introduction, entropy, models, basic methods.
2. Integer encoding, Fibonnaci codes, Elias codes.
3. Integer encoding, Elias codes, Golomb codes.
4. Statistical methods, Shannon-Fano coding, Huffman coding.
5. Statistical methods, Arithmetic coding.
6. Dictionary methods, LZ77.
7. Dictionary methods, LZ78.
8. Dictionary methods, LZW.
9. Context methods, PPM.
10. Context methods, DCA.
11. Context methods, ACB.
12. Searching in compressed text.
13. Burrows-Wheeler transformation.
14. Word based compression.
Seminar syllabus:
1. Introduction, entropy, models, basic methods.
2. Integer encoding, Fibonnaci codes, Elias codes.
3. Integer encoding, Elias codes, Golomb codes.
4. Statistical methods, Shannon-Fano coding, Huffman coding.
5. Statistical methods, Arithmetic coding.
6. Dictionary methods, LZ77.
7. Dictionary methods, LZ78.
8. Dictionary methods, LZW.
9. Context methods, PPM.
10. Context methods, DCA.
11. Context methods, ACB.
12. Searching in compressed text.
13. Burrows-Wheeler transformation.
14. Word based compression.
Literature:
1. Melichar, B.: Textové informační systémy. Praha, Vydavatelství ČVUT,
1997. 2. Salomon, D.: Data Compression. Springer, 2004