Entropy

Names of different lengths

Our first lesson ended with a sensible suspicion: if the letters of a language do not appear equally often, why should we punish them all with labels of the same length? To turn that suspicion into a practical method we need one new idea, and it is as natural as tidying a house.

A system in which every letter or symbol is given a code with exactly the same number of binary digits is called a fixed-length code. If we have thirty-two possible signs in view, each of them will cost an unbending 5 bits, whether it is used a thousand times on the page or once in an entire volume. This way of working is extremely convenient for engineers — which is why the first computers adopted it everywhere — but it ignores the reality of the world completely: it treats a letter that is everywhere, such as “e”, exactly like a rare letter such as “q”.

We can take another road, though: we can let the labels have different lengths. What then matters is no longer the size of a single letter taken on its own, but the average length of the whole text. In that average, every symbol weighs its length by how often it is called upon. If we give a long code to a rare letter we shall hardly feel the burden, because we pay it only now and then. But if we put that same long code on a frequent letter, we should pay the toll every few words. It is exactly the logic of a well-packed bag: the things we need at every step lie ready to hand at the top, while the things for rare occasions can be stowed as deep as you like at the bottom of the case.

The central question of this lesson thus becomes one that matters greatly for communication: how far can we push that average length down? The answer is one of the loveliest surprises in science: the limit does not depend on how ingenious we are at inventing codes; it is dictated strictly by the probabilities of the symbols in nature.

How much one outcome informs

To discover that limit it helps to look first at a single event rather than a whole text. Imagine a piece of news that has only one chance in eight of coming true. When it does happen, the situation is exactly like finding one box among a group of eight: to settle it we needed three successive binary questions, so the news brings us exactly three bits of novelty. An event that had one chance in two (50%) asks a single question: it brings us one bit. And an absolutely certain event, one we knew beforehand, asks no question at all: it brings us zero bits.

The general rule emerges with perfect clarity: an outcome whose probability of appearing is p gives us an amount of information equal to the number of halvings needed to tell it apart from the other possibilities. The rarer and more unexpected an event, the more information it brings when it does occur. This quantity is called the information content of the outcome, or, in a far livelier and more intuitive phrase, the degree of surprise it causes. That surprise need not be a whole number: an event with a probability of 1 in 3, for instance, brings about 1.58 bits of surprise, sitting naturally between the relative certainty of a 1-in-2 chance and the rarity of a 1-in-4 one.

Let us pause a moment and breathe this idea in: information is not a substance locked inside the object itself, but a bridge between what happened and what we expected to happen. The news that snow is falling in the mountains in the depth of winter, in January, barely raises an eyebrow: the surprise is close to nothing, so the information is minimal. But the very same headline, “snow in the mountains”, arriving on a scorching afternoon in July, leaves us astonished and becomes a sensation on the spot. Information theory takes this everyday human experience and gives it a faultless unit of measure.

Entropy

Now we can look at the whole picture again. A source of messages — a keyboard, a die thrown on the carpet or a weather station — produces symbols one after another, each with its own probability and its own degree of surprise. Entropy of that source is simply the average surprise produced by each symbol it emits: we take the surprise of every possible outcome, weigh it by the probability with which that outcome turns up, and add them all together. Entropy is measured in bits per symbol and is traditionally written with the letter H.

Entropy always lies between two very clear extremes. At one extreme, if all N possible symbols have strictly equal chances of appearing, unpredictability is at its greatest and entropy reaches the highest value it can (exactly the case of the boxes in the previous lesson). At the other extreme, if one of the symbols is guaranteed 100% and the others never appear, entropy collapses to zero: the outcome is known in advance, and the source, however much it “speaks”, teaches us nothing new. Between these two shores lie all the languages of the earth and all the signals of real life, and the interactive figure below lets you explore the passage from one to the other.

Why is entropy a monumental discovery? Because it answers the great question of efficiency once and for all. In his famous 1948 paper, Claude Shannon proved two fundamental truths in a single stroke: first, that no coding scheme, however brilliant, can push the average length of a text below the entropy of the source; and second, that there are always practical methods letting us come as close to that barrier as we wish. Entropy is therefore the pure, net weight of the information in a message, freed of every arbitrary convention of writing. A text of a thousand letters does not automatically “weigh” five thousand bits merely because the keyboard uses 5 bits per character; it holds only as many bits as it brings genuine surprise, the rest being plain packaging or wasted room.

