Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!rice!uw-beaver!mit-eddie!andante!alice!jj
From: jj@alice.att.com (jj, like it or not)
Newsgroups: comp.compression
Subject: Re: theoretical compression factor
Message-ID: <20144@alice.att.com>
Date: 30 Mar 91 03:19:08 GMT
References: <1991Mar26.220519.1242@unislc.uucp> <1991Mar27.120829.26094@bingvaxu.cc.binghamton.edu> <20135@alice.att.com> <1991Mar29.031127.9128@bingvaxu.cc.binghamton.edu>
Reply-To: jj@alice.UUCP (jj, like it or not)
Organization: NJ State Home for Bewildered Terminals
Lines: 35

In article <1991Mar29.031127.9128@bingvaxu.cc.binghamton.edu> kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) writes:
>In article <20135@alice.att.com> jj@alice.UUCP (jj, like it or not) writes:

>Consider the scheme I outlined earlier -- of comparing an input bitstream with 
>a random bitstream and just storing the differences in delta form (e.g. 
>fixed-length or Huffman coded). This doesn't _appear_ to use history -- the 
>next bit output by an uncompressing program doesn't use the previous bits of 
>the uncompressed string to obtain the next bit. The compressing program
>doesn't build up any dictionary. Or does it? (That's Q1).
What you're doing is building a model.  If your model fits, you can
do better than a historyless method.  The model itself is the
history, you have to choose the model (you call it a random number
generator, stoichastic methods, LPC methods, and such suggest other
approaches) from the knowledge of the signal.  That's your
history.

If your model (whatever it is) doesn't fit, you'll likely need
MORE bits.

>-(p lg p + q lg q)=0.926346	<---	maybe this is log_2 instead of log_e?
Always log base 2.  Not ever log base e.  Sorry, thought that was
obvious from context, since we're talking about bits here.



>What gives? Perhaps there are additional O(1) factors involved in the 
>``p log p'' limit? (That's Q2).
Anytime you have a model of some sort, you aren't doing historyless
coding.  You are assuming SOMETHING about the signal to be coded
beyond the single-token distribution.
-- 
       -------->From the pyrolagnic keyboard of jj@alice.att.com<--------
Copyright alice!jj 1991,  all rights reserved,  except transmission  by USENET and
like free facilities granted.  Said permission is granted only for complete copies
that include this notice.    Use on pay-for-read services specifically disallowed.