Data Compression (CTU14)

ATHENS Course

(Advanced Technology Higher Education Network, Socrates)

Key words: Data compression, entropy, coding of integers, statistical methods, dictionary methods, context methods
Language: English
Professor Responsible: Jan Holub
Phone: (+420) 224 359 814, (+420) 224 359 876, E-mail: Jan.Holub@fit.cvut.cz
Address where the course is to be held:
Department of Theoretical Computer Science
Faculty of Information Technology
Czech Technical University in Prague
Thákurova 2700/9, 160 00 Prague 6, Czech Republic (map)
Total number of places: 15, minimum 10
Course description as PDF

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, ACB
  5. DCA (Antidictionaries), 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.
Created by: Jan Holub
Last updated: October 6, 2012

Valid HTML 4.01!