Skip to the content.

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. Rank/Select operations on bitvectors (4/12).
  6. Practical bitvector implementations. Compressed bitvectors (RRR representation). Finding the position of the occurrences in a BWT index: uniform sampling and the r-index (6/12).
  7. Locate in the r-index (end). Subpath queries in Graph: conditional lower bound. (13/12).
  8. Wheeler Graphs.(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 prepare a joint presentation. Regardless of the topic, each student should give 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:

All papers should accessible using the department account: contact me if you have any problem.