Re: More of an Algorithems question


s...@xxxxxxxxxxxxxx wrote:
> Filter wrote:
> > How can I proove that no Algorithm can compress every file of length
> > 10^6?
>
> This is rather simple. Let's assume by length you mean bits--not that
> it really matters, but it makes things easier. A compressed file would
> be smaller than the orginal. So between 1 and 10^6-1 bits. Now how
> many unique files are there with between 1 and 10^6-1 bits? Answer:
> less than the number of unqiue files with 10^6.

Nice. Basically a pigeonhole principle argument.

So what this means is that no LOSSLESS compression scheme
can compress all files of length N bits into files of length N-1
or less.

- Randy

.

Relevant Pages

  • Re: GetCurrentPosition in a graph that does not accept seeking
    ... Some times ago I wrote a simple filter whose task was to let me to check ... The graph alone did not accept seeking (I only got 0 as ... Now I want to reuse the graph to compress into ogg through Vorbis Encoder. ... you seem to overwrite LastSampleTimeEnd ...
    (microsoft.public.win32.programmer.directx.audio)
  • Re: More of an Algorithems question
    ... >How can I proove that no Algorithm can compress every file of length ... Prev by Date: ...
    (sci.math)
  • GetCurrentPosition in a graph that does not accept seeking
    ... Some times ago I wrote a simple filter whose task was to let me to check ... the progress in a graph that compressed a generic audio file to mp3 through ... The graph alone did not accept seeking (I only got 0 as ... Now I want to reuse the graph to compress into ogg through Vorbis Encoder. ...
    (microsoft.public.win32.programmer.directx.audio)
  • Re: More of an Algorithems question
    ... Filter wrote: ... > How can I proove that no Algorithm can compress every file of length ...
    (sci.math)
  • Re: More of an Algorithems question
    ... >> How can I proove that no Algorithm can compress every file of length ... Prev by Date: ...
    (sci.math)