Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!crdgw1!uunet!bywater!arnor!arnor!victor From: victor@watson.ibm.com (Victor Miller) Newsgroups: comp.compression Subject: Re: theoretical compression factor Message-ID: Date: 4 Apr 91 15:23:53 GMT References: <46618@ut-emx.uucp> <5239@ns-mx.uiowa.edu> Sender: news@watson.ibm.com (NNTP News Poster) Reply-To: victor@watson.ibm.com Organization: IBM, T.J. Watson Research Center Lines: 16 In-Reply-To: jones@pyrite.cs.uiowa.edu's message of 3 Apr 91 19:46:35 GMT Nntp-Posting-Host: irt There are two kinds (at least) of information: statistical, of which entropy is the answer (only in an expected sense), and computational, as in Kolmogorov-Chaitin-Martin-Lof, etc. My favorite example to get people thinking is from a paper of Ziv and Lempel: Construct a sequence of bits as follows: first write down in order all 1 digit binary numbers (with leading zeroes if they are there), then all two digit, etc. The surprising fact that they prove is that this sequence is incompressible by ANY finite-state compressor (of which Huffman, or arithmetic coders are good examples), but it is rather easy to see that an efficient way of transmitting this sequence is to send a program to generate it, along with the length of the sequence. -- Victor S. Miller Vnet and Bitnet: VICTOR at WATSON Internet: victor@watson.ibm.com IBM, TJ Watson Research Center