Newsgroups: comp.compression Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!sarah!bingnews!kym From: kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) Subject: Re: theoretical compression factor Message-ID: <1991Apr4.230820.3941@bingvaxu.cc.binghamton.edu> Organization: State University of New York at Binghamton References: <46618@ut-emx.uucp> <5239@ns-mx.uiowa.edu> Date: Thu, 4 Apr 1991 23:08:20 GMT In article victor@watson.ibm.com writes: >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. Hmmm, interesting. I presume the same is true for all ``normal'' sequences over a given alphabet? -kym