5 ms·

A ridiculous patent for arbitrary compression

50 points by seagaia 15y ago

pwg 15y ago
Note that while it does not change the level of ridiculousness, the patent mentioned was granted on Jul. 2, 1996, so it is now almost 15.5 years old.
- mcherm 15y ago
  That means that in another 4.5 years EVERYONE will be allowed to use this superior compression algorithm without having to pay royalties.
  - compman775 15y ago
    Should be industry changing. I have never had access to a program implementing this algorithm. This patent might have something to do with it. </sarcasm>
amadvance 15y ago
Ridiculous is not the patent, but the patent system that accepted it.
- deleted 15y ago
  [deleted]
- seagaia 15y ago
  True. It's also a bit frustrating, reading other stuff on gzip (from where I found this), that the author of gzip wasn't able to make it run as fast as possible because of patented algorithms. Sort of disappointing.
DarkShikari 15y ago
Actually, it is possible to write a compression program that can compress any file, even random data, by one byte: http://cs.fit.edu/~mmahoney/compression/barf.html http://cs.fit.edu/~mmahoney/compression/barf.html (See if you can spot the evil trick.)
- deleted 15y ago
  [deleted]
  - deleted 15y ago
    [deleted]
- bane 15y ago
  My favorite is a lossy compression method that results in any file(regardless of entropy) compressing down to 1 byte. Just throw out the rest of the file after the first byte.
- amalcon 15y ago
  I was about to reply to this with "My favorite fake compression scheme is..." ...but it turned out to be this.
- deleted 15y ago
  [deleted]
- StavrosK 15y ago
  Haha, that's clever! It works, too.
- inportb 15y ago
  Very nice ;D
SagelyGuru 15y ago
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.
danbmil99 15y ago
> 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. Beautiful.
gregschlom 15y ago
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. The hard part was finding a way to store the remainder of the division if the data was odd...
saulrh 15y ago
Amusingly, the comp.compression FAQ that this page cites includes a discussion of this very patent from way back when it was submitted. Go to http://www.faqs.org/faqs/compression-faq/part1/section-8.html http://www.faqs.org/faqs/compression-faq/part1/section-8.htm... and grep for "5,533,051".
thoughtsimple 15y ago
Well at least we know that there was no valid prior art. So at least that part of the patent review worked correctly.
StavrosK 15y ago
What kind of a genius does it take to realize that you can't represent two bits by one bit?
gregable 15y ago
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. Uncompressing simply requires knowing how many compression steps I took. :)
westbywest 15y ago
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.) 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= http://www.itwire.com/opinion-and-analysis/cornered/41010-th...
DanBC 15y ago
Here's a nice write-up of an attempt at the comp.compression challenge. (http://www.patrickcraig.co.uk/other/compression.htm http://www.patrickcraig.co.uk/other/compression.htm) EDIT: (http://www.maximumcompression.com/compression_fun.php http://www.maximumcompression.com/compression_fun.php) > 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 :-)
DanBC 15y ago
The Hutter Prize (http://prize.hutter1.net/ http://prize.hutter1.net/) claims that compression is related to intelligence, and that good compression is advancing towards AI. I'm not so sure, but it leads to interesting ideas. 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.)

50 points by seagaia 15y ago

pwg 15y ago

Note that while it does not change the level of ridiculousness, the patent mentioned was granted on Jul. 2, 1996, so it is now almost 15.5 years old.

mcherm 15y ago
That means that in another 4.5 years EVERYONE will be allowed to use this superior compression algorithm without having to pay royalties.
- compman775 15y ago
  Should be industry changing. I have never had access to a program implementing this algorithm. This patent might have something to do with it. </sarcasm>

amadvance 15y ago

Ridiculous is not the patent, but the patent system that accepted it.

deleted 15y ago
[deleted]
seagaia 15y ago
True. It's also a bit frustrating, reading other stuff on gzip (from where I found this), that the author of gzip wasn't able to make it run as fast as possible because of patented algorithms. Sort of disappointing.

DarkShikari 15y ago

Actually, it is possible to write a compression program that can compress any file, even random data, by one byte: http://cs.fit.edu/~mmahoney/compression/barf.html http://cs.fit.edu/~mmahoney/compression/barf.html (See if you can spot the evil trick.)

deleted 15y ago
[deleted]
- deleted 15y ago
  [deleted]
bane 15y ago
My favorite is a lossy compression method that results in any file(regardless of entropy) compressing down to 1 byte. Just throw out the rest of the file after the first byte.
amalcon 15y ago
I was about to reply to this with "My favorite fake compression scheme is..." ...but it turned out to be this.
deleted 15y ago
[deleted]
StavrosK 15y ago
Haha, that's clever! It works, too.
inportb 15y ago
Very nice ;D

SagelyGuru 15y ago

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.

danbmil99 15y ago

> 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. Beautiful.

gregschlom 15y ago

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. The hard part was finding a way to store the remainder of the division if the data was odd...

saulrh 15y ago

Amusingly, the comp.compression FAQ that this page cites includes a discussion of this very patent from way back when it was submitted. Go to http://www.faqs.org/faqs/compression-faq/part1/section-8.html http://www.faqs.org/faqs/compression-faq/part1/section-8.htm... and grep for "5,533,051".

thoughtsimple 15y ago

Well at least we know that there was no valid prior art. So at least that part of the patent review worked correctly.

StavrosK 15y ago

What kind of a genius does it take to realize that you can't represent two bits by one bit?

gregable 15y ago

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. Uncompressing simply requires knowing how many compression steps I took. :)

westbywest 15y ago

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.) 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= http://www.itwire.com/opinion-and-analysis/cornered/41010-th...

DanBC 15y ago

Here's a nice write-up of an attempt at the comp.compression challenge. (http://www.patrickcraig.co.uk/other/compression.htm http://www.patrickcraig.co.uk/other/compression.htm) EDIT: (http://www.maximumcompression.com/compression_fun.php http://www.maximumcompression.com/compression_fun.php) > 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 :-)

DanBC 15y ago

The Hutter Prize (http://prize.hutter1.net/ http://prize.hutter1.net/) claims that compression is related to intelligence, and that good compression is advancing towards AI. I'm not so sure, but it leads to interesting ideas. 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.)