Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!uakari.primate.wisc.edu!polyslo!vlsi3b15!batman!nicholaA
From: nicholaA@batman.moravian.EDU (Andy Nicholas)
Newsgroups: comp.sys.apple
Subject: Re: ShrinkIt for the IIgs (very long, 11k)
Message-ID: <434@batman.moravian.EDU>
Date: 25 Oct 89 14:10:46 GMT
References: <8909300944.AA10524@trout.nosc.mil> <10743@phoenix.Princeton.EDU> <11408@smoke.BRL.MIL>
Organization: Moravian College, Bethlehem, PA
Lines: 61

In article <11408@smoke.BRL.MIL>, gwyn@smoke.BRL.MIL (Doug Gwyn) writes:

> There is clearly room for substantial improvement in data compression
> technology.  When I was implementing a LZW decoder for a GIF-to-rational
> image translator, I discovered several places in the GIF LZW algorithm
> (apparently borrowed from the BSD UNIX "compress" program) where better
> compression was attainable.

But usually you'll find (I think kent can back me up) that those incremental
improvements usually only increase the compression ratio by a fractional
part of a percent and don't amount to much unless you make a lot of
modifications... in which case your algorithm hasn't been 'tweaked,' it's
been rewritten.  :-)

> There is at least one good textbook on data compression (I don't remember
> the authors and the book is not at hand);

J.A. Storer, Data Compression: Methods and Theory, Computer Science Press, 1988
R. Sedgewick, Algorithms, 2nd ed., Addison-Wesley, 1988

> perhaps a concerted effort
> should be made to devise the best feasible compression algorithms first
> and implement them after we've completely solved the problem.

Whoa!  CS guys have been trying to do things like this for almost 40 years
now.  There are many really decent algorithms out there (LZhuf, LZss, LZ,
LZw, LRU, Huffman, etc) that some people just haven't bothered writing for
one machine or another.  To think that we should wait until we've solved
the problem is like waiting to treat cancer while you await its cure.  It's
not gonna work... :-)

> There are
> several existing candidates for "good enough" compressers while this
> problem is being researched.

Yup, LZSS, LZHUF, LZARI (gads is this slow), Arithmetic Compression (this too),
LZW, LRU, Huffman, and a host of others have already been developed.  I think
that to wait until some sort of wonderful 'research' on the promise of better
data compression it would be wiser to try to implement the more powerful
compression algorithms available today for a given type of cpu.

The 3 most powerful that execute in a reasonable length of time that I'm
aware of (throw in more if you know of any) are LZHUF, LZARI (ok, maybe this
is a little unreasonable...) and LRU.  I haven't timed anything with LRU,
but they claim its 10-25% faster than LHARC and 10-15% smaller than LHARC's
output (which is LZHUF).  If this is true, it's not too shabby.  Then again,
the downside is that these algorithms will NEVER be implemented on a IIe/c
because the data structures which LRU requires take more than 64k all by
themselves.  LZHUF is doable.. I think I once calculated that they would
require 28k of data structures to run, and so could be backfitted into the
8-bit version of ShrinkIt at least to be decoded.

If anyone knows something I don't, pitch in...

andy

-- 
Andy Nicholas                       InterNET: shrinkit@moravian.edu
Box 435                                 uucp: rutgers!liberty!batman!shrinkit
Moravian College                       GEnie: shrinkit
Bethlehem, PA  18018          America Online: shrinkit        CIS: 70007,3141