5 ms·

If you just have to decompress a single file, I don't see why this problem is impossible since you can tune your decompressor to that file. For example, files

by ealloc 14y ago

If you just have to decompress a single file, I don't see why this problem is impossible since you can tune your decompressor to that file. For example, files containing the digits of pi or e will have a uniform distribution of bytes (and are therefore incompressible by exploiting redundancy) but it is very easy to write a "decompressor" for them as there is a simple algorithm to obtain these numbers. Is there a simple algorithm for every possible number? Because then it just becomes a question of finding the algorithm that generates that number. My intuition tells me "yes" but that it may be very hard to find it. Plus, you don't need to find an algorithm for the whole file, just some subsection of it.

TwoBit 14y ago
It may be that finding that algorithm is theoretically possible but impractical. I'm going to guess that for a random bit stream that it's impractical and would require huge computing resources, cost, and time.
romaniv 14y ago
Think about it as identifying patterns. You can always remove chunks of the original file and then simply re-add them with instruction as following: "Add pattern 23989898989 to 234d, 387th and 1028th point of this file." If your pattern is big relative to the file size and repeats often, you will save space. However, if the file is truly random, the larger the pattern, the less frequently you will see it. Very large patterns will be seen only once. Very small patterns will require more information to encode their place than you're saving by removing them from the file.
- ealloc 14y ago
  Yes, I see why a repetition/pattern approach wouldn't work, but I'm proposing something else: That the file may be generated by an algorithm, in the way one generates the digits of pi using an algorithm. It's similar to how if I suspected he had generated his random file with a mersenne twister I could simply guess his seed and reproduce the file from it. (Though, I realize now this is an NP-hard problem)
mistercow 14y ago
>If you just have to decompress a single file, I don't see why this problem is impossible since you can tune your decompressor to that file. It isn't guaranteed to be impossible; it's just very, very likely to be impossible.

by ealloc 14y ago

TwoBit 14y ago

It may be that finding that algorithm is theoretically possible but impractical. I'm going to guess that for a random bit stream that it's impractical and would require huge computing resources, cost, and time.

romaniv 14y ago

Think about it as identifying patterns. You can always remove chunks of the original file and then simply re-add them with instruction as following: "Add pattern 23989898989 to 234d, 387th and 1028th point of this file." If your pattern is big relative to the file size and repeats often, you will save space. However, if the file is truly random, the larger the pattern, the less frequently you will see it. Very large patterns will be seen only once. Very small patterns will require more information to encode their place than you're saving by removing them from the file.

ealloc 14y ago
Yes, I see why a repetition/pattern approach wouldn't work, but I'm proposing something else: That the file may be generated by an algorithm, in the way one generates the digits of pi using an algorithm. It's similar to how if I suspected he had generated his random file with a mersenne twister I could simply guess his seed and reproduce the file from it. (Though, I realize now this is an NP-hard problem)

mistercow 14y ago

>If you just have to decompress a single file, I don't see why this problem is impossible since you can tune your decompressor to that file. It isn't guaranteed to be impossible; it's just very, very likely to be impossible.