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.
|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.|
|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|