History of Lossless Data Compression Algorithms: Difference between revisions
Rihamichael (talk | contribs) No edit summary |
Rihamichael (talk | contribs) No edit summary |
||
| Line 1: | Line 1: | ||
== Overview == | == Overview == | ||
I'm a student at San Jose State University doing a semester project on the history of lossless data compression algorithms. 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. | 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 [http://www.cs.sjsu.edu/~mak/CS185C/ 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.<br> | ||
<br> | |||
== Questions I plan to answer<br> == | |||
How have compression algorithms evolved over time?<br>What methods do they use to compress and how are they interrelated?<br>What real-world applications do they have, and how have they changed?<br>What priority do they place on speed vs. compression ratio?<br>What effect have software patents had on the development of compression algorithms?<br> | |||
== Planned Algorithms to Cover == | |||
LZ77 (Lempel-Ziv #1) 1977<br>--LZSS (Lempel-Ziv-Storer-Szymanski) 1982<br>--LZRW (Lempel-Ziv Ross Williams) 1991 <br>--LZJB (Lempel-Ziv Jeff Bonwick) 1998<br>--LZR (Lempel-Ziv-Renau) ???<br>----DEFLATE (ZIP, PNG, gzip, etc.) 1993<br>---------DEFLATE64 (Proprietary) 1999<br>--LZS (Lempel-Ziv-Stac) 1994<br>--LZX (Used in Microsoft .CAB) 1995<br>--LZP (Usually a preprocessor) 1995<br>--LZO (Lempel-Ziv-Oberhumer) 1996<br>--LZMA (Lempel-Ziv-Markov Chain) 1998<br> | |||
<br> | |||
LZ78 (Lempel-Ziv #2) 1978<br>--LZW (Lempel-Ziv-Welch) 1984<br>-----LZMW (Syllable-based LZW) 1985<br>-----LZAP 1988<br>-----LZWL 2006<br> | |||
<br>bzip2 (Algorithm Amalgam) 1996<br> | |||
<br>PAQ* (Context Mixing) 2002<br>---PAQ8O (Faster, higher CR) 2007<br>---Many others<br> | |||
<br>Statistical LZ<br>ROLZ (Reduced Offset LZ)<br><br> | |||
== Methods used in these algorithms<br> == | |||
Dictionary Compression (ubiquitous)<br>Prediction by Partial Matching (PPM, used by 7-Zip and RAR)<br>Context Mixing (Combines multiple statistical models)<br>Entropy Encoding<br>--Huffman Coding (Used in DEFLATE, bzip2, SSH, etc.)<br>-----Adaptive Huffman Coding (Dynamic scope)<br>-----Shannon-Fano Coding (Suboptimal compared to Huffman)<br>--Arithmetic & Range Encoding<br>--Rice & Golomb Coding (FLAC uses Rice, not used general purpose)<br>--Universal Coding (Slower than Huffman, uncommon)<br>Run-Length Encoding (AAAAAAABBBBA => 7A4BA)<br>Burrows-Wheeler Transform (Preprocessor for Run-length Encoding)<br><br> | |||
[[Category:Data_compression]] | [[Category:Data_compression]] | ||
Revision as of 22:12, 26 October 2011
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)
