There are no magic compressors that can pack any data!!!

I shall now go through a semi-technical proof of the fact
that NO compressor can compress all data.

	

First of all, we must understand that all compressors of an
input file S must work statistically.  Really, this isn't
saying anything at all, or making any incorrect assumptions - it
is just a mode of interpretation (kind of like the various
interpretations of quantum mechanics - the results are always the
same under the mathematic framework, you just have some freedom in
choosing your philosophical viewpoint).  Let me describe
what I mean.

Each file S, we will assume is a string of characters in
an array, terminated by an EOF character of value 0x100 .
Imagine we "know" the probability of each file appearing;
Let us call this P(S) , then all we do to compress a file
is to assign a number to each S, and we write that number
in -log2(P(S)) bits.  It is known that you cannot do better
than this for a given P(S) (see Shannon).

Really, the only this the statistical view is to consider the 
probabilities P(S) of each code instead of the length L(S) of
each code ; by the relation L(S) = -log2(P(S)) , these views
are equal by a transform (kind of like Matrix Mechanics vs.
Wave Mechanics vs. q-number algebra ; I'm just full of quantum
mechanical analogies today).

But we can generalize this, for those of you who say
"you don't have to use a probability compressor!" - let us
just assign a code to each possible input S.  These codes
must be prefix codes in order for them to be uniquely
decodable - i.e. we do not want two codes to be confused
by the decoder.  Let us call the length of the code for a
certain input L(S) ; now all we do is write this code
with this length.  However, we cannot just choose our
lengths arbitrarily - obviously, if S is 2 bytes long,
then I could not write 1 bit for each code in S - some
of the possible values of S would be unspecifiable!  i.e.

S    code
---------
00    0
01    1
10    00
11    01

IS NOT OK - because the decoder doesn't know how long
code is, so when it sees '00' it doesn't know if that
means S = 00 or S = 10 ; if I want to use that code
set I must also write out code lengths, which make all
the codes longer.

It turns out there is an easy way to specify this
"decodability" requirement.  It is called the Kraft
Inequality.  I have written about it before in :

However, there is an equally good way of saying it, more simply:

For each L(S) let me define a number P(S) which I have not yet given
a name or meaning, and let me define it by the relation:

 L(S) = -log2( P(S) )

or P(S) = 2^( - L(S) )

Now, the decodability requirement is :

 Sum[ all S ] P(S) <= 1

And the average output length is minimized when this Sum is at
its maximum, i.e.

 Sum[ all S ] P(S) = 1

Furthermore, it is a property of the definition of P(S) that

 0 < P(S) < 1    ( with L(S) > 0 )

Now these properties look just like the properties of a probability,
so I will call P(S) a probability, since it acts just like one,
whether it really is one or not.

Thus, we come back to the assertion : however I compress the
stream S, I MUST assign each S an output length L(S) ; these
lengths are NOT arbitrary, but must satisfy the Kraft inequality
to be decodable.  This requirment is the same as saying that
each L(S) corresponds to a P(S), which acts like a probability,
and is constrained by normal probability rules.  Thus, finding
the best L(S) set is identical to finding the best P(S) set,
and coding with L(S) = -log2( P(S) ).

NOTE that I did not say ANYTHING about our coder being
a statistical coder - all my conclusions simply came from the
fact that it was a coder which wrote a length L(S) for each
input S, and that its output was decodable.  Thus these
conclusions apply to ANY compressor - including one that
works by mathematical tricks like factoring !!!!!

Now, we can say some more very nice things given this fact :

1. Any statistical coder (PPM,LZ77,Zip,HA,ACB,etc. etc.) is
   the same as the simple P(S) coder I have described, except
   that instead of keeping a massive offline database of every
   P(S) , they use tricks to adaptively figure out P(S) based
   one what they expect a "reasonable" file to look like.
   In general, a coder which works character by character is
   just a subset of the more general whole-file-at-once coder

2. Because we know we are constrained by the Kraft Inequality,
   my proof from  Power of the Kraft Inequality 
   Holds on our L(S) set : therefore if you compress one possible
   input file by a factor F, you MUST expand another file by
   a factor greater than F - this is a simple mathematical consequence
   of the Kraft Inequality.

3. Let's take a look at what the "average" output length will be.
   Imagine that each input S occurs with a probability Q(S) , exactly.
   Note that Q(S) not necessarily = P(S) , because P(S) isn't yet
   a probability, it is just defined to be P(S) = 2^( - L(S) ) , from
   the output lengths of our general coder.  Now, the output length
   L(S) will occur with probability Q(S), so the average output length
   L(avg) is:

     L(avg) = Sum[ all S ] Q(S) * L(S)

   but L(S) = - log2( P(S) ) so:

     L(avg) = - Sum[ all S ] Q(S) * log2( P(S) )

  Thus let us define H = min[ L(avg) ] = - Sum[ all S ] P(S) * log2( P(S) )

  Now we clearly see that in the best case, P(S) is indeed the probability
  of S appearing, and that the Entropy H is equal to the minimum possible
  average output length.  Thus when people say that you cannot code
  better than the entropy, IT IS TRUE , and it DOES apply to ANY coder!!!

4. Let me attempt a short proof of H = min[ L(avg) ] ;
   I will use a two-symbol (binary) alphabet for S; S = 0 or 1 ; Any
   larger alphabet of S can be trivially constructed by recursive
   application of a binary coder to a binary tree.

   P(0) = a
   P(1) = 1-a
   Q(0) = b
   Q(1) = 1-b

   L(avg) = - Sum[ all S ] Q(S) * log2( P(S) )
          = - [ b * log2( a )  + ( 1-b ) * log2( 1-a ) ]

   Now, let us find the value of a that minimizes this L(avg)
   It is determined by :

   d/da [ L(avg) ] = 0

   L(avg) = - ( 1 / ln(2) ) * [ b * ln(a) + (1-b) * ln(1-a) ]

   d/da [ L(avg) ] = - ( 1 / ln(2) ) * [ b * (1/a) + (1-b) * (-1/(1-a)) ]

     = 0

     b/a - (1-b)/(1-a) = 0

   b/a = (1-b)/(1-a)

   b/(1-b) = a/(1-a)

   b = a

   -> L(avg) minimized when P(0) = Q(0)

   proves it for the binary case, therefore for the general case.

Back to the Index

The free web counter says you are visitor number