4 ms·

Author here. I think most of the criticism on random data compression is too far sweeping and absurd. For example saying that it's impossible to compress rando

Author here. I think most of the criticism on random data compression is too far sweeping and absurd. For example saying that it's impossible to compress random data because if it were possible you could compress data forever and make any file a single bit... is basically reductio ad absurdum. I don't see anyone making that claim (and I certainly didn't in my article where I specified a limit of 1k.) People like to bring up the pigeonhole principle as if it's a mathematical proof that there can never be a practical algorithm for compressing random data. But the truth is if there's so many different ways to represent data then we might never run into a situation where it's actually relevant. The other fault I see in these comments is the knee-jerk reaction over using a PoW-inspired algorithm for set reduction. Why is that? Could it be because blockchain technology is no longer in your favourite hype cycle and you need to signal to all your tech buddies that you're in the know by bandwagoning like everyone else? PoW is far superior to other ways to reduce the sets and has the added bonus that nonces are more compressible. The point that I got to with this research is having 14 bits left over per set to save offsets after filtering results. I was running some code yesterday and noticed that using 3 x 3 bit fields to save the number of zero bit information in the hashes produced low offsets. I think that this could be compressed with the same simple quotient idea I already wrote about to fit in the 14 bits so that you could quickly filter and recover the sets and dereference the original data. This would reduce 1024 bytes to around 1015~ which would be more than enough to solve the 20+ year compression challenge and refute claims that random data can't be compressed. Of course, the cluster that I built to run my code is too slow and I'm getting tired of waiting. So I will need a break from this. In the mean time you can stick to the insults and other predictions in the comments. As we all know from experience: hacker news is a positive and constructive community that is excellent at predicting the future.

filmfact 6y ago
Lets restructure the problem slightly, so the objection is clearer. Instead of binary data, think of decimal numbers. We’ll take a five digit number and compress using function f to a four digit one. We could come up with many different ways of doing this, but lets just throw away the most significant digit. F(00123) = 0123 F(01234) = 1234 Great - but now what happens with a five digit number? F(12345) = 2345 We lose information. We can’t encode the fifth digit in any of the other digits because that would change their meaning. It should be evident that there is no scheme where you can encode a five digit number as a four digit number without either being lossy: For some X: F’(F(X)) != X Or having undefined ranges i.e. F’(F(X)) = X, only where digit 5 = 0 Increasing the number of digits just obfuscates the problem by moving it from the realm of numbers, where it’s clear there can be no 1-1 bi-directional mapping between two sets of unique numbers where the cardinality of the sets is not equal, to the realm of ‘data’ where we can confuse the issue. At the end of the day, a function that only takes 2^(1015 * 8) Unique input values can have at most 2^(1015 * 8) unique outputs. And while thats a lot of outputs, it’s far fewer than 2^(1024 *8) that you need to represent to be able to compress any random input. Ill leave you with a quote from Oscar Wilde: “A true friend stabs you in the front, not the back”
- twhitmore 6y ago
  Exactly. Each compressed input can only decompress to one output. But the number of input values possible is far smaller than the possible output space. Therefore many outputs cannot be reproduced. Real compression algorithms compressing structured data preserve the above properties. All outputs are representable, but they devote shorter codes (and thus most of the coding symbol space) to the most common patterns. Since coding symbol space is finite, random or less compressible data are left with longer symbols/ bitstrings than if conveyed uncompressed. For a reasonably structured file, the overall outcome is compression. However random files experience a small increase in size due to coding overhead.

filmfact 6y ago

Lets restructure the problem slightly, so the objection is clearer. Instead of binary data, think of decimal numbers. We’ll take a five digit number and compress using function f to a four digit one. We could come up with many different ways of doing this, but lets just throw away the most significant digit. F(00123) = 0123 F(01234) = 1234 Great - but now what happens with a five digit number? F(12345) = 2345 We lose information. We can’t encode the fifth digit in any of the other digits because that would change their meaning. It should be evident that there is no scheme where you can encode a five digit number as a four digit number without either being lossy: For some X: F’(F(X)) != X Or having undefined ranges i.e. F’(F(X)) = X, only where digit 5 = 0 Increasing the number of digits just obfuscates the problem by moving it from the realm of numbers, where it’s clear there can be no 1-1 bi-directional mapping between two sets of unique numbers where the cardinality of the sets is not equal, to the realm of ‘data’ where we can confuse the issue. At the end of the day, a function that only takes 2^(1015 * 8) Unique input values can have at most 2^(1015 * 8) unique outputs. And while thats a lot of outputs, it’s far fewer than 2^(1024 *8) that you need to represent to be able to compress any random input. Ill leave you with a quote from Oscar Wilde: “A true friend stabs you in the front, not the back”

twhitmore 6y ago
Exactly. Each compressed input can only decompress to one output. But the number of input values possible is far smaller than the possible output space. Therefore many outputs cannot be reproduced. Real compression algorithms compressing structured data preserve the above properties. All outputs are representable, but they devote shorter codes (and thus most of the coding symbol space) to the most common patterns. Since coding symbol space is finite, random or less compressible data are left with longer symbols/ bitstrings than if conveyed uncompressed. For a reasonably structured file, the overall outcome is compression. However random files experience a small increase in size due to coding overhead.