next »

[Pineapple]

It's not necessarily a game, but indie developers can make useful software, too.

I've come up with an idea for a compression algorithm that would certainly require tremendous computing power to initially compress, but would require very little to decompress.

How would it work?

<snip>

[muku]

I'm sorry, but the amount of bits you can compress a file into is bounded by the entropy inherent in the file (Shannon's coding theorem). This is a theoretical bound; my understanding is that there are some compressions methods (the name escapes me at the moment) which get quite close to this limit, but they are very, very slow.

Anyway, the point is, you can't just make a compressed file arbitrarily short no matter how hard you try, nor can you make a file shorter and shorter by compressing it over and over.

[Theotherguy]

Yep, just about to post that. Many (in fact most) files are inherently incompressible beyond a very high limit, not for practical reasons, but for statistical ones.

However, as for your method being a valid and useful compression technique, it very may well be, except I think you underestimate the difficulty in finding such a random seed by any method other than "voodoo magic."

[Pineapple]

It works by <snip>

[muku]

It works by arranging the data into something that can be compressed, not by working with the data handed to it.

I'd argue that that's conceptually the same thing.

Shannon's Law can be discarded because we are only copressing one type of file

It can never be discarded. If your file only contains very few different values, then its entropy will be accordingly low, and so of course you can fit more of it into each byte. The theorem still holds.

Anyway, how will you find that seed? You haven't really talked about this so far.

[Pineapple]

At the moment it uses a brute-force method, but <snip>

[Zaratustra]

I'm honestly stumped as to what commonly used file format would be easier to compress if it was scrambled, even if you searched all possibilities.

I suggest you test your theory with a couple of sample files before trying to make an actual application.

[Pineapple]

The point is to <snip>

[Pineapple]

Hmm, my decompression algorithm reproduced a file of the same size, but the contents are not identical. Investigating.

<snip>

[Pineapple]

Augh, it keeps screwing up on the uncompressed bits.

[BorisTheBrave]

Your not doing yourself any favours posting every little setback on the forum. If everyone else is like me, we're only waiting for the final one where you discover it won't work at all.

Rather than appeal to technical reason, which already seems to have failed, I shall appeal to arrogance - do you really think it is likely that you have an algorithm better than what decades of research has produced, and that manages to circumvent fundamental theorems, while also being general purpose enough to apply to any data?

[Glaiel-Gamer]

I have an ultimate compression algorithm. Every file in the world is stored on a remote server and indexed by a unique 16 byte integer.

The compression algorithm then looks up the file on the megaserver and reduces the file to its index.
Considering there's way less than 1.16x10^77 files in the world (and won't ever really get close to that), this algorithm will compress every single file people use into 16 bytes.


granted, you need quite a hefty server farm to be able to do this

[BorisTheBrave]

You make it sound stupid, but that one is a legit technique. See data de duplication or content addressable storage.

My brother and I had a wicked compression technique for those with download limits, but no upload limits. You upload every single possible file in sequence, and the server sends a "1" back when you uploaded the one corresponding to what you download.

[Pineapple]

Yeah, I'm telling you my progress, but why not?

And I don't understand what's so stupid about <snip>

[Glaiel-Gamer]

I've already got something that works extraordinarily better (though quite a bit slower) than any other compression techniques widely used.

ya but this means nothing till you can decompress it

i have an algorithm that compresses every file into 1 bit, but unfortunately the decompressor for that still doesn't work

[Pineapple]

Are you mocking me? Get out of my thread.

[Zaratustra]

well mine compresses the file to 0 bits that's an improvement of infinity percent

[Pineapple]

The problem isn't even with decompressing the compressed data, it's with copying the uncompressed parts.

[BorisTheBrave]

It's because you don't claim anything about the data you are compressing. That means there is no redundant data. You cannot get around this fact by attempting to reshuffle it. It is infact a classic of novice CS students to claim better compression, I personally have seen it on forums several times before. Some scepticism is fair in such circumstances, no? Not even sure why I'm wasting the time to post, it seems others have reached the taunting phase already.

If you want me to attack your method specifically, I think you've underestimated how many possible permutations of 256 nibbles there are, and now few of them will give something RLE can work with. I suspect frequenly you could exhaust all 32-bit seeds and not find a single one that RLE would give a smaller file with. And that's with the computation time of 2 billion seeds, so don't think you can just have a larger seed space would help.

All your examples are completely messed up to. It's hardly surprising your run length encoded output is shorter - the input contains only 3 characters, but you've allowed at least 10 for the output, to write 0-9. Simply reading one number as base 3 and writing in base 10 would give equally good, if not better, output. If this were binary, then both input and output would have the same number of characters, and your examples would look much less peachy, even ignoring the aformentioned seed issue.

Given your other thread, I'm assuming that you are testing this with some image data, rather than random data that you have been implying this technique is meant for. That would be my guess as to why you have observed compression. I will be more inclined to believe you when you have a compressor and a decompressor which work, and the same file compresses to more with zlib.


You shouldn't be listing your progress because it is boring. "I found a bug... oh I fixed it". Yawn. We get it, coding is an exercise in writing a series of bugs, and then polishing it into a program.

[Pineapple]

This is something completely different, and I have already thought about your points addressed.

<snip>