Message-ID: <332C1246.4FF1@pobox.oleane.com>
Date: Sun, 16 Mar 1997 16:31:18 +0100
From: Francois Charton <deef AT pobox DOT oleane DOT com>
Organization: CCMSA
MIME-Version: 1.0
To: Paul Derbyshire <ao950 AT FreeNet DOT Carleton DOT CA>
CC: djgpp AT delorie DOT com
Subject: Re: Problems using allegro
References: <19970312 DOT 054752 DOT 7495 DOT 0 DOT fwec AT juno DOT com> <19970315 DOT 101544 DOT 7423 DOT 14 DOT fwec AT juno DOT com> <332B9F32 DOT 79F2 AT pobox DOT oleane DOT com> <5ggnfp$7dv AT freenet-news DOT carleton DOT ca>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

Paul Derbyshire wrote:
> 
> What about the public-domain LZSS? Is the compression comparable to LZW?
> the speed? What's the algorithm?
> 

Lempel and Ziv published two algorithms for data compression, one in 77, 
and one in 78. LZW comes from LZ78, whereas LZSS comes from LZ77. The two 
algorithms are very different. 

Historically, in the 80s, LZW was almost the only algorithm in use: Unix 
Compress, ARC, the GIF format all relied on it. Nowadays, LZSS has 
developped and is used in most archive formats: pkzip, gzip, lha, arj, 
(and allegro...), as well as all executable compressors, use LZSS.

As regards compression rates, they are globally equivalent: LZW often 
does a little better on images, while LZSS is better on executables/text 
files.

As regards speed: 
LZW is "symetrical": it compresses and decompresses at the same speed, 
LZSS is asymetric: compressing is *very* slow (some 4 times slower than 
LZW) but decompressing is very fast: about twice the speed of LZW. 
Samely, the compressing algorithm for LZSS is complex, but the 
decompression routine is extremely simple. 

For this reason, LZSS has been used a lot for executable compression: the 
decompression code, being very small, can easily be prepended to the exe.

As regards the algorithm, the original article on LZ77 is: "A universal 
algorithm for sequential data compression", by Ziv and Lempel, in IEEE 
transactions on information theory, vol.23, nr.3, pp337-343 (may 77).

A great description of LZW and LZSS, as well as C code for 
implementation, information on speed and many more can be found in 
"the data compression book", by Mark Nelson, published by M&T books, in 
1992. (A second edition has been published since).

Regards
Francois