No, mmathias, there won''t always be a function to represent a sample of any given data. This should be clear after any course in calculus or statistics.

Dang! People sure have been busy. Now for my points.

1) This thread could use some compression!

Mike Roberts
aka milo
mlbobs@telocity.com

quote: Original post by LackOfKnack

You''re saying no bit pattern of any size is ever repeated more than any other?

Not exactly what I am saying. What I am saying is that they are not repeated enough to see any gain. Not even an insignificant gain. No gain at all. This has been proven, but it is long an complicated. Not to sound arrogant, but you need a strong discrete math backgound for it to make any sense (I don''t completely understand it), but you can find it in any standard algorithm textbook.

quote:

No, it''s a bunch of algorithms. ?

No, it''s called a meta-algorithm, and it is still one algorithm, even if it incorporates many different algorithms. I don''t see how you can dispute this, it''s fairly obvious.

quote:
How do you know this? Does this not depend on the particular file?

I am talking here about files that have already been compressed by an already known and tried algorithm. Obviously there are many files of length n that can be compressed, but for everyone that you can compress, there is one that will be expanded. This is not based on something that ''sounds logical to me'', it''s based on mathematical fact.

quote:
Okay, that''s correct that you don''t give birth to a seed that can grow into something, but that''s where it differs: Within say, a human, you have the potential once they are born to give birth to many more unique humans. So the analogy works there.

I still don''t understand where this anolgy comes in. If anyone understands where this is coming from, say something.

quote:
For the parts we agree on, you have used mathematics and such. For the parts we disagree on, we have both been putting out statements that seem logical to ourselves but have no backup.

No. Here is the difference. I have the backup of math and thousands of people (myself included) that have actually worked with compression algorithms.
You have a few wild, unoriginal, shown false ideas that at first glance seem logical. If you tried to actually implement them, you would quickly see the flaws.

quote:
Why not? It could. But I see your point. But it''s still possible.

I don''t completely agree with what I said earlier BUT when he makes wild claims and, in the same post, asks about the simplist algorithms, it really makes it sound like he is talking BS.

quote:
deathlok: You''ve proven .9 repeating equals 1, but it doesn''t really, right? Very close, but not exactly.

You contradicted yourself in these two sentences. How can it be proved that .999... equals 1, but not exactly?

quote:
osmanb: But you could compress _most_ of them, you''re saying?

I belive he is saying thta for every file that can be compressed, there is at least one that can''t. And on average, over all files of the same length, there is no gain.
Here is my main point. You have no clue as to what you are actually talking about, just a wild idea that at first glance sounds logical. It really pisses me off when people talk out of their ass about something they obviously have really know nothing about. At very least, go implement huffman encoding, and if you still think that your idea has some merit, then come back and talk about it.


Mike

First off, I''d like to apologize. I was the anonymous poster a bunch of messages ago that flamed EB; I lost my cool.

Now on to the interesting stuff. All this talk about mathematical impossibilities really makes me cringe. I agree with Gladiator that we only think something is impossible because we have defined it within our understanding of our environment. Back to the flat world example, people said it was impossible for the earth to be round because you would fall off the sides or bottom. They had no grasp of gravity etc. Just because people "proved" it impossible, didn''t make it so. Correct me if I''m wrong but I also believe that time travel was mathematically impossible until Einstein''s theory of relativity said that it was indeed possible. Something moving faster than the speed of light was also something that was "proven" mathematically impossible, but again Einstein "proved" it possible.

On and on throughout history "impossibilities" have been proven wrong (though I can''t think of any more examples at the moment), so how can someone say something is impossible. It may indeed be impossible, but I doubt our science is sophisticated enough in order to do so. It can "prove" or "disprove" something within our current understanding of things but that is all.

I''m sure flight was accepted as impossible before the wright brothers made their flight (don''t quote me on this but I''m sure someone proved that it was impossible mathematically as well).

Keiren, or whoever started this post, may be right or wrong, but to outright state that what he did was impossible because it was mathematically impossible is ludicrous. Maybe he found a way to open a portal to another dimension and thus store most of that file in this other dimension with only a pointer into that other dimension, thus achieving his compression claims. Its not probable, but you can''t say its impossible. And before someone replies saying this isn''t really compression, it was just an example, not to be taken seriously.

Bret.

The joys of Magic Function Theory.
Here is why, in gory detail, magic function cannot work
(Please note, for a second I couldn't think of why this wouldn't work, so I attempted to "implement" it and see what went wrong. This isn't a mathematical proof, but rather an attempt to prove that it can work, then realizing the reasons it can't):

Let's start with the assumption that I want to compress a file of at most 128KB (2^20 bits) using a magic function compressor (meaning one that uses a function to recreate the data, thus saving "gobs" of space since we only need to store an index to which function recreates each file). Now, the first problem we run into is "Wait a minute. To index each of the 2^(2^20) functions we're using would require (drum roll, please) 2^20 bits, which is no less than we started with...and if we want to compress files _smaller_ than 2^20 bits, we'll require 20 extra bits to contain the length of the file.

But wait! What if we stored the length first (20 bits) then ONLY stored the rightmost bits past the first '1' bit? (thus 0000 0001 0001 1010 becomes 100011010) That could save us a ton of bits, right?

Then we could theoretically have compression down to 20 bits! Sure, our max would be (2^20)+20, but our average would be very low ((20+(2^20)+20)/2)! Hey, this fits into Information Theory, too, since we _do_ have certain patterns that get bigger instead of smaller, right?

