History of Lossless Data Compression Algorithms

Overview

I'm a student at San Jose State University doing a semester project on the history of lossless data compression algorithms. You can see the course description here. This page will be updated as the semester progresses. I plan to include information about the evolution of Lempel-Ziv compression algorithms, as well as other alternative formats such as DEFLATE and DEFLATE64.

Questions I plan to answer

How have compression algorithms evolved over time?
What methods do they use to compress and how are they interrelated?
What real-world applications do they have, and how have they changed?
What priority do they place on speed vs. compression ratio?
What effect have software patents had on the development of compression algorithms?

Planned Algorithms to Cover

LZ77 (Lempel-Ziv #1) 1977
--LZSS (Lempel-Ziv-Storer-Szymanski) 1982
--LZRW (Lempel-Ziv Ross Williams) 1991
--LZJB (Lempel-Ziv Jeff Bonwick) 1998
--LZR (Lempel-Ziv-Renau) ???
----DEFLATE (ZIP, PNG, gzip, etc.) 1993
---------DEFLATE64 (Proprietary) 1999
--LZS (Lempel-Ziv-Stac) 1994
--LZX (Used in Microsoft .CAB) 1995
--LZP (Usually a preprocessor) 1995
--LZO (Lempel-Ziv-Oberhumer) 1996
--LZMA (Lempel-Ziv-Markov Chain) 1998

LZ78 (Lempel-Ziv #2) 1978
--LZW (Lempel-Ziv-Welch) 1984
-----LZMW (Syllable-based LZW) 1985
-----LZAP 1988
-----LZWL 2006

bzip2 (Algorithm Amalgam) 1996

PAQ* (Context Mixing) 2002
---PAQ8O (Faster, higher CR) 2007
---Many others

Statistical LZ
ROLZ (Reduced Offset LZ)

Methods used in these algorithms

Dictionary Compression (ubiquitous)
Prediction by Partial Matching (PPM, used by 7-Zip and RAR)
Context Mixing (Combines multiple statistical models)
Entropy Encoding
--Huffman Coding (Used in DEFLATE, bzip2, SSH, etc.)
-----Adaptive Huffman Coding (Dynamic scope)
-----Shannon-Fano Coding (Suboptimal compared to Huffman)
--Arithmetic & Range Encoding
--Rice & Golomb Coding (FLAC uses Rice, not used general purpose)
--Universal Coding (Slower than Huffman, uncommon)
Run-Length Encoding (AAAAAAABBBBA => 7A4BA)
Burrows-Wheeler Transform (Preprocessor for Run-length Encoding)