Data Compression

Lecturer:

Jan Holub, Neurčen (gar.)

Tutor:

Jan Holub, Neurčen (gar.)

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:

http://service.felk.cvut.cz/courses/XD36KOD/

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:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans:

• Computer Technology - System Programming- structured studies (compulsory course of the branch)