From Twenty Questions to Entropy and Huffman Compression

Suppose I secretly choose one of these eight letters. You may ask only questions whose answer is yes or no. Your job is to identify my letter with certainty. How many answers do you need? Because the letters are equally likely, the sensible first question cuts the possibilities into equal halves. Ask whether the letter lies in A through D. One answer leaves the upper four; the other leaves the lower four. The first answer has taken us from eight candidates to four. It has not named the symbol, but it has removed exactly half of the uncertainty. Ask another balanced question inside the surviving half. Four candidates become two. The same yes-or-no answer has again divided the remaining possibilities by two. A third question separates the final pair. Eight leaves now stand at the ends of the tree, and every letter is reached by exactly three answers. The count is not an accident. Three binary answers can form eight distinct answer strings, because two choices made three times give two cubed. Turn that relation around. The number of binary questions needed to choose among eight equal possibilities is log base two of eight, which is three. We give one balanced binary answer a unit of information and call that unit a bit. A bit is not merely a zero stored in memory. It is the distinction between two alternatives that were both still possible. With q binary answers there are two to the q possible answer strings. Therefore identifying one of N equally likely outcomes requires log base two of N bits. Next we will make the letters unequally likely. That one change will lead us first to entropy, the ideal average question count, and then to Huffman coding, a way to build an actual binary description close to that ideal.

Keep the same eight symbols, but change their likelihoods. A now occurs forty percent of the time. B occurs twenty percent. C and D each occur ten percent, and the final four symbols each occur five percent. A alone occupies forty percent of the probability bar. It is twice as likely as B, and four times as likely as either C or D. C and D together occupy another twenty percent. They are less common individually, but they still matter much more often than any one of the four symbols at the narrow end. The final four slices are equal and rare. Each accounts for only one twentieth of the messages. If we keep the old balanced tree, every outcome still costs three questions. That treats a five-percent event exactly like the event that appears forty percent of the time. Instead, ask the most useful question first: is the symbol A? When the answer is yes, which happens forty percent of the time, the search ends after one bit. If it was not A, the next question can separate B. B then takes two answers. The commonest sixty percent of all symbols have received the two shortest paths. The price is that C and D now require four questions. That sounds worse than the old three, but each of those symbols appears only one time in ten. The four rarest outcomes take five questions each. Long answers are not free, but we pay for them on only twenty percent of the symbols. Now average the question counts using their probabilities. A contributes point four times one. B contributes point two times two. C and D together contribute point two times four, and the rare group contributes point two times five. The result is two point six questions per symbol. Some individual outcomes became more expensive, but the outcomes we see most often became much cheaper. The equal-depth plan cost exactly three questions. Exploiting likelihood saves point four of a question per symbol on average. Over a million symbols, that becomes roughly four hundred thousand fewer binary answers.

For eight equal outcomes, three halvings isolate one outcome because one eighth equals one over two cubed. Now replace one eighth by a general probability p. Imagine a very large collection of equally detailed possibilities. An event with probability p occupies the fraction p of them. To isolate that fraction by balanced binary questions, we keep halving. After q balanced questions, one answer path identifies about one part in two to the q. To match an event occupying fraction p, two to the q must be about one over p. Solve for q. The ideal question count is log base two of one over p. Equivalently, it is minus log base two of p. This quantity measures surprise. A likely event has a large p and a small information value. A rare event has a small p and needs a longer answer path to distinguish it. For A, p is point four, so the ideal length is about one point three two two bits. For a five-percent symbol, it is about four point three two two bits. These are not yet legal single-symbol code lengths. A single binary question cannot be split into a fraction. But across a long stream, common and rare symbols can share a description strategy, and a fractional average becomes meaningful. To find the ideal average, weight each symbol's question count by the probability of seeing that symbol, then add. This weighted average is the quantity we call entropy. Now calculate it for our distribution. A contributes about point five two nine bits per source symbol. That is its ideal length multiplied by the forty-percent frequency with which we pay it. B contributes about point four six four. C and D together contribute about point six six four. The four five-percent symbols each carry more surprise, and together they contribute about point eight six four bits. Adding every group gives an entropy of about two point five two two bits per symbol. Here is another way to read the same number. In a long block of n symbols, the probability pattern concentrates most messages among roughly two to the n H typical sequences. Distinguishing that many likely messages needs about the log of their count, which is n H binary answers. Entropy is therefore not an arbitrary formula. It is the question count forced by the number of likely messages.

