Re: More of an Algorithems question

On Thu, 17 Nov 2005 12:51:17 -0500, quasi wrote:
> On Thu, 17 Nov 2005 17:21:45 +0000 (UTC), Dave Seaman
><dseaman@xxxxxxxxxxxx> wrote:

>>On Thu, 17 Nov 2005 12:15:12 -0500, quasi wrote:
>>> On Thu, 17 Nov 2005 15:07:58 GMT, cri@xxxxxxxx (Richard Harter) wrote:
>>
>>>>On 15 Nov 2005 14:55:51 -0800, "Filter" <filtermedialtd@xxxxxxxxx>
>>>>wrote:
>>>>
>>>>>
>>>>>Hi,
>>>>>
>>>>>How can I proove that no Algorithm can compress every file of length
>>>>>10^6?
>>>>
>>>>However there is an algorithm that will losslessly compress every file
>>>>of length 10^6 except one.
>>>>
>>
>>> I don't believe that.
>>
>>> The pigeonhole principle applies easily to invalidate such a claim ...
>>
>>> Let n=10^6.
>>
>>> There are 2^n possible files with n bits, but only 2^(n-1) files with
>>> n-1 bits. Hence, at most half the files can be compressed.
>>
>>There are 2^n-1 files with fewer than n bits. Hence, the claim stands.

> Not by my count.

> For example, 16 possible files with 4 bits but only 8 possible files
> with 3 bits, no?

Are there any other files with fewer than 4 bits that you have overlooked in
your count?


--
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book&bookid=228>
.

Relevant Pages