Compression and Coding Algorithms

1 Data Compression Systems.- 1.1 Why compression?.- 1.2 Fundamental operations.- 1.3 Terminology.- 1.4 Related material.- 1.5 Analysis of algorithms.- 2 Fundamental Limits.- 2.1 Information content.- 2.2 Kraft inequality.- 2.3 Human compression.- 2.4 Mechanical compression systems.- 3 Static Codes.- 3.1  Unary and binary codes.- 3.2 Elias codes.- 3.3  Golomb and Rice codes.- 3.4 Interpolative coding.- 3.5 Making a choice.- 4 Minimum-Redundancy Coding.- 4.1  Shannon-Fano codes.- 4.2 Huffman coding.- 4.3  Canonical codes.- 4.4 Other decoding methods.- 4.5 Implementing Huffman’s algorithm.- 4.6 Natural probability distributions.- 4.7 Artificial probability distributions.- 4.8 Doing the housekeeping chores.- 4.9 Related material.- 5 Arithmetic Coding.- 5.1  Origins of arithmetic coding.- 5.2 Overview of arithmetic coding.- 5.3 Implementation of arithmetic coding.- 5.4 Variations.- 5.5 Binary arithmetic coding.- 5.6 Approximate arithmetic coding.- 5.7 Table-driven arithmetic coding.- 5.8 Related material.- 6 Adaptive Coding.- 6.1  Static and semi-static probability estimation.- 6.2 Adaptive probability estimation.- 6.3 Coping with novel symbols.- 6.4 Adaptive Huffman coding.- 6.5 Adaptive arithmetic coding.- 6.6 Maintaining cumulative statistics.- 6.7 Recency transformations.- 6.8 Splay tree coding.- 6.9 Structured arithmetic coding.- 6.10 Pseudo-adaptive coding.- 6.11 The Q-coder.- 6.12 Making a choice.- 7 Additional Constraints.- 7.1 Length-limited coding.- 7.2 Alphabetic coding.- 7.3 Alternative channel alphabets.- 7.4 Related material.- 8 Compression Systems.- 8.1  Sliding window compression.- 8.2 Prediction by partial matching.- 8.3 Burrows-Wheeler transform.- 8.4 Other compression systems.- 8.5 Lossy modeling.- 9 What Next?.- References.