Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!rutgers!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: <20159@alice.att.com>
Date: 2 Apr 91 19:47:00 GMT
References: <20135@alice.att.com> <1991Mar29.031127.9128@bingvaxu.cc.binghamton.edu> <20144@alice.att.com> <1991Apr2.034441.28170@bingvaxu.cc.binghamton.edu>
Reply-To: jj@alice.UUCP (jj, like it or not)
Organization: NJ State Home for Bewildered Terminals
Lines: 31

In article <1991Apr2.034441.28170@bingvaxu.cc.binghamton.edu> kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) writes:
>In article <20144@alice.att.com> jj@alice.UUCP (jj, like it or not) writes:
>I guess the mere _selection_ of the random bit generator _may_ be considered 
>building a model of the data -- in which case _any_ compression technique 
Exactly.
>selects such a model & there _is_ no historyless compression (as you
>seem to imply that model-building and historylessness are exclusive).
No, you have a model that subsumes history, in that the RNG
has predictable outputs, and you use it as a filter.
That is different than knowing the single-token probabilities
alone.

>Is p lg p a hard-and-fast bound or not? I still think it's an average.

It's ALWAYS the average rate.  Given that you're using compression,
you can't measure any other thing, unless you have a fixed message
set, and that's all.  (In which case you should enumerate your
messages, perhaps huffmanwise...)  If you have  any set of data
with the overall 'p' known, that is the average rate for THE WHOLE
SET. Parts of it may do better, because they may hit shorter
symbols (for instance), but if you look at the probabilities
of THAT PART, you should find that you don't do better than
the p log p chosen over your locality, without a model.

I think you need to revisit the basic statistical assumptions
of compression.
-- 
       -------->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.