From: kalki33!system@lakes.trenton.sc.us
Newsgroups: talk.origins
Subject: Re: CWACKers and Complexity (bits of information definition)
Date: Tue, 10 Nov 92 14:19:31 EST
Reply-To: kalki33!system@lakes.trenton.sc.us
Organization: Kalki's Infoline BBS, Aiken, SC, USA

kv07@IASTATE.EDU (Warren Vonroeschlaub) writes:

> In article <7F9VTB1w165w@kalki33>, kalki33!system@lakes.trenton.sc.us writes:
> > If we confine the discussion to actually existing books, eliminating the
> > nonsense ones and the ones which were never printed, then it is possible
> > to compress the descriptions with suitable coding (i.e. Huffman). But
> > this introduces an algorithm whose information content must also be
> > taken into account. In addition, we would have to supply all the text of
> > all the existing books to the coding process!
> 
>   Uh, not quite.  Are you saying that my hard disk with Stacker (which
> compresses the data) takes up just as much space as the uncompressed data?

No. I was responding to a question of how to determine the information
content of a typical "book". I emphasized that if we use the set of
ALL POSSIBLE BOOKS, then each book in that set can be specified by a
certain minimum number of bits (# of chars in "average" book times log
of # of characters in the alphabet), and no fewer, since in this set all
letters and all letter combinations occur with equal frequency.

However, since all possible books have not been printed, and never will
be, if we restrict the set to ACTUALLY EXISTING BOOKS, then using some
suitable coding we can obtain a smaller size for the bit string which
will uniquely specify each book in the smaller set.

In the smaller set, the set of actual books, there are unequal
frequencies of occurrences of letters and letter combinations. Thus in
standard english the letter "e" occurs more frequently than other
letters. This fact makes compression possible.

In order for compression --or at least, Huffman compression-- to work,
we first need to determine the frequency counts for each character in
the set of data we wish to compress. We can guess at this by using a
table of the average frequencies of occurrence of letters in standard
english (or some specified alphabet). Or we can get an exact figure by
actually counting each letter in the entire set of data. In the former
case, we run the risk of not obtaining the greatest possible compression
ratio, and in the latter case we have to perform the laborious process
of running the entire set of data through a counting algorithm. In
either case, the encoding algorithm itself will have to be run, and this
will introduce an extra amount of information (possibly small) to the
whole process.

For example, if you want to ZIP a file, you must have the ZIP program
itself stored somewhere. This is extra information. Also, the ZIP
program must process each character in the file to be compressed, so
that the original file must be stored somewhere too. The final outcome
may be a smaller file, but the total process actually involves more
information than was in the original file.

>   Your error seems to be in assuming that the compression algorithm encodes t
> data being compressed in a table of some sort.  This is not the case.  Consid
> LZW compression where the encoding/decoding tables are built dynamically duri
> compression/decompression.

I was using the example of Huffman coding because, in principle at
least, it can give the greatest possible compression ratio. I believe
that my analysis was correct.

>   Also (and I am not 100% sure of this, so any experts correct me if I have t
> confused with another aspect of information theory) the actual data isn't wha
> is supposed to be used anyway.  The information content is supposed to be bas
> on the size of the smallest universal Turing machine that can generate the da
> Taking advantage of proprietary compression schemes is assumed, not excluded.

Yes, that is true. However, in the case of a data source that is
"random", (and the set of all possible books will exhibit statistical
randomness, since every letter and every combination of letters will
occur with equal frequency), the shortest Turing machine program will be
exactly the one which simply copies the data to its tape, letter by
letter. To do this, the data will have to be on the tape (or somewhere)
already, and will thus be part of the program!

There may be some argument here from Turing machine specialists, since a
distinction can be made between the "program" and the "data". However,
it must be admitted that the total information needed by the Turing
machine includes not only its string of instructions but also the string
of data on which it operates.

I think the difficulty of understanding may lie in realizing the
distinction I made between the two sets of books. I understood "all
possible books" to mean all possible strings of characters of a given
length (the number of characters in a typical "book") drawn from a fixed
alphabet of 64 characters (covering upper/lower case, numerals and some
punctuation). This of course includes immense numbers of "jibberish"
books, as well as some "meaningful" books that have not yet been --or
never will be-- written.

Randomly distributed --or uniform-- information may not be compressed
any further, whereas nonuniform information certainly can.

Of course, I too welcome the comments of professional information
theorists!

Sincerely,
Kalki Dasa


       -------------------------------------------------------
      |  Don't forget to chant:   Hare Krishna Hare Krishna   |
      |                           Krishna Krishna Hare Hare   |
      |                           Hare Rama Hare Rama         |
      |                           Rama Rama Hare Hare         |
      |                                                       |
      |   Kalki's Infoline BBS Aiken, South Carolina, USA     |
      |        (kalki33!kalki@lakes.trenton.sc.us)            |
       -------------------------------------------------------
Newsgroups: talk.origins