Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!know!news.cs.indiana.edu!nstn.ns.ca!cs.dal.ca!ug.cs.dal.ca!chris
From: chris@ug.cs.dal.ca (Chris Robertson)
Newsgroups: comp.compression
Subject: Re: theoretical compression factor
Message-ID: <1991Apr3.001158.12011@cs.dal.ca>
Date: 3 Apr 91 00:11:58 GMT
References: <15098:Mar2512:53:1291@kramden.acf.nyu.edu> <18263:Mar2518:10:4091@kramden.acf.nyu.edu> <15626@smoke.brl.mil>
Sender: news@cs.dal.ca (USENET News)
Organization: Math, Stats & CS, Dalhousie University, Halifax, NS, Canada
Lines: 15
Nntp-Posting-Host: ug.cs.dal.ca

In article <15626@smoke.brl.mil> gwyn@smoke.brl.mil (Doug Gwyn) writes:

>                              ...  any invertible method that maps the
> domain onto the range, which is known to map at least one point to a
> shorter representation, MUST map at least one other point to a longer
> representation.  (I think this was noted somewhere in Knuth.)


Wouldn't it depend on the characteristics of the data to be compressed?
Under certain restrictions, ie, if there is redundancy built into the domain,
then why _couldn't_ you get a mapping such that every element of the domain
had a correlate shorter than itself?


 - chris