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

 

28.08.2011 - 18:27 Jyrki Kivinen
 25.02.2011 - 16:16 Veli Mäkinen
http://www-edit.cs.helsinki.fi/en/node/61652
Printer-friendly versionPrinter-friendly version