Hacker News Reader

Comment by hn_throwaway_99 | Hacker News Reader

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.

View on HN

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

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.

The current best compresses it to <15MB because it's not a human which that example is referring to. :)

That's enwik8. enwik9 is an order of magnitude larger.

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.

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 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.

Reply on news.ycombinator.com