5 ms·

I guess I'm missing something here :-) ls -la /bin/tar 230464 Feb 25 2010 /bin/tar If tar can compress and decompress an arbitrary length file by more th

I guess I'm missing something here :-) ls -la /bin/tar 230464 Feb 25 2010 /bin/tar If tar can compress and decompress an arbitrary length file by more than 230464 bytes then doesn't it meet the challenge? Even if I've misunderstood, can anyone explain in plain english why this is a futile task?

praptak 14y ago
It's the contest organizer who gets to choose the file contents. Random noise is practically non-compressible. Btw, tar by itself does not compress at all.
- georgemcbay 14y ago
  "Random noise is practically non-compressible." It has to be actually random though. I was hoping the solution to this would be that Patrick had figured out that Mike used a specific random number generation engine with a specific seed and thus his decompressor was just a reversed engineered version of the original data generator and the file it "decompressed" was 0 bytes long.
  - juan_juarez 14y ago
    It says the source was random.org - probably the closest thing to 'true' random you're going to find freely available.
dsr_ 14y ago
You can't compress any arbitrary file, but there are lots of files you can compress. Proof for the first part (aka the Pigeonhole Principle): look at the universe of files that are 100 bits long. Apply your compressor to each one, so that you have reduced the length of each file to 99 bits. But the number of 99-bit long files is half the number of 100-bit long files, which means that for some of your compressed files, you can't tell exactly which 100-bit long file it corresponds to. Now, you can perform run length encoding on some files. That looks for runs of repeated bits, replaces them with a special marker, and writes a dictionary to translate the marker to the run. You can look for patterns. This will work... on some files. Not on all. A good compressor will try several different encoding schemes to do its work, and is going to succeed on files with embedded patterns. For instance, if the file is ASCII text, lots of bit patterns will never occur, and lots will occur repeatedly. If the file is English ASCII text, even more redundancy can be exploited. If the file is a structured data set, there's almost certainly a bunch of repeating patterns. But for purely random data, there won't be enough patterns repeated enough to exploit.
dubya 14y ago
Generally, you can't compress every n-bit file into an (n-1) bit program because there are twice as many n-bit files as (n-1) bit programs. So the average n-bit file is not compressible. On the other hand, there are clearly some files that are highly compressible, and many that are at least a little bit compressible, so it's not as impossible as the challenge issuer made it sound. I'm not sure how you'd calculate this, but if more than 1 in 50 random files were somewhat compressible then it would be a bad bet to issue.
bradleyjg 14y ago
Lossless compression works by exploiting redundancy in the data. If I want to compress a text file that contains the word 'uncharacteristically' 1000 times, I can simply replace ever occurrence with the a certain short unused byte sequence and record the mapping in the header. Similarly in an image file, if there is a block of 50 pixels that are all the same color, I can replace that block with a special byte sequence and map the coordinates and color in the header. But if I have truly random data, there are no patterns to exploit. The shortest means of representing random data - is the data itself. This is provable using information theory (which in a way is a branch of thermodynamics).
- lurker14 14y ago
  nitpick: There is no such thing as a truly random piece of data. "Truly random" is only meaningful in the limit as the file size goes to infinity. The string "000000" could be generated by a truly random process just as well as any any other.
  - bradleyjg 14y ago
    I meant Kolmogorov randomness which is defined via incompressibility.
    - lurker14 14y ago
      Fair enough, but Kolmogorov randomness is an existence concept, not a constructive concept, so I find it weird to talk about having such a string in this case where a real person sets about to generate a concrete file. Can you generate a Kolmogorov random file on your particular Unix system? That requires specifying what "your Unix system" rather rigorously, which seems unpleasant.
  - deleted 14y ago
    [deleted]
DanBC 14y ago
Here's a very simple example of compression. It explains what other people have said about using redundancy to achieve compression. (https://sites.google.com/site/usingaiforbettercompression/ https://sites.google.com/site/usingaiforbettercompression/) (And then it has a few quotes from different places about why AI is linked to compression.) (Google sites is sub-optimal, and when I've finished it I'll host it elsewhere.) (Also, submitted it here. (http://news.ycombinator.com/item?id=4616442) http://news.ycombinator.com/item?id=4616442)) EDIT: I'll just paste it here. I need to work on language and tone, apologies for being patronising. Imagine we have a language with just 4 letters: A, B, C, and D. In this language the frequency probabilities are A = 0.5, B = 0.3, C = 0.15, and D = 0.05 A short sentence in this language may look something like this, after we strip out the spaces. There are 20 characters. ACABBAABABAACBAADCAB Now let's represent those letters with carefully chosen numerical values. A = 0 B = 10 C = 110 D = 111 Our sentence becomes (first with spaces, and then without) A C A B B A A B A B A A C B A A D C A B 0 110 0 10 10 0 0 10 0 10 0 0 110 10 0 0 111 110 0 10 0110010100010010001101000111110010 These values were chosen because they are unambiguous, even when you remove the spaces. You cannot turn the above collection of 1's and 0's into anything other than the correct sequence. This uses 34 characters to represent the our sentence. But there's a further step. We create another table. 00 = q 01 = w 10 = z 11 = x And again we represent the sentence with the new letters. 0110010100010010001101000111110010 01 10 01 01 00 01 00 10 00 11 01 00 01 11 11 00 10 w z w w q w q z q x w q w x x q z wzwwqwqzqxwqwxxqz This is 17 characters. We have saved 3 characters. Obviously this isn't great, but it's just an example to demonstrate the process. You can see from this example why compressing random data can be hard. One feature of randomness is an equal distribution of each possible character. We cannot use redundancy to create our dictionary tables.
huhtenberg 14y ago
If you were able to trim just 1 byte of an arbitrary file by running it through a compressor, then you could reduce any file to a single byte by repeatedly running it through the same compressor. Clearly, that's not possible.
- crististm 14y ago
  Actually it is possible - the problem is that you will move the information into your compressor. I don't know how "universal" this compressor would be though...

