Re: More of an Algorithems question

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?
.

Relevant Pages

  • Re: data compression program
    ... Then I should get a lawyer. ... should refine your claim regarding what your algorithm accomplishes. ... The common contract terms say something like "anything developed during ... is that NO algorithm can losslessly compress truly random data (and BTW, ...
    (comp.theory)
  • Re: More of an Algorithems question
    ... >How can I proove that no Algorithm can compress every file of length ... However there is an algorithm that will losslessly compress every file ... Prev by Date: ...
    (sci.math)
  • Re: data compression program
    ... Barb Knox wrote: ... That's what makes it better than the competition. ... If that were true then you could losslessly compress any file down to just 1 bit, by repeatedly running your algorithm. ...
    (comp.theory)