Data compression and compressed data structures

Lecturer: Giovanni Manzini, Computer Science Dept. University of Pisa.

Tentative lesson plan:

  1. Statement of the lossless data compression problem. Kraft inequality. Order-0 Entropy. Optimal codes, Huffman codes and arithmetic coding (22/11).
  2. Beyond order-0 Entropy: MTF + gamma codes. Order-k entropy. PPM algorithms (24/11).
  3. LZ77 parsing: definition, bounds in terms of the order-k entropy. Introduction to the Burrows-Wheeler transform (27/11).
  4. Compression bounds for the BWT. Introduction to compressed indices (29/11).
  5. Wavelet Trees for efficient rank operations. Bitvectors supporting Rank/Select operations (4/12).
  6. From compressed bitvectors to compressed indices. Finding the position of the occurrences. Introduction to Wheeler graphs (6/12)
  7. (13/12)
  8. (15/12)

All lectures are 9am-11am in Sala Seminari EST (Room 351). There will be no streaming or recording of the lectures.

There are two possible exam formats:

  1. Students can present a problem/idea related to their research and show how it can take advantage of the techniques described in the course; this must include a working prototype of the suggested solution.

  2. Students can present a related to the course using materials provided by the instructor.

  3. All the exams should be given no later than 31/5/2024.

Study material

Possible exam material

Some topics can be studied by two people that will later do a joint presentation. Regardless of the topic, each student should do a 30 minute presentation describing: 1) the problem, 2) the previous state of the art, 3) the content of the new contribution. Tentative list of topics (paper links will be added soon):