Squeezing English
Words by the Numbers
Chapter 9 · Information and Compression
Words by the Numbers 8 ranked words by how much they tell you about a document. This chapter asks a sharper version of the question: how much does each letter tell you, and what is the least space in which English can be written down? The answer is a number measured in bits, it comes from the same counting you have been doing since Words by the Numbers 1, and it explains why a zip file of a novel is so much smaller than the novel. The maths is one logarithm again: the base-2 logarithm, which counts bits.
Surprise, Measured in Bits
Claude Shannon, working at Bell Labs, set out the mathematics of information in his 1948 paper "A Mathematical Theory of Communication" (the year and title are from memory, not from this chapter's searches, so check them). Its starting point is simple. An event that you expected carries little news; an event that you did not expect carries a lot. Shannon measured that news, the surprise of an event with probability p, as -log2(p) bits. A fair coin landing heads has p = 1/2 and so exactly 1 bit of surprise: the answer to one yes/no question. A specific face of a fair die has p = 1/6, and -log2(1/6) = 2.585 bits, a little more than the 2 bits that two yes/no questions can settle and a little less than 3.
The entropy of a whole distribution is the average surprise, each outcome's surprise weighted by how often it happens: H = sum of p * -log2(p). It is the number of bits you need on average to say which outcome occurred, and it is the quantity the rest of the chapter is about. The first snippet works both ideas by hand on coins, dice and cards.
| Distribution | Entropy (bits) | Why |
|---|---|---|
| fair coin | 1.000 | two equally likely outcomes, one yes/no question |
| coin that lands heads 90% | 0.469 | mostly predictable, so little news on average |
| fair die | 2.585 | log2 of 6, the most a six-outcome die can have |
| die with a 50% six | 2.161 | lopsided, so less than the fair die |
| 26 equally likely letters | 4.700 | log2 of 26, the ceiling for a 26-letter alphabet |
The pattern to remember: for a fixed number of outcomes, entropy is highest when they are all equally likely (log2 of the number of outcomes) and falls as the distribution becomes lopsided. English letters are very lopsided. That is the whole reason English can be compressed.
What Is a Letter Worth?
Words by the Numbers 3 counted how often each letter occurs. Those frequencies are probabilities, so the same formula gives the entropy of English letters. A fixed-length code spends the same effort on every symbol: 27 symbols need 5 bits each (log2(27) = 4.755, rounded up because you cannot send part of a bit in a fixed-width code). A variable-length code gives short codes to common symbols and long ones to rare ones, as Morse code does with e and q. David Huffman published a method for building the best such code, in a 1952 paper "A Method for the Construction of Minimum-Redundancy Codes" in Proceedings of the IRE (volume 40, issue 9, pages 1098 to 1101, per the search; the search also said he developed it as a student at MIT). The algorithm is short: repeatedly merge the two least frequent symbols into one, and every merge pushes the symbols inside one level deeper in the code. The second snippet builds it from the letter counts of each book and compares it with the entropy.
| Book | Letter entropy | Huffman average | Word entropy per character |
|---|---|---|---|
| Alice in Wonderland | 4.046 | 4.083 | 1.744 |
| The Time Machine | 4.078 | 4.121 | 1.714 |
| Pride and Prejudice | 4.098 | 4.133 | 1.691 |
| The Federalist Papers | 4.080 | 4.116 | 1.525 |
Three results. First, the entropy of a single letter in these books is about 4.05 to 4.10 bits, against 4.755 if all 27 symbols were equally likely and 5 for a fixed-length code, so just knowing the letter frequencies saves about 18 to 19% on the fixed code. Second, Huffman's code comes within 0.05 bits of the entropy in every book (it is never more than one bit per symbol above it, a standard result I did not check against a source: check). The space gets 2 or 3 bits, e 3 bits and z 10, which is the same ordering as the surprise values you will compute in Exercise 1. Third, treating whole words as the symbols gives a much smaller figure, 1.5 to 1.7 bits per character. That number is a trap. It is the entropy of each book's own word counts, and it ignores the cost of describing the vocabulary itself; with thousands of words seen only once, such a plug-in estimate comes out too low, and the word list would have to be sent to the reader as well. It is not a fair estimate of the entropy of English.
Shannon's Guessing Game
Letter frequencies ignore context: after a q the next letter is nearly always u, which a single-letter count cannot see. Words by the Numbers 5 used the previous word to predict the next; the same idea works for letters, and Shannon turned it into an experiment. In his 1951 paper "Prediction and Entropy of Printed English" (Bell System Technical Journal, volume 30, number 1, pages 50 to 64, per the search), people were shown some text and asked to guess the next letter, then the next, and so on. The number of guesses a person needs says how predictable the text is: if the first guess is usually right, the text carries little information per letter. The sources I could read agree on the broad picture. Statistics over up to eight letters gave about 2.3 bits per letter, and allowing for structure up to about 100 letters pushed the estimate down to around one bit per letter, which means English is about 75% redundant. They do not agree on the exact range: one secondary summary gave a bound of 0.6 to 1.3 bits and another gave 1.0 to 1.5, and a third summary of a replication study was garbled enough that I could not tell the direction of its comparison. I therefore say only "roughly one bit per letter, give or take". Shannon also converted a word-level calculation into about 2.62 bits per letter; that figure comes from the same search and I did not check it in the paper.
The next snippet plays the game with a machine instead of a person. A model trained on text sees the previous k characters, ranks all 27 symbols from most to least likely, and we count how far down the list the true next character sits. It also reports the cross-entropy in bits per character: the average surprise when the model's probabilities are used on text it was not trained on. For the first table the model is trained on the first half of a book and tested on the second half; for the second, trained on three books and tested on the fourth. The smoothing constant (0.1, added to every count so an unseen next letter does not get probability zero) is my arbitrary choice.
| Book (second half) | No context | 1 character | 2 characters | 3 characters |
|---|---|---|---|---|
| Alice in Wonderland | 4.054 | 3.237 | 2.589 | 2.262 |
| The Time Machine | 4.077 | 3.281 | 2.683 | 2.325 |
| Pride and Prejudice | 4.096 | 3.307 | 2.595 | 2.041 |
| The Federalist Papers | 4.077 | 3.230 | 2.468 | 1.877 |
Each extra character of context takes a large bite out of the surprise: from about 4.1 bits with no context to between 1.9 and 2.3 with three characters. The guessing results say the same in plainer words. With two characters of context, the machine's first guess is right about 38 to 40% of the time, and it needs 3.7 to 3.9 guesses on average, out of a possible 27. These figures are not comparable with Shannon's one bit, because his readers could use whole words, grammar and meaning over spans of up to about 100 letters, and my model sees at most three characters. Two cautions about my own numbers. The order-3 figures differ a lot between books (1.88 to 2.33); I did not investigate why. And more context is not always better: with a fixed amount of training text, long contexts are mostly unseen and the smoothing does the work, so the curve eventually turns upward (this was not tested here beyond three characters).
How Much Can English Be Squeezed?
Everything so far is a bound or a model. A compressor is the working version: it turns text into fewer bits and turns them back again. Whatever size it reaches is an upper bound on what the text's entropy rate can be, because it is a scheme that really works. The last snippet runs three compressors from Python's standard library over each book, and over four controls: the same letters shuffled (destroying everything but letter frequencies), a random string of 27 symbols (nothing to find), and a thousand characters repeated a hundred times (almost nothing but repetition). Sizes are in bits per character of the cleaned text, so 8 would mean no better than storing one byte per character.
| Book | Letter entropy | zlib | lzma | bz2 |
|---|---|---|---|---|
| Alice in Wonderland | 4.05 | 2.60 | 2.31 | 2.08 |
| The Time Machine | 4.08 | 2.85 | 2.53 | 2.26 |
| Pride and Prejudice | 4.10 | 2.66 | 2.16 | 1.87 |
| The Federalist Papers | 4.08 | 2.43 | 1.87 | 1.69 |
| Text | What the compressor can use | zlib / bz2 / lzma (bits per character) |
|---|---|---|
| first 100,000 characters of one book | letter frequencies, words, repeated phrases | 2.64 / 2.15 / 2.39 |
| the same letters shuffled | letter frequencies only | 4.73 / 4.46 / 4.21 |
| random 27-symbol string | nothing | 5.29 / 4.84 / 4.91 |
| 1,000 characters repeated 100 times | exact repetition | 0.08 / 0.10 / 0.05 |
Read the controls first, because they show what the compressors are finding. Shuffling the letters leaves them near the single-letter entropy (about 4.1, and lzma got to 4.21), so the gap between 4.2 and 2.4 on real text is the value of ordering: words, spelling and repeated phrases. The random string cannot be squeezed below its entropy of 4.755 and the compressors do not manage it: zlib needs 5.29 bits per character, more than the plain 5-bit code, because its bookkeeping costs more than it saves when there is nothing to find. At the other extreme, a text that is just repetition shrinks to under a tenth of a bit per character. On real books the three tools land between 1.7 and 2.9 bits per character, that is 64% to 79% smaller than a byte per character. bz2 and lzma beat the order-3 figure for Alice in Wonderland, zlib did not, and all three are a long way from Shannon's one bit, which hints at what is still left in the structure of English, and why modern language models, which predict text from long contexts, are also compressors in disguise (I am stating that last link from general knowledge, not from a source I checked). One more warning on comparing columns: the cross-entropy figures earlier were measured on held-out halves, while the compressors were measured on whole books, so the two groups are close cousins, not a fair race.
| Method | Context it uses | Alice in Wonderland (bits per character) |
|---|---|---|
| fixed-length code | none | 5.00 |
| letter entropy (Huffman, 4.08) | none, just letter counts | 4.05 |
| order-2 model, held-out half | previous 2 characters | 2.59 |
| order-3 model, held-out half | previous 3 characters | 2.26 |
| zlib / lzma / bz2, whole book | repeats over the whole text | 2.60 / 2.31 / 2.08 |
| Shannon's human readers (1951) | meaning and long range | roughly 1 (see the conflict above) |
log instead of log2 and getting nats or a different scale; including a symbol with probability zero in the sum (0 * log 0 is undefined, so skip it); testing a model on the text it was trained on, which flatters it badly; quoting one entropy number for "English" without saying the symbols, the cleaning and the context length; trusting a word-level entropy computed from one text's own counts; comparing compressors on different inputs, or on a file too small for the compressor's overhead to be ignored; and forgetting that a smoothing constant or a context length is a choice that moves the answer.
For Pride and Prejudice cleaned to a-z and spaces, print the surprise of every symbol, show the three least and three most surprising ones, and confirm that the frequency-weighted average of the surprises is the entropy. Then compare the surprise of u anywhere with the surprise of u straight after q. What does the difference tell you about context?
📄 View solutionBuild a real Huffman code for the letters of Alice in Wonderland, encode the first 20,000 characters into a string of 0s and 1s, decode it back, and check you recover the original. Report the bits per character and compare it with the entropy and with a fixed 5-bit code. Why can the code be decoded without separators between symbols?
📄 View solutionPlay Shannon's guessing game with a machine that has read only the other three books. For context lengths 0 to 3 print the average number of guesses needed on Alice in Wonderland, then for context length 2 print the number of guesses for each character of a 60-character passage. Where do the long runs of 1s occur, and which letters cost the most guesses?
📄 View solutionQuick Reference
- Surprise:
-math.log2(p)bits for an event of probability p; a fair coin is 1 bit, a fair die face 2.585 - Entropy: the average surprise,
sum(p * -math.log2(p)); highest when outcomes are equally likely (log2(n)), lower when lopsided - Letter entropy: about 4.05 to 4.10 bits per symbol in the four books (27 symbols, uniform would be 4.755, a fixed code 5)
- Huffman code: short codes for common symbols, built by repeatedly merging the two rarest; within 0.05 bits of the entropy here
- Context helps: held-out cross-entropy fell from about 4.1 (no context) to 1.9 to 2.3 bits (three characters); an order-2 model needed 3.7 to 3.9 guesses per character
- Compressors: zlib, lzma and bz2 reached 1.7 to 2.9 bits per character on cleaned book text; shuffled letters stayed near 4.2 to 4.7, random symbols could not be squeezed, and zlib made them bigger than 5 bits
- Shannon 1951: human guessing gave an estimate of roughly one bit per letter (sources conflict on the range, 0.6 to 1.3 in one summary and 1.0 to 1.5 in another)
- Pitfalls: test on held-out text, state the symbol set and context length, and do not use a word entropy computed from a text's own counts as the entropy of English