Mail Archives: djgpp/1997/03/16/10:54:30
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
- Raw text -