Re: Fixpoint for LZH
From: David C. Ullrich (ullrich_at_math.okstate.edu)
Date: 07/19/04
- Next message: David C. Ullrich: "Re: PBZ: Short Proof of Fermat's Last Theorem"
- Previous message: Adam: "~ Sets of functions 1"
- In reply to: Dik T. Winter: "Re: Fixpoint for LZH"
- Next in thread: Dik T. Winter: "Re: Fixpoint for LZH"
- Reply: Dik T. Winter: "Re: Fixpoint for LZH"
- Messages sorted by: [ date ] [ thread ]
Date: Mon, 19 Jul 2004 07:14:14 -0500
On Mon, 19 Jul 2004 01:14:49 GMT, "Dik T. Winter" <Dik.Winter@cwi.nl>
wrote:
>In article <1090049632.322988@athnrd02.forthnet.gr> morpheus@olympus.mons writes:
> > Dik T. Winter wrote:
> > [snip]
> > > > I stand corrected. I was rather using "strict contraction" in the sense
> > > > of the previous article, but your and David's points still stand, even
> > > > under this definition: size(f(file))> size(file) =/=> f does not have
> > > > any fixed points.
> > >
> > > But you have not actually shown that size(f(file)) never equals size(file).
> >
> > Even if f is such that size(f(file))=size(file), this says nothing about
> > the existence of a fixed point of f.
>
>Yup, exactly what I said below.
>
> > > With all kinds of schemes that may change filesize, and in some cases leave
> > > it unchanged, it is possible that a fixed point does exist.
> >
> > It is possible that several schemes may have a fixed point, but it
> > appears to me as though a filesize change doesn't imply anything about
> > the existence of said point.
>
>Where do I say that there is an implication? I only say that it is
>possible that such does exist!
>
> > In that sense, zip appears to be fundamentally different from Stuffit
> > for example, in that Stuffit for Macs if memory serves right, never
> > increased file size. It's been a while since I was using a Mac, so my
> > memory may be failing me on this.
>
>Stuffit will never increase filesize indeed.
But that's impossible. At least it's impossible _if_ there exists
a way to decompress any compressed file, and it does in fact
decrease some file sizes. This is a simple counting argument.
>But that is a program that
>uses quite a few different compression formats and if any of them fail
>to make the file shorter, it will just produce the original.
And then how does it know that when it tries to decompress the
file it should leave it alone? The fact that the file was not
changed must be recorded somewhere...
(Maybe it literally does nothing at all, like if it compresses
file.ext it writes file.stuffed, while if it decides not to
compress the file it just leaves file.ext alone, without
writing another file? If so it seems like that can't work,
because if the _original_ file was named file.stuffed then
after it leaves the file alone the decompressor will
think that it was compressed...
Just speculating on how it could appear to do what you
say...
Ok, if it leaves the file alone maybe it outputs a
message to the user saying that that's what it did.
In that case, if the original was file.stuffed, the
user has to _remember_ that that's not a compressed
file - that's a few bits that the routine writes
to the user's brain.)
???
>The point
>was *not* whether a particular program has a fixed point (I know some
>for Stuffit), but whether a compression scheme has a fixed point.
************************
David C. Ullrich
- Next message: David C. Ullrich: "Re: PBZ: Short Proof of Fermat's Last Theorem"
- Previous message: Adam: "~ Sets of functions 1"
- In reply to: Dik T. Winter: "Re: Fixpoint for LZH"
- Next in thread: Dik T. Winter: "Re: Fixpoint for LZH"
- Reply: Dik T. Winter: "Re: Fixpoint for LZH"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
