News
Currently, no news are available
Statistical Data Compression
Advanced lecture with theoretical and practical exercises, V2+Ü2, for Computer Science and related programs.
| Prerequisites |
Solid foundations of mathematics and probability (MInf1 - Minf3 or equivalent); Some familiarity with algorithms (e.g. Heaps, BWT, suffix arrays, Bloom filters) is beneficial. That said, we will offer a quick refresher on relevant algorithms at the start of the semester. |
| Credits | 6 ECTS credits |
| Required time | V2+Ü2 (2 hours of lectures, 2 hours of tutorials per week) |
| Language | English |
| Final Exam | written; need to have passed midterm to take part. Course failed if failed. If passed, 70% of your grade. |
| Midterm Exam | mandatory to pass to qualify for final exam. If passed, 30% of your grade. 25 Nov 2026 14:00 - 16:00 s.t. (please arrive at least 15 minutes early). |
| Registration | Click on Registration in the menu header |
| Details | Materials will be available after registration under Information > Materials |
| Times |
Sessions: Wednesdays and Thursdays, 14:00 - 16:00 c.t., HS II E2.5. |
| Mode | Lecture in presence |
| Link | https://cms.sic.saarland/statdc26/ |
| Instructor | Kamila Szewczyk |
| Examiner | Prof. Dr. Sven Rahmann |
Please verify with your exam office if you can get ECTS credit for this course if you are not studying one of the following programs:
- Computer Science (B.Sc and M.Sc)
- Bioinformatics (M.Sc)
- Mathematics and Computer Science (M.Sc)
Content Overview
- Basic notions of information theory
- Review of string algorithms (suffix arrays, Burrows-Wheeler Transform BWT)
- Optimal prefix codes (e.g. Huffman codes)
- Optimal codes (arithmetic coding)
- Asymmetric numeral systems (rANS, tANS)
- Lempel-Ziv factoring and compression (LZ77, LZ78, LZP/ROLZ)
- LZ match finding algorithms
- Adaptive Huffman codes
- Adaptive range coding
- Introduction to Prediction by Partial Matching (PPM)
- Context-adaptive binary arithmetic coding
- Dynamic Markov coding
- Advanced techniques im PPM (information inheritance, secondary escape estimation, low order estimation)
- Advanced low-order bitwise models (indirect, finite state machines)
- Linear/logistic context mixing
- Non-linear post-mixing maps (adaptive probability maps, APM)
- Symbol ranking (SR); move-to-front (MTF), quantised local-frequency coding (QLFC)
- BWT post-coding techniques
- Parsing optimization for context mixing (PAQ9A)
- PAQ8 architecture
- Compression via large language models (LLMs)
- Neural network mixing
- Case study: DNA compression
Target audience
This course is offered as an advanced / specialized lecture at UdS.
It should be taken later in the B.Sc. program or any time in the M.Sc. program.
The material requires good mathematical knowledge (probabilities!) and low-level programming skill (you need to know your hardware).
Good programming languages to know would be C, Rust or C++, for example.