3 ms·

This is probably a dumb question, but I recall from (way) back in my college days studying Shannon's source coding theorem that there are calculable limits rega

This is probably a dumb question, but I recall from (way) back in my college days studying Shannon's source coding theorem that there are calculable limits regarding how much a data stream can be compressed. Has this limit been calculated for the sample file in question? And apologies if this was in the linked article or one of the footnotes.

AnotherGoodName 3y ago
No. In fact there are limits but unless you've already written a 'perfect compression tool' you can't actually know the limit. https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity is ultimately what you're looking for btw. Shannon is more about limits in transmission speed given noise but Kolmogorov dealt with the limits of compression which is actually unknowable.
mgraczyk 3y ago
To establish bounds in this way, you have to start with some claim about the distribution of the input data. In this case, the data is natural human language, so it's difficult or impossible to directly state what distribution the input was drawn from. Even worse, the prize is for compressing a particular text, not a sample from a distribution, so tight bounds are actually not possible to compute. There is some discussion on the Hutter prize page, under "What is the ultimate compression of enwik9?" http://prize.hutter1.net/hfaq.htm http://prize.hutter1.net/hfaq.htm
- jftuga 3y ago
  From this article: More empirically, Shannon's lower estimate suggests that humans might be able to compress enwik9 down to 75MB, and computers some day may do better.
  - AnotherGoodName 3y ago
    The current best compresses it to <15MB because it's not a human which that example is referring to. :)
    - userbinator 3y ago
      That's enwik8. enwik9 is an order of magnitude larger.
  - londons_explore 3y ago
    Notable that enwiki8/9 isn't really just human text - a good ~half of the data is random xml markup which may not have the same properties as text.

AnotherGoodName 3y ago

No. In fact there are limits but unless you've already written a 'perfect compression tool' you can't actually know the limit. https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity is ultimately what you're looking for btw. Shannon is more about limits in transmission speed given noise but Kolmogorov dealt with the limits of compression which is actually unknowable.

mgraczyk 3y ago

To establish bounds in this way, you have to start with some claim about the distribution of the input data. In this case, the data is natural human language, so it's difficult or impossible to directly state what distribution the input was drawn from. Even worse, the prize is for compressing a particular text, not a sample from a distribution, so tight bounds are actually not possible to compute. There is some discussion on the Hutter prize page, under "What is the ultimate compression of enwik9?" http://prize.hutter1.net/hfaq.htm http://prize.hutter1.net/hfaq.htm

jftuga 3y ago
From this article: More empirically, Shannon's lower estimate suggests that humans might be able to compress enwik9 down to 75MB, and computers some day may do better.
- AnotherGoodName 3y ago
  The current best compresses it to <15MB because it's not a human which that example is referring to. :)
  - userbinator 3y ago
    That's enwik8. enwik9 is an order of magnitude larger.
- londons_explore 3y ago
  Notable that enwiki8/9 isn't really just human text - a good ~half of the data is random xml markup which may not have the same properties as text.