02940 Algorithms and Data Structures for Compressed Data

General info

Course description here. To sign up: email Patrick Hagge Cording.

We meet wednesdays from 9 to 12 in room 030, building 324.

First meeting is September 2.


Week Topic(s) Litterature
1 Entropy, prefix codes, integer codes, arithmetic codes "Introduction to Data Compression", G. E. Blelloch (chapter 2, 3, 4.0-4.2).
"Managing Gigabytes", I. A. Witten, A. Moffat, T. C. Bell (section 3.3 to and including "Nonparameterized models").
2 FM-index Indexing Compressed Text”, P. Ferragina and G. Manzini.
3 Compressed inverted indexes Quasi-Succinct Indices”, S. Vigna.
4 Rank/select and wavelet trees Compressed full-text indexes", G. Navarro and V. Makinen (Section 1, 4 and 6, with emphasis on Section 4.2 and 6-6.3)
5 Follow-up and warm-up for next week Compressed full-text indexes", G. Navarro and V. Makinen (Section 5.4 and 10.1)
6 LZ-End On compressing and indexing repetitive sequences", S. Kreft and G. Navarro (Section 1 to 4).
7 String matching in LZ-compressed text Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts", P. Bille, R. Fagerberg, and I. L. Gørtz.
8 No class
9 Grammar compression and the smallest grammar problem The Smallest Grammar Problem", M. Charikar, E. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Sahai, and A. Shelat.
10 Random access to grammar-compressed strings Random Access to Grammar-Compressed Strings and Trees", P. Bille, G. M. Landau, R. Raman, K. Sadakane, S. R. Satti, and O. Weimann (Section 1-7).
11 Compressed suffix arrays Compressed full-text indexes", G. Navarro and V. Makinen (Section 7 and 8)
12 LZ77: greedy parsing Note on the greedy parsing optimality for dictionary-based text compression", M. Crochemore et al.
13 Open problems session