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