582487 Data compression techniques (ohtk 25.8.2011)
Principal theme | Prerequisite knowledge | Approaches the learning objectives | Reaches the learning objectives | Deepens the learning objectives |
---|---|---|---|---|
Information theory | principles of probability theory | Can compute empirical entropies for given inputs | Understands entropy concepts and can prove for example Kraft inequality | Can apply information theory for proving lo |
Coding | bit manipulation | Can simulate coding algorithms such as (adaptive) Huffman, arithmetic coding, | Can prove properties of coding algorithms | Can develop sensible variants of coding algorithms |
Text compression | string processing methods | Can simulate couple of compression algorithms such as Lempel-Ziv, PPM, and Burrows-Wheeler transform | Can prove compression efficiencies for the algorithms | Can implement a compression algorithms that competes in time/space/compression efficiency with existing ones |
Succinct data structures | data structures | Can give a high-level explanation of some succinct data structures like rank/select, wavelet-tree, and compressed suffix array | Understands the principles of the basic succinct data structures and their connections | Can develop new succinct/compressed data structures |