Xref: utzoo alt.comp.compression:158 comp.compression:15 Path: utzoo!utgpu!cs.utexas.edu!swrinde!elroy.jpl.nasa.gov!ames!haven!umd5!galileo.cs.jhu.edu!callahan From: callahan@cs.jhu.edu (Paul Callahan) Newsgroups: alt.comp.compression,comp.compression Subject: Re: Trying to get maximum compression Message-ID: Date: 24 Mar 91 20:29:58 GMT References: <1991Mar24.152106.6333@pegasus.com> Reply-To: callahan@galileo.cs.jhu.edu.UUCP (Paul Callahan) Organization: JHU Computer Science Deparment, Baltimore MD Lines: 38 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