Huffman coding turns the probability list into a binary tree. Begin with one leaf for every symbol. The only repeated instruction is to merge the two smallest weights. The first two rarest leaves are E and F, each with weight five. Join them under a new node of weight ten. G and H are the next equal pair. Merge their five-percent weights into a second node of weight ten. C and D each have weight ten. Merge those two leaves into a node of weight twenty. The two ten-weight branches made from E through H are now the smallest pair. Their merge produces another weight twenty. Three weights of twenty are available. Ties may be resolved consistently in more than one way. Merge these two compound branches to make forty. B has weight twenty and the compound branch has weight forty. They are the two smallest remaining items, so their parent has weight sixty. Finally merge A, with weight forty, and the remaining weight sixty. Their root has weight one hundred, and the Huffman tree is complete. Assign zero to the upper branch and one to the lower branch at each split. A codeword is the sequence encountered while walking from the root to a leaf. A is reached immediately by code zero, so the most likely symbol costs only one bit. B follows one then zero, so it costs two bits. C and D sit deeper, with codes one one zero zero and one one zero one. Each requires four bits. The four rarest symbols lie one level deeper still. Their codes share the prefix one one one, then use two more bits to select the leaf. No codeword is the beginning of another codeword. That prefix property lets a decoder read the stream from left to right and know exactly when each symbol ends. Compute the average length. A pays one bit forty percent of the time. B pays two bits twenty percent of the time. C and D pay four, and the final four symbols pay five. The Huffman code therefore uses two point six bits per symbol on average. The merging rule has recovered the likelihood-aware question plan, and it has guaranteed that no other binary prefix code has a smaller average length for these individual symbols.

Put the two numbers on one scale. Entropy for our source is about two point five two two bits per symbol. The Huffman code uses two point six. The gap is only point zero seven eight of a bit per symbol. Huffman coding is not merely better than the fixed three-bit code. It is very close to the information-theoretic target. Two questions remain. Why can no lossless prefix code move the green point to the left of entropy? And if the bound is unbeatable, why is Huffman allowed to sit slightly above it? A binary prefix code is a set of nonoverlapping leaves in a binary tree. A codeword of length l occupies one part in two to the l of the tree's capacity. Add those occupied fractions over all symbols. They cannot exceed one. This is the tree-capacity inequality, often called Kraft's inequality. Now compare the actual average length L with entropy H. Their difference can be written as this weighted logarithmic ratio. The log-sum inequality says that weighted ratio is at least minus the log of the tree capacity. Since the capacity is at most one, that quantity is nonnegative. Therefore every binary prefix code has average length at least H. Shorter paths for some outcomes consume more tree capacity and force compensating longer paths elsewhere. The average cannot cross the entropy bound. Entropy supplies ideal lengths such as one point three two two bits. Real codewords have whole-number lengths. Huffman chooses those integers optimally, and its average is always less than one bit above entropy for a memoryless symbol source. When probabilities are exact powers of one half, the ideal lengths are integers and Huffman can meet entropy exactly. Otherwise it rounds through the tree, as our small point zero seven eight gap demonstrates. There is also a way to make the rounding cost per symbol smaller. Encode blocks of symbols together. One possible extra bit is then shared by the whole block rather than charged to every symbol. Now return to files. Typical English text is structured. Spaces and common letters occur more often than rare punctuation, so even the one-byte distribution is uneven. English also has dependencies across positions. After the letters q and u, some next letters are far more plausible than others. Words, phrases, indentation, and repeated substrings create further predictability. A compressor turns that predictability into short descriptions. Huffman coding exploits a probability distribution. More advanced compressors also exploit context, repeated strings, and predictions from earlier data. Independent random bytes are different. Each of the two hundred fifty-six byte values has probability one over two hundred fifty-six, and the next byte is not predicted by the bytes before it. There is no statistical redundancy to exploit. The entropy is eight bits per byte, exactly the size already used by an ordinary byte. There are two hundred fifty-six possible byte values, which is two to the eighth. If they are equally likely, identifying one requires eight bits. For an n-byte file there are two to the eight n possible inputs. There are not enough shorter binary strings to give every input a unique shorter lossless description. Some individual random-looking file may shrink by chance, but most will not, and compressor metadata can make them larger. Already compressed or encrypted files often behave similarly because their byte patterns have been deliberately made difficult to predict. The whole story now fits into four steps. First, a bit is one resolved binary choice. Second, repeated halving says an event of probability p carries about log base two of one over p bits. Averaging that surprise gives entropy. Third, Huffman coding repeatedly merges rare events so likely symbols end near the root. Its integer code lengths approach the entropy limit without ever beating that lower bound. Finally, compression is possible when data contains predictable structure. English supplies redundancy and context. Independent random bytes do not. Entropy measures that difference, and coding turns the available predictability into fewer stored bits.