Re: More of an Algorithems question

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.


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

Relevant Pages

  • Re: Attention Sean - question about CSI
    ... is possible to compress any given string to 1 bit. ... except the compressed data and the description of the algorithm, ... In our universe, there is one common reference: ...
    (talk.origins)
  • Re: compression type
    ... occurance of what repeats, for there to be a token, for how tokens ... see its construction algorithm. ... It's very limited to think that's the only way to compress, ... made different, to the other shape, where the math to say one shape ...
    (comp.compression)
  • Re: Attention Sean - question about CSI
    ... is possible to compress any given string to 1 bit. ... except the compressed data and the description of the algorithm, ... In our universe, there is one common reference: ...
    (talk.origins)
  • Re: Attention Sean - question about CSI
    ... It should compress very ... If I am allowed to choose the compression algorithm *after* ... which compresses that string to a single bit. ... from the binary code, and use it to decompress the data, then ...
    (talk.origins)
  • Re: Attention Sean - question about CSI
    ... It should compress very ... If I am allowed to choose the compression algorithm *after* ... which compresses that string to a single bit. ... and decompress readable text to algebraic combinations of large random ...
    (talk.origins)