Contents

1 Basics

• gzip (GNU zip) is a open-source text compressor, written by Mark Adler and Jean-loup Gailly.
• Implements DEFLATE algorithm [1, 2] created by Phil Katz.

2 DEFLATE

1. Divide the input into blocks.
2. LZ77 encode each block.
3. Compute a Huffman tree for the offsets.
4. Huffman encode the Huffman tree using a static probabilistic model.
5. Huffman encode each block using an adaptive probabilistic model.

2.1 Lab: GZIP

IPython notebook

References