praptak 14y ago

It's the contest organizer who gets to choose the file contents. Random noise is practically non-compressible. Btw, tar by itself does not compress at all.

georgemcbay 14y ago
"Random noise is practically non-compressible." It has to be actually random though. I was hoping the solution to this would be that Patrick had figured out that Mike used a specific random number generation engine with a specific seed and thus his decompressor was just a reversed engineered version of the original data generator and the file it "decompressed" was 0 bytes long.
- juan_juarez 14y ago
  It says the source was random.org - probably the closest thing to 'true' random you're going to find freely available.

dsr_ 14y ago

You can't compress any arbitrary file, but there are lots of files you can compress. Proof for the first part (aka the Pigeonhole Principle): look at the universe of files that are 100 bits long. Apply your compressor to each one, so that you have reduced the length of each file to 99 bits. But the number of 99-bit long files is half the number of 100-bit long files, which means that for some of your compressed files, you can't tell exactly which 100-bit long file it corresponds to. Now, you can perform run length encoding on some files. That looks for runs of repeated bits, replaces them with a special marker, and writes a dictionary to translate the marker to the run. You can look for patterns. This will work... on some files. Not on all. A good compressor will try several different encoding schemes to do its work, and is going to succeed on files with embedded patterns. For instance, if the file is ASCII text, lots of bit patterns will never occur, and lots will occur repeatedly. If the file is English ASCII text, even more redundancy can be exploited. If the file is a structured data set, there's almost certainly a bunch of repeating patterns. But for purely random data, there won't be enough patterns repeated enough to exploit.

dubya 14y ago

Generally, you can't compress every n-bit file into an (n-1) bit program because there are twice as many n-bit files as (n-1) bit programs. So the average n-bit file is not compressible. On the other hand, there are clearly some files that are highly compressible, and many that are at least a little bit compressible, so it's not as impossible as the challenge issuer made it sound. I'm not sure how you'd calculate this, but if more than 1 in 50 random files were somewhat compressible then it would be a bad bet to issue.

bradleyjg 14y ago

Lossless compression works by exploiting redundancy in the data. If I want to compress a text file that contains the word 'uncharacteristically' 1000 times, I can simply replace ever occurrence with the a certain short unused byte sequence and record the mapping in the header. Similarly in an image file, if there is a block of 50 pixels that are all the same color, I can replace that block with a special byte sequence and map the coordinates and color in the header. But if I have truly random data, there are no patterns to exploit. The shortest means of representing random data - is the data itself. This is provable using information theory (which in a way is a branch of thermodynamics).

lurker14 14y ago
nitpick: There is no such thing as a truly random piece of data. "Truly random" is only meaningful in the limit as the file size goes to infinity. The string "000000" could be generated by a truly random process just as well as any any other.
- bradleyjg 14y ago
  I meant Kolmogorov randomness which is defined via incompressibility.
  - lurker14 14y ago
    Fair enough, but Kolmogorov randomness is an existence concept, not a constructive concept, so I find it weird to talk about having such a string in this case where a real person sets about to generate a concrete file. Can you generate a Kolmogorov random file on your particular Unix system? That requires specifying what "your Unix system" rather rigorously, which seems unpleasant.
- deleted 14y ago
  [deleted]

DanBC 14y ago

Here's a very simple example of compression. It explains what other people have said about using redundancy to achieve compression. (https://sites.google.com/site/usingaiforbettercompression/ https://sites.google.com/site/usingaiforbettercompression/) (And then it has a few quotes from different places about why AI is linked to compression.) (Google sites is sub-optimal, and when I've finished it I'll host it elsewhere.) (Also, submitted it here. (http://news.ycombinator.com/item?id=4616442) http://news.ycombinator.com/item?id=4616442)) EDIT: I'll just paste it here. I need to work on language and tone, apologies for being patronising. Imagine we have a language with just 4 letters: A, B, C, and D. In this language the frequency probabilities are A = 0.5, B = 0.3, C = 0.15, and D = 0.05 A short sentence in this language may look something like this, after we strip out the spaces. There are 20 characters. ACABBAABABAACBAADCAB Now let's represent those letters with carefully chosen numerical values. A = 0 B = 10 C = 110 D = 111 Our sentence becomes (first with spaces, and then without) A C A B B A A B A B A A C B A A D C A B 0 110 0 10 10 0 0 10 0 10 0 0 110 10 0 0 111 110 0 10 0110010100010010001101000111110010 These values were chosen because they are unambiguous, even when you remove the spaces. You cannot turn the above collection of 1's and 0's into anything other than the correct sequence. This uses 34 characters to represent the our sentence. But there's a further step. We create another table. 00 = q 01 = w 10 = z 11 = x And again we represent the sentence with the new letters. 0110010100010010001101000111110010 01 10 01 01 00 01 00 10 00 11 01 00 01 11 11 00 10 w z w w q w q z q x w q w x x q z wzwwqwqzqxwqwxxqz This is 17 characters. We have saved 3 characters. Obviously this isn't great, but it's just an example to demonstrate the process. You can see from this example why compressing random data can be hard. One feature of randomness is an equal distribution of each possible character. We cannot use redundancy to create our dictionary tables.

huhtenberg 14y ago

If you were able to trim just 1 byte of an arbitrary file by running it through a compressor, then you could reduce any file to a single byte by repeatedly running it through the same compressor. Clearly, that's not possible.

crististm 14y ago
Actually it is possible - the problem is that you will move the information into your compressor. I don't know how "universal" this compressor would be though...