02940 Algorithms and Data Structures for Compressed Data |
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 |