Ytdyklly

According to Wikipedia:

Shannon's entropy measures the information contained in a message as opposed to the portion of the message that is determined (or predictable). Examples of the latter include redundancy in language structure or statistical properties relating to the occurrence frequencies of letter or word pairs, triplets etc.

So entropy is a measure of the amount of information contained in a message. Entropy coders are used to losslessy compress such a message to the minimum number of bits needed to represent it (entropy). To me this looks like a perfect entropy encoder would be all that is needed to losslessy compress a message as much as possible.

Many compression algorithms however use steps before entropy coding to supposedly reduce the entropy of the message.

According to german Wikipedia

Entropiekodierer werden häufig mit anderen Kodierern kombiniert. Dabei dienen vorgeschaltete Verfahren dazu, die Entropie der Daten zu verringern.

In english:

Entropy coders are frequently combined with other encoders. Previous steps serve to reduce the entropy of the data.

i.e. bzip2 uses the Burrows-Wheeler-Transform followed by a Move-To-Front-Transform before applying entropy coding (Huffman coding in this case).

Do these steps really reduce the entropy of the message, which would imply reducing the amount of information contained in the message? This seems contradictory to me, since that would mean that information was lost during compression, preventing lossless decompression. Or do they merely transform the message to improve the efficiency of the entropy coding algorithm? Or does entropy not correspond directly to the amount of information in the message?

A lot of casual descriptions of entropy are confusing in this way because entropy is not quite as neat and tidy a measure as sometimes presented. In particular, the standard definition of Shannon entropy stipulates that it only applies when, as Wikipedia puts it, "information due to independent events is additive."

In other words, independent events must be statistically independent. If they aren't, then you have to find a representation of the data that defines events in ways that make them truly independent. Otherwise, you will overestimate the entropy.

To put it yet another way, Shannon entropy only applies to true probability distributions, and not to random processes in general. For concrete examples of processes that don't fit the assumptions of Shannon entropy, consider...

Markov processes

A Markov process is a series of events in which the most recent event is sampled from a distribution that depends on one or more previous events. Obviously a huge number of real-world phenomena are better modeled as Markov processes than as discrete, independent probability distributions. For example: the text you're reading right now!

The naively calculated Shannon entropy rate of a Markov process will always be greater than or equal to the true entropy rate of the process. To get the true entropy of the process, you need to take into account the statistical dependence between events. In simple cases, the formula for that looks like this:

$$ H(mathcal{S}) = - sum_i p_i sum_j p_i (j) log p_i (j) $$

This can also be represented like so:

$$ H(Y) = - sum_{ij} mu_i P_{ij} log P_{ij} $$

Again quoting Wikipedia, here "$mu_i$ is the asymptotic distribution of the chain" -- that is, the overall probability that a given event will occur over a long horizon.

This is all a complicated way of saying that even when you can calculate the overall probability of a given event in the long run, certain sequences of events are more likely than others in a Markov process. So for example, the following three strings of English words are increasingly less likely:

• They ran to the tree


• The tree ran to they


• Tree the they to ran

But Shannon entropy will assess all three strings as equally likely. The Markov process entropy takes the difference into account, and as a result, it assigns a lower entropy rate to the process.

Entropy rates are model-dependent

If you zoom way out, here's the big picture: the entropy rate of a given sequence of events from an unknown source is model-dependent. You'll assign a different entropy rate to a particular series of events depending on how you model the process that generated them.

And very frequently, your model of the process isn't going to be quite correct. This isn't a simple or easy to solve problem. In fact, in general, it is impossible to assign a true entropy rate to a sufficiently long and complex sequence of events, if you don't know what the true underlying process is. This is a central result in algorithmic information theory.

What this means in practice is that given an unknown source of sequences of events, different models will yield different entropies, and it's impossible to know which is correct in the long run -- although the one that assigns the lowest entropy is probably the best.

No, if the algorithm is lossless no steps in the compression sequence can reduce its entropy - otherwise it would not be able to be decompressed/decoded. However, the additional entropy may be stored in 'out-of-band' information - such as the list that needs to be maintained in order to decode the move-to-front transform.

They reduce the apparent entropy inherent in the structure of the original message. Or in other words they tune the message to make use of the strengths of the next stages of compression.

One simple example would be replacing the name in the end tags of xml with a special symbol. You can perfectly recreate the original xml from that but the compressor doesn't have to include the full name again in that place.

A more real-world example is png compression. It's entropy compressor is DEFLATE, which is a combination of Lempel-Ziff and Huffman. This means that it works best with values and patterns that repeat often. Most adjacent pixels tend to be similar colors. So each row is assigned a filter which turn the original pixel values into a differential encoding. This way the values that end up encoded by DEFLATE are mostly close to 0. In the extreme case this will turn a smooth gradient from all different values into a single value throughout the row which the LZ portion or DEFLATE makes very quick work of.

Entropy coders do not compress the message to the minimum number of bits needed to represent it. I know it's tempting to think that, but it's not what they do. They aren't magic and they can't achieve that.

Instead, they do something a bit less magical -- but still useful. Suppose for the moment that we knew that each character of the message was chosen independently from some distribution. Then it would be possible to build a lossless compression algorithm that optimally compresses the messages. These algorithms are called entropy encoders.

Now real messages usually don't have that independence property. For instance, if you see a Q, it's likely that the next letter is a U. And so on. It is still possible to apply an entropy encoder algorithm to a real message, where each character isn't chosen independently of the rest. The algorithm will still be lossless, it can still be used for compression, and in practice, it will still often shorten the length of the message. However, it doesn't shorten it to the minimum possible length. It doesn't compress the message to something whose length is equal to the entropy of the message; it compresses it less than that.

Once you realize this property of entropy encoders, then the paradox evaporates.

In general, any lossless step never reduces the entropy of the message. However, it might put the message into a form where some other compression algorithm is more effective, so it might still be useful (on average) in practice.