Subject: High compression ratio algorithms

From: [email-masked] (Spaceman Spiff)
Date: 21 Feb 91 01:05:40 GMT

Great group! I've been waiting for it.

What can anyone tell me (well, everyone) about very high compression
ratio algorithms?

There's lots of standard compression methods out there:
Huffman is the trusty classic, L-Z a little more efficient in
most cases, RLE (Run Length Encoding) for faxes and some other occasions,
linear prediction for speech or continuous signals, and about 47 other methods
used for different applications. For most "standard" files, a "standard"
compression ratio is somewhere like 70%. (ie 1000 bytes -> 700 bytes)
[LOTS of fuzziness in there, but gives you a feel.] 

I would assume an adaptive algorithm which breaks a sequence into chunks and
then tests MANY different methods (like the ones I listed) and uses the best
method for each chunk would be close to optimal. Ideally, each chunk could be
broken into sub-chunks recursively if the overhead for each subdivision is
smaller than the compression savings. 

Is this how its done? It actually wouldn't be THAT hard to implement, and has
the great advantage of being able to compress the ((*#&$^ out of anything. 
The many methods available might even give it the fun ability to sometimes
compress its own output...

The severe disadvantage is compression CPU time. Each method would have to
be tested, (though you could have estimators, like figuring out the entropy
to see if Huffman will work without actually making the Huffman encodings),
so the compression would be SLOW..... 

However, decompression time would be basically unchanged from "standard" 
encodings, since each chunk is decoded ONCE using whatever decompression
method is appropriate to the compressor for that chunk.

I've been toying with trying to write a program like this. Do people think it
will work? If not, what IS the best known algorithm for super-compression?
Please don't mention encoding pictures by fractals. :-) (That could be another
thread.) 

My intent is to make a working compression algorithm for long-term archives
where space is important, or wide distribution, where many, many, many people
will get this compressed file and use it, so every K saved is an extra 10
Megs of storage saved around the world. :-) It would be stupid to use such
a slow algorithm for "Oh, I'm real close to quota. I'll smash some files
down before I log out", or for a small computer. Yet with '040s out, and
the power of RISC workstations, its worthwhile to give the CPU something
to chew on..

Reply to the board- I'd really like some discussion.

-Steve

------------------------------------------------------------------------------
Steve Worley                                           [email-masked]
------------------------------------------------------------------------------