The term was borrowed from physics. When Shannon found the mathematical formula for average surprise, he noticed that it agreed down to the last comma with the equation by which Ludwig Boltzmann had described, half a century earlier, the microscopic disorder in a gas. Legend has it that the great mathematician John von Neumann advised him with a smile: “Call it entropy. In the first place because it is the same formula as in thermodynamics, and in the second place because nobody really knows what entropy is, so in a debate you will always have the upper hand.” Anecdote aside, the connection is genuine and deep: an observer’s lack of information and the disorder of particles in nature are two faces of the same coin.

The Huffman code

The time has come to see how such an optimal code can actually be built. In 1952 a young MIT student named David Huffman found himself facing a choice: his renowned professor, Robert Fano, had offered the class the option either of sitting a hard final exam or of finding an optimal method for coding symbols — a problem that had remained unsolved. Huffman worked for months without success and was on the point of giving up to revise for the exam. As he gathered his crumpled drafts to throw them in the bin, a brilliant idea struck him: the secret was not to build the code from the top down, splitting the frequent symbols, but to start from the bottom up, joining the two rarest symbols.

Huffman’s method is as simple as it is elegant. We look for the two symbols that appear most rarely and join them into a pair; they will have identical codes, told apart only by the last digit (one gets 0, the other 1). That pair is now treated as a single combined entity whose probability is the sum of the two. We repeat the step with what is left: again we look for the two smallest probabilities and join them, rung by rung, until all the branches gather into a single root. At the end, reading the path from the root back to each letter, we obtain the guaranteed optimal code.

This code has a golden property, without which computers would stumble at every step: no code is the beginning (the prefix) of another, longer code. Thanks to that property, called the prefix code, all the letters can be stuck directly one after another in a single unbroken string of bits, with no need for spaces or separating commas. At the receiving end we read digit by digit: at the exact moment we recognise a valid code we know for certain that the letter has ended, we put it on the screen and start deciphering the next character.

When real texts are analysed, the space between words is counted as a character in its own right and is almost always the commonest symbol in the text. For clarity, capital letters are turned into small ones and punctuation marks are simplified.

The Huffman code gives every individual character a whole number of bits — at least one bit — and here lies its one practical limitation. If we have a message made up almost entirely of the letter “a”, the surprise brought by each “a” falls well below one bit (to 0.1 bits, say), yet the Huffman code cannot give it less than one whole binary digit. In such extreme cases the Huffman code stays stuck a little above the ideal entropy.

How, then, can we reach Shannon’s theoretical promise? The answer is to stop coding letters one at a time and to group them into blocks instead: pairs of two, or groups of three letters at once. An extremely predictable sequence gets a single short code of one bit, and that cost is now shared between two or three characters. As we look at larger groups of symbols, the average length descends smoothly and comes practically to the absolute threshold of entropy.

Redundancy

The difference between the length of a fixed-length code and the true entropy of the message shows how much “ballast” the ordinary way of transmitting data carries. That surplus of representation, taken as a share of the total room, is called redundancy.

The human language we speak every day is extraordinarily redundant, and that for several intertwined reasons: some letters are far more frequent than others, certain combinations of sounds are practically impossible, and the words in a sentence announce one another through rules of grammar and sense. Thanks to redundancy we can understand without effort a message such as “g__d m_rn_ng, h_w ar_ y_u?”, even though a third of the letters are missing, and we can make out a friend’s voice in a noisy café. Redundancy is a sword with two splendid edges: on one hand it is what lets us compress files massively on a computer; on the other it is the safety net that protects speech and writing from errors and misunderstandings.

The Huffman algorithm we explored above exploits only the first part of that redundancy: the individual frequency of each letter. But truly powerful compression goes deeper: it takes the context of the preceding letters into account. If we have just met the letter “q”, for instance, we know almost for certain that “u” will follow; the appearance of “u” is no surprise to anyone, so it is not worth spending precious bits to announce it.

Here we arrive at a conclusion of overwhelming beauty: to compress a text is, in essence, to be able to predict it. The better a system understands the rules and the context of a language, the more precisely it anticipates what will come next, and what is perfectly anticipated no longer needs to be transmitted. This power of prediction — extended from letters to words, sentences and whole ideas — is the very secret engine from which, in the second half of our course, the great language models and today’s artificial intelligence will be born.