EddyHawk's Info List
---
Compression Algorithm:
----
RLE (Run Length Encoding)
Dictionary
 LZ family
 -proposed by Abraham Lempel & Jakob Ziv
 -the coding is called LZ (Lempel Ziv)
 -invented by Jakob Ziv
 -LZ77
  proposed/invented by Jakob Ziv on 1977, thus it's called LZ77
  .LZSS (Lempel Ziv Storer Szymanski)
   -LZSS+Huffman
    .LHA (LZ Huffman Archiver)
     -by Haruyazu Yoshisaki
    .AR002
     -by Haruhiko Okumura
    .deflate (ZIP V2.0)
     -by Phil Katz (PKWARE)
    .ARJ
     -by Robert K. Jung
    .UC
  .LZRW (Lempel Ziv Rose Williams)
   -by Rose Williams (Australia), the founder of comp.compression newsgroup
   -LZRW-1 to LZRW-4
 -LZ78
  proposed/invented by Jakob Ziv on 1978, thus it's called LZ78
  .LZW (Lempel Ziv Welch)
   -proposed by David Welch
   -patented by UniSys
   -used in GIF picture format
  .LZMW (Lempel Ziv Michael? Wagner)
   -proposed by Michael? & Wagner
  .LZAP (Lempel Ziv All Prefixes)
   by: J.S
  .Y (Yabbadabbadabbado)
   by D. J. Bernstein
   reinvented by Rose Williams as LZRW-5
 -LZFG (Lempel Ziv Fiala Greene)
  proposed by Fiala & Greene (1990)
  also called 'LZ with Finite Windows' (?)
  patented (?)
 -LZC
  used by Unix's Compress
 -lazy match
 -LZP (Lempel Ziv Predictor)
  by: Charles Bloom
  EdH: I never seen a successful implementation of LZP. No executable provided
   by the author and X1 am5 (LZP algo) hangs my cpu. Why?
Statistical
 -Huffman
  .invented by D.A. Huffman (1954?)
  .static Huffman
   2 pass
    read data to collect frequency distribution then reread data to
     compress
  .dynamic Huffman
 -Shannon-Fano
 -Arithmetic
  .Markov
  .PPM (Prediction by Partial Matching)
Magic Function Theory
---
Burrows-Wheeler Transformation (BWT)
 -proposed by Michael Burrows & David Wheeler
 -invented by David Wheeler (1983/1994 (?))
 -not compression algorithm, but reversibly transform data to format suitable
  for compression
 -BWT is proposed to be followed by MTF (Move To Front) coding
TAR
 used in Unix, combine multiple files into single file before compress
 TAR doesn't provide compression
 compressed data must be processed twice: first decompress it
  then unTAR to extract files in TAR-ed archive
Solid Archiving
 sees multiple (small/similar) files as single file before compress
 compressed data only be processed once, because the solid archiver 
 simultaneously decompress & extract files
---
MISC
---
-Too many compression algorithms are patented and often overlaps each others
 or comprise too wide algorithms
 .it try to patent mathematic algorithms while most court deals with source
  piracy
  it can't be settled properly in court
 .compressor author find difficulties to properly select & implement
  compression algorithms w/o getting sued
 .getting harder to invent & patent new algorithm
 .patent office doesn't have enough knowledge to examine patent requests
 .application author find difficulties on supporting standard, well-known
  but patented format
  ex: to use GIF you must pay to at least 30 parties!
-Peter Fenwick (New Zealand)
 write paper about 'Improved BWT Algorithm'
 write paper about 'Associative Coder' (?)
