Read why it is impossible to compress random data. Many reasons are given, as well as the problems with claims otherwise:

http://www.faqs.org/faqs/compression-faq/part1/section-8.html

aig

GA, yeah, osman was making fun...so am I

oh, i was just posting info about sorting to clarify that it was impossible, cuz someone else didn''t seem sure...whatever

-J

don''t try to be funny... i''m talking some serious shit here...

ziplux: No, he said it somewhere:

quote: If I run my bit-based huffman on them (after bit-reordering), in thinks it''s 16-bit data. Although this process actually makes the file larger, if I run it again on the data it says it''s 4-bit data and compresses it smaller than the original data. Run it again, 16-bit and it enlarges. Again, 4-bit and it''s smaller again. I found you can actually do this about 256 times before it stops getting smaller. I WILL post a demo of this bit-based huffman; and you can watch it repeatedly compress the data. I''m coding the demo now.

AP and fel: Thank you, I agree very wholeheartedly.

deathlok: Yeah, the round earth thing is a poor analogy. But, there have been other incidences closer to this one in which math and science are shaken. As someone said, it has been proven using standard mathematics that 1 = .9999999.

ga: See above, plus, if you consider that bit string you posted earlier to be random, I was able to compress it by 6 bits on paper at a byte size of 5 and 2 bits at a size of 4. I haven''t had time yet to try other sizes. If you had a larger file to work with, the savings would surely outweigh the measly header file.

Also, that 16-4-16 thing wasn''t my idea or even my argument. I even said I was more skeptical of the 16-4 than the original.

osmanb: If his program fails I''ll take up the job as soon as I can. This interests me much now.

Vetinari: No, you couldn''t. You''d always have a header file of some sort, and depending on the method, you''d always need a seed to start the decompression from. So you _can''t_ compress any file of any size, because once you get down to a certain size, your header is bigger than the savings themselves. But who''d need to compress 15 bytes or whatever anyway? When you''re down that low, it''s impractical. So _practically_ any file could be compressed, especially if you had an array of scrambling and compression methods at your disposal.

jritts, on your takeback post: I agree. But he said right off the bat he didn''t care, so people should''ve just posted the resources. But they didn''t, and I disagreed with them, so I started arguing with them.


Lack

Christianity, Creation, metric, Dvorak, and BeOS for all!

Vetinari, which mathematically proven things had been proven wrong later??? Then there was no matemathically correct proof and nobody realized it?

Visit our homepage: www.rarebyte.de.st

GA

Don''t try to prove your points whatever they are... Just confess that everything (no, i didn''t say possible) can be taken to a point where it works out as you want it to... even though we don''t know how to make it work, that doesn''t mean it''s impossible. you just don''t know how to do it.. as times passes by, and our society evolves greatly, what you wen''re able to accomplish might be done in the next century or so... so don''t say it''s impossible... just say that you don''t know how to get it to work... hey.. im confusing myself now.. arggh... where''s the aspirin... i''ve got a headache.. do you think they sell aspirin at Domminick''s? ouch... don''t push me... i''ll be out in a second...

Was trying to see how far osmanb was willing to take the joke... you guys wrecked it *pout*

Perfect compression: C:\format C

Comment on the earlier fruit and carbon comments: Compressing carbon gives you a diamond, which is cool. Compressing an apple gives you applesauce, which is nasty. Neither of them are reversible processes...

-fel



Edited by - felisandria on 4/18/00 4:15:37 PM

Glad-iator, the problem is *today* it IS understood why random data can''t compress. Read http://www.faqs.org/faqs/compression-faq/part1/section-8.html.

From the page (read it slowly, and it will make sense):

"Theorem:

No program can compress without loss *all* files of size >= N bits, for any given integer N >= 0.

Proof:
Assume that the program can compress without loss all files of size >= N bits. Compress with this program all the 2^N files which have exactly N bits. All compressed files have at most N-1 bits, so there are at most (2^N)-1 different compressed files [2^(N-1) files of size N-1, 2^(N-2) of size N-2, and so on, down to 1 file of size 0]. So at least two different input files must compress to the same output file. Hence the compression program cannot be lossless.

The proof is called the "counting argument". It uses the so-called pigeon-hole principle: you can''t put 16 pigeons into 15 holes without using one of the holes twice."

In other words, if an algorithm could compress all combinations of a file of any given size, at least two of those combinations MUST compress to the exact same compressed file - thus upon decompression, it cannot be known which of the two (or more) original files the compressed file should decompress to. (ie. two of the pigeons (original files) went through the same hole (compressed representation)).

Think about this simple example: you have 8 bits - that allows you 256 combinations. Can you compress *all* 256 combinations to 7 bits or less, and have all 256 of the compressions be unique? Nope - MATHEMATICALLY IMPOSSIBLE.

aig

Lack, maybe my string wasn''t random, but the whole zip file would be. 6 bits are just 3/40, have you added the header size to your compressed string length? You want to say that Veterinari''s proof is wrong?? It isn''t, because the header is part of the compressed file. I think enough proofs were given that you can''t compress every file.
Gladiator, you think it''s possible to find a highest prim number but we don''t know how to find it??

Visit our homepage: www.rarebyte.de.st

GA