Algorithms in the Real World (Guy Blelloch) 29 Aug 97 Lecture #2 (Compression) Notes by Ben Zhao

• Information Theory

• Lossless Compression 1. Huffman Coding

2. Shannon-Fano Coding

3. Arithmetic Coding

4. PPM (prediction by partial matching)

5. LZ78 and LZW (GIF, UNIX Compress...)

6. LZ77 (gzip, ZIP, ...)

1 Information Theory

......

Entropy Examples:

1.1 The English Language

2 Basic Compression Algorithms

2.1 Prefix Codes 2.2 Huffman Codes 2.3 Shannon-Fano Coding 2.4 Arithmetic Coding 2.5 Deriving Probabilities

PPM: Prediction by partial matching

3 Lempel-Ziv Overview

3.1 LZ78 and LZW

Encode: Decode: Properties:

3.2 LZ77 (Sliding Windows)