🚀 go-pugleaf

In article <1991Mar24.152106.6333@pegasus.com> shaw@pegasus.com (Sandy Shaw) writes:
>I am trying to get the maximum compression possible of the following
>32 byte hex file(in ASC): 
>
>f3e9 ec5c 8bec ecdb ece9 ec12 ec3f ecec
>0cbb 8bec 5cdb ecdb 5c9c bbec 8bdb 9cec

I suspect that this isn't what you're looking for, but I figure
SOMEBODY's got to say it.

How about the following compression scheme: 

The bit string "0" represents the 32 byte sequence:

    f3e9 ec5c 8bec ecdb ece9 ec12 ec3f ecec
    0cbb 8bec 5cdb ecdb 5c9c bbec 8bdb 9cec

Any bit string beginning with a "1" represents the sequence of bits
following the 1.

Note:  This is a compression scheme to the extent that it allows all bit
strings to be represented.  It also gives maximum compression for the given
hex file, unless one is allowed to encode it as the empty string.

It may seem that I'm just making a wisecrack, but I think there is a valid
point here.  That is, it's not immediately clear how one may ask this sort
of compression question about a single string (as opposed to infinite families
of strings) without leading to the trivial solution I have outlined above.

Perhaps you are looking for the notion of Kolmogorov complexity, roughly the 
length of the shortest program that can produce a given string.  For a single
string, even this question can only be posed in an interesting manner for
a given computer or Turing machine (i.e. what's to stop me from assuming my
programming language has a primitive "!" that prints the above string?).

--
Paul Callahan
callahan@cs.jhu.edu