Subject: A brief compression bibliography

From: [email-masked] (Peter Gutmann)
Date: 1 Apr 91 16:09:10 GMT

I thought I'd post the following list of useful references for data  
compression articles...they include my own opinions and comments on them, and 
were chosen because I found them useful, they represent some outstanding  
achievment in data compression, they include code which makes implementation  
particularly easy, or a mixture of the above.  I have excluded research  
reports, obscure publications, private communications, and reading through  
source code, since most people won't have access to this sort of thing.  
    This is a very much abbreviated list.  If there is any great demand for it
I'll type up a full list (which will be rather long) of references, but I'm no
going to give my opinion of each and every one (which is probably just as well
too), just the name and where it appears.  
    Format flames > /dev/null.  
      
General  
-------  
  
[Lele 1987] Lelewer, D.A, and Hirschberg, D.S.  "Data Compression", ACM  
    Computing Surveys, Vol.19, No.3 (September 1987), p.261.  
    A survey of data compression techniques which concentrates on Huffman  
    compression and makes only passing mention of other techniques.  
  
[Stor 1988] Storer, J.A.  "Data Compression: Methods and Theory", Computer   
    Science Press, Rockville, MD.  
    A survey of various compression techniques, mainly statistical  
    non-arithmetic compression and LZSS compression.  Includes complete Pascal
    code for a series of LZ78 variants.  
      
[BWC 1989] Bell, T.C, Witten, I.H, and Cleary, J.G.  "Modeling for Text  
    Compression", ACM Computing Surveys, Vol.21, No.4 (December 1989), p.557  
    A good general overview of compression techniques (as well as modeling for
    text compression); the condensed version of "Text Compression".  
  
[BWC 1989] Bell, T.C, Witten, I.H, and Cleary, J.G.  "Text Compression",  
    Prentice-Hall 1989.  
    *The* reference on data compression.  
      
[Will 1990] Williams, R.  "Adaptive Data Compression", Kluwer Academic  
    Publishers 1990.  
    Still waiting for it on back order from Australia.  NZ price is ~$250!  
  
LZ77  
----  
  
[Bell 1986] Bell, T.C.  "Better OPM/L Text Compression", IEEE Transactions on 
    Communications, Vol.34, No.12 (December 1986), p.1176.  
    An implementation of LZSS compression using a binary tree to implement the
    dictionary.   
  
[Bren 1987] Brent, R.P.  "A Linear Algorithm for Data Compression", Australian
    Computer Journal, Vol.19, No.2 (May 1987), p.64.  
    An LZSS implementation with hashing, followed by dynamic Huffman coding.  
    Contains some pseudocode.  
  
[LZFG 1989] Fiala, E.R, and Greene, D.H. "Data Compression with Finite  
    Windows", Communications of the ACM, Vol.32, No.4 (April 1989), p.490.  
    A combination of LZ77 and LZ78 schemes which uses a complex data structure
    to achieve good compression and a fast runtime.  Presented in "Text  
    Compression" as LZFG.  Note that LZFG is patented by Xerox.  This scheme i
    used in the Lha and Arj archivers.  
  
LZ78  
----  
  
[LZW 1984] Welch, T.A.  "A Technique for High-Performance Data Compression",  
    IEEE Computer Journal, June 1984, p.8.  
    The LZW compression technique.  Includes pseudocode.  Note that LZW is   
    patented by Unisys.  Variants of LZW are used in UNIX compress, V42bis,  
    and various archivers (SEA Arc, PKZIP, StuffIt, etc).  
[Nels 1989] Nelson, M.R.  "LZW Data Compression", Dr.Dobbs Journal, October  
    1989, p.29  
    A C implementation of [LZW 1984].  
  
Arithmetic Statistical  
----------------------  
  
[WNC 1987] Witten, I.H, Neal, R.M, and Cleary, J.G.  "Arithmetic Coding for  
    Data Compression", Communications of the ACM, Vol.30, No.6 (June 1987),  
    p.520.  
    A good introduction to and practical implementation of arithmetic coding i
    C.  Includes a simple order-0 model.  
