Actually, it is possible to write a compression program that can compress any file, even random data, by one byte: <a href="http://cs.fit.edu/~mmahoney/compression/barf.html" rel="nofollow">http://cs.fit.edu/~mmahoney/compression/barf.html</a><p><i>(See if you can spot the evil trick.)</i>
When I was 15 I spent a lot of time working on my own compression algorithm... The idea was to treat the data as one giant integer and divide it by 2 recursively, each time reducing the size of the data by one bit.<p>The hard part was finding a way to store the remainder of the division if the data was odd...
Amusingly, the comp.compression FAQ that this page cites includes a discussion of <i>this very patent</i> from way back when it was submitted. Go to <a href="http://www.faqs.org/faqs/compression-faq/part1/section-8.html" rel="nofollow">http://www.faqs.org/faqs/compression-faq/part1/section-8.htm...</a> and grep for "5,533,051".
This patent, and many other similar 'Intellectual Property Rights' are no doubt carefully entered on some accounts as real assets and then 'financialised', i.e. leveraged by a huge factor, borrowed against, turned into some kind of bonds and then the whole process repeated several times.
If I treat the file as one big integer and each pass through my compression simply decrements by one, eventually ill achieve one bit or zero bits depending on how you look at it.<p>Uncompressing simply requires knowing how many compression steps I took. :)
Here's a nice write-up of an attempt at the comp.compression challenge.<p>(<a href="http://www.patrickcraig.co.uk/other/compression.htm" rel="nofollow">http://www.patrickcraig.co.uk/other/compression.htm</a>)<p>EDIT:<p>(<a href="http://www.maximumcompression.com/compression_fun.php" rel="nofollow">http://www.maximumcompression.com/compression_fun.php</a>)<p>> <i>Does there exist a file which is extremely compressable by one archiver, but almost incompressable by another one?. I thought the answer was no, but Nimda Admin did sent me a file with these very strange properties. Please download and extract the rarred file strange.rar and try to compress it with (win)rar and (win)zip. You will see compression is RAR is extremely good, but compression in ZIP is almost 0%!. Just when you think you understand compression, someone sends you this file. Thanks Nimda :-) </i>
It looks like this was nearly contemporary with the Adams Platform video compression scam. (The scammer claimed he could transmit streaming, high definition video over a 56kbit dialup modem, and he somehow collected $27Million from gullible funders.)
<a href="http://www.itwire.com/opinion-and-analysis/cornered/41010-the-great-video-compression-scam-how-adam-clark-hoodwinked-tolly-group-and-many-more?tmpl=component&print=1&layout=default&page=" rel="nofollow">http://www.itwire.com/opinion-and-analysis/cornered/41010-th...</a>
The Hutter Prize (<a href="http://prize.hutter1.net/" rel="nofollow">http://prize.hutter1.net/</a>) claims that compression is related to intelligence, and that good compression is advancing towards AI.<p>I'm not so sure, but it leads to interesting ideas.<p>A genetic algorithm, taking sample chunks from the expanded data, creating dictionaries, compressing, and comparing scores might be a useful approach. (But a poor fit for the hutter prize's restrictions.)
> the direct bit encode method of the present invention is effective for reducing an input string by one bit regardless of the bit pattern of the input string.<p>Beautiful.