4 ms·

Quote: "A lossless compression algorithm that can actually reduce the size of at least one input file must also necessarily expand the size of at least one othe

Quote: "A lossless compression algorithm that can actually reduce the size of at least one input file must also necessarily expand the size of at least one other possible input file. This is a direct application of the pigeonhole principle. A compression algorithm that claims to never increase the size of any input, while at the same time reducing the size of at least some inputs (it's not the trivial do-nothing compression that, by definition, preserves the length of the input), is called paradoxical compression." This paradoxical compression, as stated above is incomplete. You can achieve all input files to be compressed without having to expand any other file but you would expand time instead. Let me explain it: - Any set of data can be expressed using mathematical functions/algorithms that can be saved as one file, very small in data compared with original data, but to do so you'll need to invest a lot of time to find those functions/algorithms. One practical example would be a mission to Alpha Centauri which might want to have Earth's internet on board but no physical space for all that data. Let's say it takes 10 years to prepare the mission which in that case you'd also use this 10 years to compress, for argument sake, Google's big index, (or NSA Utah center if you like that one) and you'll have on board, on a single thumb stick, Internet version from 10 years before launch. Edit: Since some people have problems understanding this extreme compression, I am trying to clarify this further. This method is unique to that set of data. And it can be applied to only that data, only one time and that's it. Not a general set of algorithms so you can compress anything else. It will fail if not applied to that data. It is not a classic compression, it is more, if you like the term, a data generator. It will run a program that at the end of its run will generate that Internet version you started with 10 years ago. But to do that you'll need to research how to do that data generating, hence the extreme time it takes to achieve. In practice I'll envision a lot of people getting their slice of data and do one function. And the program will run those functions one after another, generating the data.

anonymoushn 5y ago
This is incorrect. If you would like to encode every string that's 10 gigabytes long to a string that's at least 1 byte shorter, then you don't have enough strings that are at least 1 byte shorter. There are fewer of them by a factor of about 256, and each one of them can decode to only one 10-gigabyte-long string. This is explained in the article.
beecafe 5y ago
No, you can't. Consider applying your compression algo twice, or N times. If it gets smaller each time, then eventually you could compress anything to a single bit.
- unnouinceput 5y ago
  You can't apply this method twice. Please understand this particular compression type is unique to a single given fixed set of data. That's it! It's not a general compression method, is custom made for that data only. And it takes time to research it to achieve that extreme compression.
  - anonymoushn 5y ago
    It doesn't work. If it did work, you could apply it separately to every string containing 100 bits and end up with 2^100 separate strings containing fewer than 100 bits, each of which decodes to a unique 100-bit string.
    - unnouinceput 5y ago
      You're still missing the point. Please read the edit I made to root comment.
      - anonymoushn 5y ago
        You're still wrong. A data generator is a program that runs on some computer. Programs are strings with lengths. If you'd like to use a purpose-built computer or decoder for each output, then you need to include the complexity of the computer or decoder in the compressed size. Otherwise you could write a decoder such as "when given any input, output the contents of wikipedia" and claim that it compresses a certain text to 0 bytes.
  - beecafe 5y ago
    If your compression algorithm worked for just one fixed set of data, then you could just store that fixed data in the decompressor and achieve infinity compression of the data to 0 bits.
gus_massa 5y ago
You mean something like http://prize.hutter1.net/ http://prize.hutter1.net/ ? The problem is that once you fix the architecture (for example a x64 compatible processor) and you try to compress every possible 1GB files like in my link, for some of them you will get a size of descompresor+data that is very small, specially if you have a lot of time. This is essentially the challenge. The articles in Wikipedia have a lot of internal structure, so if you are smart and/or have lot time you can get a very small size. Anyway, once you fixed the architecture, it is possible that an evil person looks at the details of the the architecture and make a file that is so weird that the size of descompresor+data is bigger, in spite you are very smart or you have a lot of time to try the brute force approach. The Pigeonhole Principle guarantees that the evil person can always success, in spite the file with the problem may not be very interesting and it may be very difficult to find it. (Actually, any file with cryptography random number will probably work. A file with pseudo random numbers is not enough, because with enough patient you may find the algorithm, seed and offset and use that as the compressed version. The digits of pi skipping the first million is also a bad idea, because is also a ba idea for the same reason.)
- unnouinceput 5y ago
  Yes, something like that, except in my case you'd need a lot more than 50 hours to generate back the data. Also I agree with your points, this assumes every participant to be honest when researching their slice, as per my edit.
  - gus_massa 5y ago
    With your method, you will be able to compress most sensible files but not all files. The main point of this article is that with any method, you can not compress all files. In the case of the ship, they will be able to store a very compressed version of Wikipedia, but they will not be able to store a file with the same size that records the last bit of the central pixel of a CCD carera that is pointed to the sun filtered with the von Neumann trick https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_...