Kind of...there's a few things wrong with this approach, first off: What if all the functions we use (in practice) start with bit 1? oops. Then every output will be larger than the original file. Well, that's easy to fix, just optimize the most common function identifiers to set the first 21 bits to 0, right? Then we'll always get savings of at least 1 bit! Hurrah! Have we done it?

Even optimized, our program will only shrink 2^((2^20)-21) files...and then, half of them will only shrink by 1 bit, half of the remaining by 2 bits, half of that remaning by 3 bits, etc...but a vast vast majority of the files (2^(2^20))-(2^(2^20)-21) will still get bigger.

And don't forget that we can't have 1-7 bit bytes, all bytes with fewer than 8 bits will need to be rounded up, right? Aah, even less savings now, since any file that shrinks by less than the # of bits required to hit the next byte will reexpand to a full byte. So only a tiny fraction of the files will shrink even 1 byte, only 1/8th of those will shrink 2 bytes, and 1/8th of those, etc...

"But...but...I'm still sure it can work! Just let me run my magic function creator..."
Okay, so we run the magic function creator...Now, it creates 2^(2^20) unique functions that give us the original 2^(2^20) bit patterns...Now, of course these functions will have to be at least 2^20 bits long each (or they wouldn't be unique themselves)...for now, we'll pretend we have a magic operating system that will run anywaything, so OKAY! We have our 2^20 bit long functions, each describing PERFECTLY a 128k output (Of course, do I even need to mention that these functions match 1 to 1 to each output? Heck, they're just the original bit strings!)...now let's store them on our hard disk...*makes HD grinding noises* What's the estimated size of our compressor? Only: 2^(2^20) * 2^20 bits! errr. ONLY???? Now, I can't confirm this (My calculator can't handle such big numbers), but I was told that this equals somewhere in the realm of (oh, I dunno) 50 to 500 billion gigs. Hmm. My computer can store 96 gigs...that's nowhere near even my lower bound guess of 50 billion...

I don't know about you, but I don't how I'd store this magic function compressor...maybe on dvd?

Of course, this doesn't even take into consideration the amount of time it would take to build the functions...I imagine that would be reasonably significant in and of itself.

I guess you could argue that someday we'll have the space to store all of these...but remember that the compressor offered no savings for probably 99% of the files and only minor minor savings for the ones that did compress...and if you have a 50 billion gig hd and are worrying about saving 8 bits out of your 128k files...well... @_@

If I made any mistakes, feel free to point 'em out, but remember I wrote this with the best intentions in mind...

Deathy


Edited by - deathlok on 4/19/00 12:25:41 PM

OK, I promised myself I wouldn't get involved, but...DAMN!
NOW INSTEAD OF NOT READING THIS -> READ IT

Instead of boring you to death with complicated stuff, I will make short, sweet (maybe) and simple.

You can't cram 3 bowling balls into a container that was designed to hold 2.5 (2 and a half) without destroying part of the third, after wich, you couldn't bowl with 3 balls 'cuz the third was cut in half. Same principle with data: you can't return a MP3 to a .WAV file because part of it was destroyed when it was compressed. So you can't fit a 100Mb of random data into something that was meant to hold 100Kb. If you still think its possible, try fitting 2 people into a space suit without cutting one in half.
'Nuff said.

Why am I talking? No one will read this

Edited by - Blah! on 4/19/00 12:32:34 PM

Oh my goodness, they''re reproducing...

quote: Original post by Hitman
Now on to the interesting stuff. All this talk about mathematical impossibilities really makes me cringe. I agree with Gladiator that we only think something is impossible because we have defined it within our understanding of our environment.

I agree. Maybe we''re being too hard on those who think this magical compression can exist. I mean, all we have to do is redefine math to say 256 <= 254, or compress our data via a portal to another dimension! Of course, it''s so obvious now! How silly of me. I mean, *current* mathematics says it''s impossible, but since when do computers use current mathematics?

aig

quote: Original post by An Irritable Gent

I mean, all we have to do is redefine math to say 256 <= 254, or compress our data via a portal to another dimension!
aig

*grins* I thought of that, too, but in the end that''s like "Compressing" a file by moving it to another computer. Just because it''s not on your HD doesn''t mean that it''s any smaller...and sticking it in another dimension, in the end, just annoys the natives.

Deathy

BTW Hitman: Einstein's Theory of General Relativity doesn't prove time travel to be possible -> it only theorized on it.

To travel forward in time significantly (pardon my bad english ), one would have to go very very far in space very very quickly, then return. Since going in space quickly enough to achieve time travel would require light- speed or faster, time travel is indeed a thing that math and physics proved impossible. Einstein himself said that achieving light-speed is impossible, so traveling in time to get a significant result would be impossible.
So bottom line is time travel is impossible. Next time, read the whole paper, not just the first 2 chapters .

But since you don't believe anything is impossible, ignore this post and go back to stuffing 3 tons of concrete into a 2 oz. container.

Edited by - Blah! on 4/19/00 12:53:03 PM

AIG responded
-- Oh my goodness, they''re reproducing...

--I agree. Maybe we''re being too hard on those who think
--this magical compression can exist. I mean, all we have
--to do is redefine math to say 256 <= 254, or compress
--our data via a portal to another dimension! Of course,
--it''s so obvious now! How silly of me. I mean, *current*
--mathematics says it''s impossible, but since when do
--computers use current mathematics?

--aig

The argument here was that someone said they found a way to do something and lots of people responded saying that it was impossible because blah, blah, blah.

Are you really so arrogant to think that you know everything there is to know about everything in order to say something is impossible? If you are, then I''m glad I don''t know you personally.

Bret.