Re: More of an Algorithems question

On Thu, 17 Nov 2005 13:13:06 -0500, quasi <quasi@xxxxxxxx> wrote:

>On Thu, 17 Nov 2005 17:59:28 +0000 (UTC), Dave Seaman
><dseaman@xxxxxxxxxxxx> wrote:
>
>>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?
>
>Ok, I see my confusion.
>
>I failed to take into account files with less than (n-1) bits.
>
>I get it now -- thanks.
>
>quasi

Ok, but then along the lines of what I was thinking, the following
claim is valid:

In any lossless compression scheme, less than half of the files with n
or fewer bits can be compressed.

quasi
.

Relevant Pages

  • Re: More of an Algorithems question
    ... I failed to take into account files with less than (n-1) bits. ... Prev by Date: ...
    (sci.math)
  • Re: Compact connected Hausdorff
    ... > of U are also open in X (a relatively open subset of an open set is ... > What am I missing? ... Prev by Date: ...
    (sci.math)
  • Re: Rational and irrational numbers
    ... yourself, and where possible, go for depth of understanding -- after ... all, you're deepkdeb. ... Prev by Date: ...
    (sci.math)
  • Re: Random choice of numbers
    ... quasi writes: ... For n in N, n> 2, let pbe the probability that if n numbers are ... Prove or disprove: pis rational, ... Of course if n-1 is divisible by k, ais divisible by n^k - ^k. ...
    (sci.math)
  • Re: Not sure about interpretation of this set notation
    ... and k for an element of A. I would change the letters for clarity: ... Assuming division by 2 makes sense, here's another way to express X: ... Prev by Date: ...
    (sci.math)