Re: More of an Algorithems question

On Fri, 18 Nov 2005 00:11:37 GMT, LC Killingbeck
<NOTlynn.killingbeck@xxxxxxxxxxxxxxxx> wrote:

>quasi <quasi@xxxxxxxx> wrote in
>news:t7ipn118hl17f4p3sbtetcnsqv7jj250f3@xxxxxxx:
>
>> 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
>
>Isn't "less than half" even stronger as "none"? A 1-bit file cannot be
>compressed, since the only smaller file (0 bits) is needed to
>represent itself. Then a 2-bit file cannot be compressed, since all of
>the 0- and 1-bit files are needed to represent themselves. Induction.

Yes, I saw that the two 1-bit files were a problem as far compression,
but I was assuming that a compression scheme is allowed to compress
some files while potentially expanding others. Thus, a compression
scheme could map some files of <=n bits to more than n bits, and, as
you point out, something like that is necessary. If anything gets
smaller, something has to get bigger -- I guess it's a kind of
conservation law for bits.

quasi
.

Relevant Pages

  • Re: More of an Algorithems question
    ... > In any lossless compression scheme, less than half of the files with n ... leaving 9 orphans (or, pigeons without unoccupied pigeon holes). ...
    (sci.math)
  • Re: More of an Algorithems question
    ... >> Yes, I saw that the two 1-bit files were a problem as far compression, ... Yes, as you suggest, any permutation on the set of n-or-less bit files ... can be used to define a compression scheme. ...
    (sci.math)
  • Re: how do I do DCT on a 100x100 image?
    ... huhua wrote: ... lower frequencies less and usually leaves the DC element alone). ... compression techniques which are usually lossless. ... typical compression scheme you will get much greater data ...
    (comp.dsp)
  • Re: Optimize file
    ... not supported (has to do with compression scheme used LZW ... apps I have on my PPC. ... support for them was simply dropped from PPC image viewers ...
    (microsoft.public.pocketpc)
  • Re: compression API available in Java & C++?
    ... > I'm looking for a compression algorithm that works better than gzip ... No general-purpose compression scheme is going to be very much help for such ... The gzip compression scheme can be pre-trained ...
    (comp.lang.java.programmer)