mjhjmtu

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 generates 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(mathcalS) = - 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, certain sequences of events are more likely than others to be generated by 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 it 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.

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.

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.

The word "Entropy" if often used a bit loosely, to refer to two different things:

• The "total amount of information" in a message or system




• The information "density", or how tightly the information is packed.

OP's quote of the Wikipedia's entry for https://en.wikipedia.org/wiki/Entropy_(information_theory) refers to the first:

Shannon's entropy measures the information contained in a message

But (at least when I'm writing this) the same article starts with:

Information entropy is the average rate at which information is produced by a stochastic source of data.

So one is an amount and one is a rate (similar to distance vs. speed). These are sometimes called "extensive" and "intensive" properties (see https://en.wikipedia.org/wiki/Intensive_and_extensive_properties#Extensive_properties).

A classic example of the distinction is Paul Revere's famous lantern signal: "one if by land, and two if by sea". 1 bit of total information (if we ignore the "none if I haven't gotten to North Church yet" case). If Paul added another set of lanterns in each window of the building, that would be '''redundant''': no more information, so the same "total" or "extensive" entropy; but much more message length, so much lower "intensive" entropy.

If he starts that way but changes to use only one set of lanterns, that's "lossless compression" like in OP's question. The "extensive" entropy is the same, but the "intensive" entropy" is different: Because the number of lanterns in the 2nd window is highly correlated with how many you've seen in the first, the redundant message is more predictable, or less random, so has much lower intensive entropy.

There are two other important things to remember:

• First, we typically don't know the "true" entropy of a system in either sense. A naive bystander doesn't know whether "3 lanterns" would be different message, or whether signals in different window are redundant or not. If Paul makes his ride a habit, we can count and see whether the windows always match each other. But maybe we just haven't watched long enough to see the rare (and probably important!) exceptions.



• 
  

  Second, it matters how you measure. Consider trying to estimate how much is communicated by each successive letter of text (that's a rate, so "intensive" entropy, also sometimes called "relative entropy"):

  
  
  
  • If you just notice that people send text around in 8-bit units, your first "estimate" might be 8 bits per letter.
  
  
  • If you count the number of distinct letters being used, you'd estimate log2(26), or 4.7 bits per letter (a bit higher if you consider spaces, case, etc).
  
  
  • If you consider that "e" is a better bet for "next letter" than "z", you'll measure letter frequencies and get around 4.14 (see http://people.seas.harvard.edu/~jones/cscie129/papers/stanford_info_paper/entropy_of_english_9.htm).
  
  
  • If you count letter-pairs you'll pick up on patterns like "qu", "th", etc., and get around 3.56.
  
  
  • If you count sequences of up to around 5 letters, you'll get still lower values, and as a bonus you can pretty reliably distinguish what human language the text is in).
  
  
  • If you're as hard-core and clever as N. G. Burton and J. C. R. Licklider in "Long-Range Constraints in the Statistical Structure of Printed English" (American Journal of Psychology 68(1955)), you can get up to sequences of 10,0000 letters in a row, and find yet another entropy value.
  
  

But of course, messages can (and do) have many patterns that aren't modelled by such n-gram methods, so the "true" entropy is lower still.

If you model a theoretical infinite source with perfectly random Zipfian distribution of tokens, you can calculate the extensive and intensive entropy it would have, which turns out to depend only on the number of possible distinct tokens. Graphs of what each type of entropy looks like as that number increases, are in [http://www.derose.net/steve/writings/dissertation/Diss.0.html]. The two behave quite differently:

• total (extensive): http://www.derose.net/steve/writings/dissertation/Graph13.png
  


• relative (intensive): http://www.derose.net/steve/writings/dissertation/Graph14.png
  

Hope that helps or is at least interesting...