Re: How much lossless compression is possible in images?

From: Mxsmanic (mxsmanic_at_hotmail.com)
Date: 12/09/04 

Date: Thu, 09 Dec 2004 05:24:26 +0100

*** T. Winter writes:

> What is a perfect algorithm of theory? I have honestly no idea.

To me, it's an algorithm that accomplishes its compression without any
overhead.

> Why fixed-length bit strings?

For simplicity.

> Now if your compression uses a fixed coding table things
> might be different. Off-hand I do not know, but I expect that in that
> case indeed total sizes might be equal.

In theory a compression algorithm just performs a simple substitution.
It should not have to produce a total number of output bits for all
possible strings that is greater than the total number of input bits for
all possible strings. But I haven't considered this in depth and I may
be missing something. This would have to be a "perfect" algorithm, as
well, that is, one that adds no overhead.

> Yes, of course. It is necessary to make the decompressor work. Consider
> run-length encoding on bytes. You need a marker to show that the next
> byte is a count and not a plain byte. On the other hand, when the next
> plain byte is the marker you have to do other things (that increase the
> code) to let that show. So suppose you use 255 as marker, the next
> byte when it has the value 0..254 as a count of 4..258, and a plain byte
> of 255 just be doubled. Now you know that all strings that do not
> contain the 255 byte will decrease in size or stay equal. All strings
> that contain the 255 byte and do not contain a repetition of 4 or more
> equal bytes will increase in size. For the remainder it can go either way.
> I *think* that in the end the total size of all possible messages will be
> larger.

The question is, does there exist an algorithm that does not add any
overhead? I think a simple substitution table would qualify, but I'm
not sure, nor am I sure how the length of strings is to be treated (is
it counted as part of the encoded information in the string?). 

-- 
Transpose hotmail and mxsmanic in my e-mail address to reach me directly.
Quantcast