Data Compression
| Code | Completion | Credits | Range |
|---|---|---|---|
| X36KOD | Z,ZK | 4 | 2+2s |
- The course is a substitute for:
- Data Compression (36KOD)
- Lecturer:
- Jan Holub, Neurčen (gar.), Jakub Jaroš
- Tutor:
- Jan Holub, Neurčen (gar.), Jan Baier, Jakub Jaroš
- Supervisor:
- Department of Computer Science and Engineering
- Synopsis:
-
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.
- Requirements:
- Syllabus of lectures:
-
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.
- Syllabus of tutorials:
-
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.
- Study Objective:
- Study materials:
-
Melichar, B.: Textové informační systémy. Praha, Vydavatelství ČVUT, 1997.
Salomon, D.: Data Compression. Springer, 2004
- Note:
- Time-table for winter semester 2011/2012:
- Time-table is not available yet
- Time-table for summer semester 2011/2012:
-
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon Tue Fri Thu Fri - The course is a part of the following study plans:
-
- Computer Technology - Software Engineering- structured studies (compulsory elective course, compulsory elective course, S1 recommendation)
- Computer Technology - System Programming- structured studies (compulsory course of the branch)
- Computer Technology - Computer Graphics- structured studies (compulsory elective course, compulsory elective course, S1 recommendation)
- Computer Technology - Computer Network and Internet- structured studies (compulsory elective course, compulsory elective course, S4 recommendation)
- Computer Technology - Designing Digital Systems- structured studies (compulsory elective course)