Lossless Data Compression, Fall 2005

Lecturer

Peter Bro Miltersen.

Programmer

Troels Bjerre Sørensen

Actual Handout

Bell, Witten, Cleary. Modelling for Text Compression.

Virtual Handout

Peter Bro Miltersen, Course Notes for Data Compression, 1, 2.

John Kieffer, Lectures on Source Coding, Chapter 1, 2, 3, 4, 5, 6. 7.

Susanne Albers, Competetive Online Algorithms

Burrows and Wheeler, A Block-Sorting lossless Data Compression Algorithm

Vereshchagin and Vitanyi, Kolmogorov's structure functions and model selection.

Time and Place

Shannon-157, Mondays, 13.15-15 and Codd-121, Thursdays, 14.15-16 during first quarter.

Structure of course

The first two weeks will be lectures, covering the basic theory. On September 12th, the java framework developed for the course will be presented. To pass the course, you must do a project using this framework. The final report on the project must be handed in at the end of the quarter. The project may be done in groups with up to three students. Please form such groups duing the two first weeks of the quarter and tell me which groups have been formed on September 12th. On October 24-26th, twenty-minute individual oral exams on the project and the course will be held. You'll get a grade on the 13-scale, based on the project report and the exam. A daimi newsgroup: daimi.ldc has been set up for discussions related to the course and the second quarter course "Lossy Data Compression".

groups

Exam plan

Exam curricculum ("Pensum"): Miltersen 1 and 2. Kieffer 7. Albers, pages 18-20, 31-35. Bell, Cleary, Witten, pages 558-568, 576-581. Burrows and Wheeler. Background reading ("Kursorisk pensum"): Kieffer 1-6, Vereschagin and Vitanyi.

Java framework

To install the java framework for the course on a linux machine, go to a designated directory and run

svn co --username anon --password anon http://svn.daimi.au.dk/svn/trold/Prog/Java/ldc

This should give you a subdirectory named ldc, containing several files with java source code. To compile them, run

javac `find ldc -name "*.java"`

and to generate javadoc, run

javadoc ldc

To get started, look at the javadoc for the command line tool Compressor.

Lectures given

August 29th: Introduction to the course. The basic lossless source coding task. Prefix codes. Kraft-McMillan inequality. Entropy. Powerpoint. Slides as pdf. Kieffer 1, page 1-3, Miltersen 1, Section 1 and 2.

September 1st Shannon's theorem. Huffman codes. Kieffer 2,3 (background reading). Miltersen, Section 3.

September 5nd: Prediction models (0th order kth order models, Finite state models, Hidden Markov models, Linear models). Huffman coding prediction models. Memory-less codes. Powerpoint. Slides as pdf. Miltersen, Section 4, 5, 8. Kieffer 4 (background reading).

September 8th: Arithmetic coding. Powerpoint. Slides as pdf.. Miltersen, Section 6, 9,Kieffer 6.

September 12th: Final words on arithmetic coding. Presentation of the ldc object oriented java framework for data compression. Presentation of project.

September 15th: Adaptive models. Hierarchial models. PPM. Miltersen, Section 7. Bell, Cleary, Witten, 558-568.

September 19th: Run-length transform. Kieffer 7. Move to front transform. Albers, 18-20, 31-15. Lempel-Ziv 78 Kieffer 5. Lempel-Ziv 77. Bell, Witten, Cleary, 576-581.

September 22th. Discussion of progress on project.

September 26th LZ78. The Burrows-Wheeler transform. Pointwise redundancy analysis of Burrows-Wheeler. Burrows and Wheeler.

September 29th The Kolmogorov code and Kolmogorov complexity. Miltersen 2

October 3nd Discussion of progress on project.

October 6th The Kolmogorov structure function. Miltersen 2, Vereshchagin and Vitanyi (background reading).

Lectures planned

October 10th Discussion of progress on project.

October 13th Universal portfolio selection and compression.

October 14th End of Quarter. Hand in project report. Project exam dates: 24/10, 25/10/, 26/10.