[Abra 1989] Abrahamson, D.M.  "An Adaptive Dependancy Model for Data  
    Compression", Communications of the ACM, Vol.32, No.1 (January 1989), p.77
    An extension of [WNC 1987] to use a simple order-1 model.  
      
[DMC 1987] Cormack, G.V, and Horspool, R.N.S.  "Data Compression using Dynamic
    Markov Modeling", The Computer Journal, Vol.30, No.6 (June 1987), p.541.  
    The DMC compression scheme, a binary arithmetic coder using a Markov model
    Contains pseudocode but it has a bug.  Presented in "Text Compression" as 
    DMC.  
  
[Word 1989] Moffatt, A.  "Word-Based Text Compression", Software - Practice  
    and Experience, Vol.19, No.2 (February 1989), p.185.  
    A scheme which uses arithmetic coding of words in text.  Presented in "Tex
    Compression" as WORD.  
  
[PPMC 1990] Moffatt, A.  "Implementing the PPM Data Compression Scheme", IEEE 
    Transactions on Communications, Vol.38, No.11 (November 1990), p.1917.  
    A discussion on the implementation of the PPMC compression scheme, a  
    maximum-order 3 arithmetic compressor.  Presented in "Text Compression" as
    PPMC.  
  
[Nels 1991] Nelson, M.R. ???, Dr.Dobbs Journal, February 1991.  Still waiting 
    for my copy to arrive.  
  
Non-Arithmetic Statistical  
--------------------------  
                            
[Knut 1985] Knuth, D.E.  "Dynamic Huffman Coding", Journal of Algorithms No.6 
    (1985), p.163.  
    An implementation of adaptive Huffman coding.  Includes Pascal-ish code.  
  
[Splay 1986] Jones, D.W.  "Application of Splay Trees to Data Compression",  
    Communications of the ACM, Vol.31, No.8 (August 1988), p.996  
    A simple, fast statistical compression algorithm.  Includes full Pascal  
    code.  
      
[Vitt 1987] Vitter, J.S.  "Design and Analysis of Dynamic Huffman Codes",   
    Journal of the ACM, Vol.34, No.4 (October 1987), p.825.  
    Another implementation of adaptive Huffman coding.  Includes pseudocode.  
    Used in the UNIX compact program.  
      
[Cope 1989] Copeland, J.A. "Data Compression Technique for PC Communications",
    IEEE Journal on Selected Areas in Communications, Vol.7, No.2 (February  
    1989), p.246.  
    A simple, easily-implemented technique, much like MNP5, which encodes char
    as code of length 4-12 bits.  
  
Other  
-----  
  
[BSTW 1986] Bentley, J.L, Sleator, D.D, Tarjan, R.E, and Wei, V.K.  "A   
    Locally Adaptive Data Compression Scheme", Communications of the ACM,  
    Vol.29, No.4 (April 1986), p.320.  
    A scheme which encodes words as an integer count since their last use.  
    Present in "Text Compression" as MTF.  
[Maek 1989] Maekinen, E. "On Implementing Two Adaptive Data-Compression   
    Schemes", The Computer Journal, Vol.32, No.3 (1989), p.238.  
    Some note on implementing [BSTW 1986].  
  
Notes  
-----  
  
 - There has been some confusion about terminology for variants of Huffman  
compression schemes (for example I would call [Knut 1985] "Adaptive Huffman  
Coding" not "Dynamic Huffman Coding" in line with more recent usage).  The  
three variants are:  
  
 1. Static coding:   Uses fixed tables for coding/decoding.  
 2. Dynamic coding:  Makes one pass to build up tables, second pass to encode.
 3. Adaptive coding: Adapts to the data as it is processed.  
   
 - Any proper noun in the above list is probably a TM of someone or other.  
   
 [email-masked] || [email-masked] || [email-masked]  
                     (In order of decreasing reliability)  
Warning!  
  Something large, scaly, and with fangs a foot long lives between <yoursite> 
and <mysite>.  Every now and then it kills and eats messages.  If you don't  
receive a reply within a week, try resending...