aaaaaaaaaaab 5y ago
Your idea is information-theoretically unsound. You cannot create information out of thin air.

anonymoushn 5y ago

This is incorrect. If you would like to encode every string that's 10 gigabytes long to a string that's at least 1 byte shorter, then you don't have enough strings that are at least 1 byte shorter. There are fewer of them by a factor of about 256, and each one of them can decode to only one 10-gigabyte-long string. This is explained in the article.

beecafe 5y ago

No, you can't. Consider applying your compression algo twice, or N times. If it gets smaller each time, then eventually you could compress anything to a single bit.

unnouinceput 5y ago
You can't apply this method twice. Please understand this particular compression type is unique to a single given fixed set of data. That's it! It's not a general compression method, is custom made for that data only. And it takes time to research it to achieve that extreme compression.
- anonymoushn 5y ago
  It doesn't work. If it did work, you could apply it separately to every string containing 100 bits and end up with 2^100 separate strings containing fewer than 100 bits, each of which decodes to a unique 100-bit string.
  - unnouinceput 5y ago
    You're still missing the point. Please read the edit I made to root comment.
    - anonymoushn 5y ago
      You're still wrong. A data generator is a program that runs on some computer. Programs are strings with lengths. If you'd like to use a purpose-built computer or decoder for each output, then you need to include the complexity of the computer or decoder in the compressed size. Otherwise you could write a decoder such as "when given any input, output the contents of wikipedia" and claim that it compresses a certain text to 0 bytes.
- beecafe 5y ago
  If your compression algorithm worked for just one fixed set of data, then you could just store that fixed data in the decompressor and achieve infinity compression of the data to 0 bits.

gus_massa 5y ago

You mean something like http://prize.hutter1.net/ http://prize.hutter1.net/ ? The problem is that once you fix the architecture (for example a x64 compatible processor) and you try to compress every possible 1GB files like in my link, for some of them you will get a size of descompresor+data that is very small, specially if you have a lot of time. This is essentially the challenge. The articles in Wikipedia have a lot of internal structure, so if you are smart and/or have lot time you can get a very small size. Anyway, once you fixed the architecture, it is possible that an evil person looks at the details of the the architecture and make a file that is so weird that the size of descompresor+data is bigger, in spite you are very smart or you have a lot of time to try the brute force approach. The Pigeonhole Principle guarantees that the evil person can always success, in spite the file with the problem may not be very interesting and it may be very difficult to find it. (Actually, any file with cryptography random number will probably work. A file with pseudo random numbers is not enough, because with enough patient you may find the algorithm, seed and offset and use that as the compressed version. The digits of pi skipping the first million is also a bad idea, because is also a ba idea for the same reason.)

unnouinceput 5y ago
Yes, something like that, except in my case you'd need a lot more than 50 hours to generate back the data. Also I agree with your points, this assumes every participant to be honest when researching their slice, as per my edit.
- gus_massa 5y ago
  With your method, you will be able to compress most sensible files but not all files. The main point of this article is that with any method, you can not compress all files. In the case of the ship, they will be able to store a very compressed version of Wikipedia, but they will not be able to store a file with the same size that records the last bit of the central pixel of a CCD carera that is pointed to the sun filtered with the von Neumann trick https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_...

aaaaaaaaaaab 5y ago

Your idea is information-theoretically unsound. You cannot create information out of thin air.