From: joel@ce.ucsc.edu (Joel Darnauer)
Newsgroups: comp.compression
Subject: Multiple Decoders was Stupid compressor idea
Date: 14 Apr 92 11:07:34 GMT


In article <2367@accucx.cc.ruu.nl>, nevries@accucx.cc.ruu.nl (Nico de Vries.) writes:

|  Suppose we take a compressed file (doesn't matter which compressor) and
|  we remove a single byte. The first one. Now what the decompressor does
|  is trying ann 256 options and takes the file which looks most likely (this
|  is the weak part of cource but we could try decompression an compressio
|  and if the decompressor goes wrong we just don't remove the byte).
|  This seems to work to me.

It's an interesting idea, but I'm inclined to think that if you already know
enough about the data that you are encoding to recognize "good" decoded data from
"bad" decoded data, you could simply employ that information in a single
decoder-encoder pair.  Say for example, we do the above procedure for english text
and our method for detecting whether a file is good is to scan it for mispellings
or grammatical errors.  After throwing away the first byte, we see if there is a
single decodable message that has no spelling errors.  If there is more than one,
we must signal the decoder that the byte was not thrown away *and* send it.  Since
there is no way to guarantee that the byte is not absolutely necessary to the
decodability, we must have a way of telling the decoder whether it was sent or
not.  Sometimes we can get away with a bit, otherwise, we send a byte and a bit.

We can improve this method as follows.  Suppose we decide that N possible values
of the 256 values the byte could have are possible values for a valid message. 
The decoder and encoder are using the same analysis, so say they both have the
same subset of of values to choose from in some array M[N].  Instead of sending
the actual value, we send the index into the array of valid numbers - which is
guaranteed not to be bigger than a byte.  In fact if we know enough about our
data, most of the time we will only need to pick from two or three possible
choices.  Further savings could be realized by sorting the array M[] by some
probability and then using a varaible length code to economize even more bits.

But why stop there?  Why not throw away every byte that isn't necessary?  In fact,
why not throw away every *bit* that isn't needed.  This is exactly what most
lossless coders try to do anyway - they send only the minimum number of bits
needed to discriminate between the possible valid messages.  Most such encoders,
however, cannot afford to enforce any sort of grammar on thier message.  

What keeps us from doing this in real life is a combination of reasons.  First,
The complexity invlolved in doing 256 possible decodes is high, but the cost of
checking for complex grammar can be even higher!  Also, imagine what would happen
if the message to be encoded didn't meet our expectations.  There is no model of
data that is simultaneously simple and general.  I would expect that adaptive
schemes like ziv-lempel woudl do much better for a wider class of data, and be a
lot handier than having a compression routine for every file format.  There are
ways to get around many of these problems, but I would bet that the advantage for
any practical scheme will be small (less than 10%).

Curiously enough, this sort of scheme has been proposed for (usu. lossy) image
compression, but backwards.  Feed the image or part of an image into a bank of 256
different compressors, and then pick the encoder that did best, and send a byte to
identify it followed by the message.  The decoder knows in advance which decoder
to use, so it only decodes the correct message.  If your encoding is simple enough
to use parallel hardware or if you don't care about time, this could give you some
advantages.  I think, that the advantage over adaptive coding schemes in not that
great, however.

joel darnauer

[1] Majid Rabani and Paul W. Jones,"Digital Image Compression Techniques",
	1991, SPIE Optical Engineering Press.

-- 
Newsgroups: comp.compression