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.

What was run, and what to trust
Every Python snippet in this chapter and in the three exercise solutions was executed (Python 3.14.0), and the output in the comments is what Python printed. The four books are plain-text files from Project Gutenberg (eBook numbers 11, 35, 1342 and 1404), which the code downloads once and saves next to the script; you need an internet connection the first time. For the information measures the text is cleaned to 27 symbols, the letters a to z and a single space, so punctuation, capitals and digits are thrown away; numbers for real files with punctuation would differ. The probabilities in the first snippet (such as the 90% chance of rain) are invented, illustrative numbers. The compression numbers use the Python standard-library modules zlib, bz2 and lzma at the settings shown, and other compressors would give other figures. The history comes from two web searches that returned summaries of web pages; such fetched pages are often truncated or model-summarised, so treat the wording as a paraphrase. The searches supported the journal, volume, pages and date of Shannon's prediction paper and the date and journal of Huffman's coding paper, and they showed a source conflict about Shannon's final estimate, noted below. Statements marked (check) were not confirmed against a source.

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.

import math def surprise(p): return -math.log2(p) # bits of surprise for an event of probability p def entropy(probs): return sum(p * surprise(p) for p in probs if p > 0) print("surprise of single events (bits):") for label, p in [("fair coin lands heads", 1/2), ("one specific die face", 1/6), ("one specific card from 52", 1/52), ("rain tomorrow (invented p = 0.9)", 0.9)]: print(f" {label:34} p {p:.3f} surprise {surprise(p):.3f}") print("entropy of whole distributions (bits):") for label, probs in [("fair coin", [0.5, 0.5]), ("coin that lands heads 90%", [0.9, 0.1]), ("fair die", [1/6] * 6), ("die with a 50% six", [0.1] * 5 + [0.5]), ("26 equally likely letters", [1/26] * 26)]: print(f" {label:28} {entropy(probs):.3f}") # surprise of single events (bits): # fair coin lands heads p 0.500 surprise 1.000 # one specific die face p 0.167 surprise 2.585 # one specific card from 52 p 0.019 surprise 5.700 # rain tomorrow (invented p = 0.9) p 0.900 surprise 0.152 # entropy of whole distributions (bits): # fair coin 1.000 # coin that lands heads 90% 0.469 # fair die 2.585 # die with a 50% six 2.161 # 26 equally likely letters 4.700
DistributionEntropy (bits)Why
fair coin1.000two equally likely outcomes, one yes/no question
coin that lands heads 90%0.469mostly predictable, so little news on average
fair die2.585log2 of 6, the most a six-outcome die can have
die with a 50% six2.161lopsided, so less than the fair die
26 equally likely letters4.700log2 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.

import heapq, math, pathlib, re, urllib.request from collections import Counter BOOKS = {"Alice in Wonderland": 11, "The Time Machine": 35, "Pride and Prejudice": 1342, "The Federalist Papers": 1404} def load(number): path = pathlib.Path(f"pg{number}.txt") if not path.exists(): # download once, then reuse the saved copy url = f"https://www.gutenberg.org/cache/epub/{number}/pg{number}.txt" req = urllib.request.Request(url, headers={"User-Agent": "Mozilla/5.0"}) path.write_bytes(urllib.request.urlopen(req).read()) raw = path.read_text(encoding="utf-8-sig").replace("\r", "") start = raw.index("\n", raw.index("*** START OF")) + 1 return raw[start:raw.index("*** END OF")] def clean(text): # 27 symbols: a-z and one space return re.sub(r"[^a-z]+", " ", text.lower()).strip() def entropy(counts): total = sum(counts.values()) return -sum(c / total * math.log2(c / total) for c in counts.values()) def huffman_lengths(counts): # code length (bits) for each symbol heap = [(c, i, [s]) for i, (s, c) in enumerate(counts.items())] heapq.heapify(heap) depth = {s: 0 for s in counts} n = len(heap) while len(heap) > 1: c1, _, a = heapq.heappop(heap) c2, _, b = heapq.heappop(heap) for s in a + b: depth[s] += 1 # every merge pushes its symbols one level deeper n += 1 heapq.heappush(heap, (c1 + c2, n, a + b)) return depth print(f"fixed-length code for 27 symbols: 5 bits per character; log2(27) = {math.log2(27):.3f}") for title, number in BOOKS.items(): text = clean(load(number)) letters = Counter(text) lengths = huffman_lengths(letters) avg = sum(letters[s] * lengths[s] for s in letters) / len(text) words = text.split() wc = Counter(words) print(f"{title}") print(f" characters {len(text):,} letter entropy {entropy(letters):.3f} bits Huffman average {avg:.3f} bits") print(f" space {lengths[' ']} bits, e {lengths['e']} bits, z {lengths['z']} bits") print(f" word entropy {entropy(wc):.2f} bits per word, {entropy(wc) * len(words) / len(text):.3f} bits per character") # fixed-length code for 27 symbols: 5 bits per character; log2(27) = 4.755 # Alice in Wonderland # characters 135,508 letter entropy 4.046 bits Huffman average 4.083 bits # space 2 bits, e 3 bits, z 10 bits # word entropy 8.62 bits per word, 1.744 bits per character # The Time Machine # characters 174,220 letter entropy 4.078 bits Huffman average 4.121 bits # space 2 bits, e 3 bits, z 10 bits # word entropy 9.08 bits per word, 1.714 bits per character # Pride and Prejudice # characters 692,488 letter entropy 4.098 bits Huffman average 4.133 bits # space 3 bits, e 3 bits, z 10 bits # word entropy 9.11 bits per word, 1.691 bits per character # The Federalist Papers # characters 1,122,155 letter entropy 4.080 bits Huffman average 4.116 bits # space 3 bits, e 3 bits, z 10 bits # word entropy 8.90 bits per word, 1.525 bits per character
BookLetter entropyHuffman averageWord entropy per character
Alice in Wonderland4.0464.0831.744
The Time Machine4.0784.1211.714
Pride and Prejudice4.0984.1331.691
The Federalist Papers4.0804.1161.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.

import math, pathlib, re, urllib.request from collections import Counter, defaultdict BOOKS = {"Alice in Wonderland": 11, "The Time Machine": 35, "Pride and Prejudice": 1342, "The Federalist Papers": 1404} ALPHABET = " abcdefghijklmnopqrstuvwxyz" def load(number): path = pathlib.Path(f"pg{number}.txt") if not path.exists(): # download once, then reuse the saved copy url = f"https://www.gutenberg.org/cache/epub/{number}/pg{number}.txt" req = urllib.request.Request(url, headers={"User-Agent": "Mozilla/5.0"}) path.write_bytes(urllib.request.urlopen(req).read()) raw = path.read_text(encoding="utf-8-sig").replace("\r", "") start = raw.index("\n", raw.index("*** START OF")) + 1 return raw[start:raw.index("*** END OF")] def clean(text): # 27 symbols: a-z and one space return re.sub(r"[^a-z]+", " ", text.lower()).strip() def train(text, k): # counts of the next character after each k-character context model = defaultdict(Counter) for i in range(k, len(text)): model[text[i - k:i]][text[i]] += 1 return model def cross_entropy(model, text, k, alpha=0.1): # average bits per character on text the model has not seen bits = 0.0 for i in range(k, len(text)): c = model.get(text[i - k:i], Counter()) p = (c[text[i]] + alpha) / (sum(c.values()) + alpha * 27) bits -= math.log2(p) return bits / (len(text) - k) texts = {title: clean(load(n)) for title, n in BOOKS.items()} print("bits per character on the second half of each book, model trained on the first half:") for title, text in texts.items(): half = len(text) // 2 row = [] for k in range(4): # order k = the previous k characters as context row.append(f"order {k}: {cross_entropy(train(text[:half], k), text[half:], k):.3f}") print(f" {title:22}", " ".join(row)) # Shannon's guessing game, played by a machine: guess the most likely character first, # then the next most likely, and count the guesses needed. Train on three books, test on the fourth. print("guesses needed per character (order 2 model, tested on a book it has never seen):") for held_out in BOOKS: pool = "".join(t for title, t in texts.items() if title != held_out) model = train(pool, 2) overall = Counter(pool) tally = Counter() test = texts[held_out] for i in range(2, len(test)): c = model.get(test[i - 2:i], Counter()) order = sorted(ALPHABET, key=lambda ch: (-c[ch], -overall[ch])) tally[order.index(test[i]) + 1] += 1 n = sum(tally.values()) average = sum(g * v for g, v in tally.items()) / n print(f" {held_out:22} 1st guess right {tally[1] / n:.1%}, within 3 guesses {sum(tally[g] for g in (1, 2, 3)) / n:.1%}, average {average:.2f} guesses") # bits per character on the second half of each book, model trained on the first half: # Alice in Wonderland order 0: 4.054 order 1: 3.237 order 2: 2.589 order 3: 2.262 # The Time Machine order 0: 4.077 order 1: 3.281 order 2: 2.683 order 3: 2.325 # Pride and Prejudice order 0: 4.096 order 1: 3.307 order 2: 2.595 order 3: 2.041 # The Federalist Papers order 0: 4.077 order 1: 3.230 order 2: 2.468 order 3: 1.877 # guesses needed per character (order 2 model, tested on a book it has never seen): # Alice in Wonderland 1st guess right 39.3%, within 3 guesses 66.3%, average 3.73 guesses # The Time Machine 1st guess right 38.2%, within 3 guesses 64.5%, average 3.79 guesses # Pride and Prejudice 1st guess right 38.0%, within 3 guesses 64.5%, average 3.86 guesses # The Federalist Papers 1st guess right 39.8%, within 3 guesses 65.8%, average 3.70 guesses
Book (second half)No context1 character2 characters3 characters
Alice in Wonderland4.0543.2372.5892.262
The Time Machine4.0773.2812.6832.325
Pride and Prejudice4.0963.3072.5952.041
The Federalist Papers4.0773.2302.4681.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.

import bz2, lzma, math, pathlib, random, re, urllib.request, zlib from collections import Counter BOOKS = {"Alice in Wonderland": 11, "The Time Machine": 35, "Pride and Prejudice": 1342, "The Federalist Papers": 1404} def load(number): path = pathlib.Path(f"pg{number}.txt") if not path.exists(): # download once, then reuse the saved copy url = f"https://www.gutenberg.org/cache/epub/{number}/pg{number}.txt" req = urllib.request.Request(url, headers={"User-Agent": "Mozilla/5.0"}) path.write_bytes(urllib.request.urlopen(req).read()) raw = path.read_text(encoding="utf-8-sig").replace("\r", "") start = raw.index("\n", raw.index("*** START OF")) + 1 return raw[start:raw.index("*** END OF")] def clean(text): # 27 symbols: a-z and one space return re.sub(r"[^a-z]+", " ", text.lower()).strip() def entropy(text): counts = Counter(text) return -sum(c / len(text) * math.log2(c / len(text)) for c in counts.values()) def bits_per_char(data): raw = data.encode("ascii") return {"zlib": len(zlib.compress(raw, 9)) * 8 / len(data), "bz2": len(bz2.compress(raw, 9)) * 8 / len(data), "lzma": len(lzma.compress(raw)) * 8 / len(data)} print("compressed size in bits per character (a-z and spaces only; 8 bits = no saving over ASCII):") for title, number in BOOKS.items(): text = clean(load(number)) sizes = bits_per_char(text) print(f" {title:22} letter entropy {entropy(text):.2f} " + " ".join(f"{k} {v:.2f}" for k, v in sizes.items())) # Controls: text with no English structure, and text with a lot of repetition random.seed(1) text = clean(load(11))[:100_000] controls = { "first 100,000 characters of one book": text, "the same letters shuffled": "".join(random.sample(text, len(text))), "random 27-symbol string": "".join(random.choice(" abcdefghijklmnopqrstuvwxyz") for _ in text), "first 1,000 characters repeated 100 times": text[:1000] * 100, } print("controls, bits per character:") for label, data in controls.items(): sizes = bits_per_char(data) print(f" {label:42} " + " ".join(f"{k} {v:.2f}" for k, v in sizes.items())) print(f" (log2 of 27 = {math.log2(27):.2f} is the floor for the random string)") # compressed size in bits per character (a-z and spaces only; 8 bits = no saving over ASCII): # Alice in Wonderland letter entropy 4.05 zlib 2.60 bz2 2.08 lzma 2.31 # The Time Machine letter entropy 4.08 zlib 2.85 bz2 2.26 lzma 2.53 # Pride and Prejudice letter entropy 4.10 zlib 2.66 bz2 1.87 lzma 2.16 # The Federalist Papers letter entropy 4.08 zlib 2.43 bz2 1.69 lzma 1.87 # controls, bits per character: # first 100,000 characters of one book zlib 2.64 bz2 2.15 lzma 2.39 # the same letters shuffled zlib 4.73 bz2 4.46 lzma 4.21 # random 27-symbol string zlib 5.29 bz2 4.84 lzma 4.91 # first 1,000 characters repeated 100 times zlib 0.08 bz2 0.10 lzma 0.05 # (log2 of 27 = 4.75 is the floor for the random string)
BookLetter entropyzliblzmabz2
Alice in Wonderland4.052.602.312.08
The Time Machine4.082.852.532.26
Pride and Prejudice4.102.662.161.87
The Federalist Papers4.082.431.871.69
TextWhat the compressor can usezlib / bz2 / lzma (bits per character)
first 100,000 characters of one bookletter frequencies, words, repeated phrases2.64 / 2.15 / 2.39
the same letters shuffledletter frequencies only4.73 / 4.46 / 4.21
random 27-symbol stringnothing5.29 / 4.84 / 4.91
1,000 characters repeated 100 timesexact repetition0.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.

MethodContext it usesAlice in Wonderland (bits per character)
fixed-length codenone5.00
letter entropy (Huffman, 4.08)none, just letter counts4.05
order-2 model, held-out halfprevious 2 characters2.59
order-3 model, held-out halfprevious 3 characters2.26
zlib / lzma / bz2, whole bookrepeats over the whole text2.60 / 2.31 / 2.08
Shannon's human readers (1951)meaning and long rangeroughly 1 (see the conflict above)
Common mistakes
Treating a bit as a unit of meaning rather than of surprise (entropy measures unpredictability, not importance: a random string has the highest entropy of all); using 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.
Exercise 1

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 solution
Exercise 2

Build 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 solution
Exercise 3

Play 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 solution

Quick 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
Coming next
Words by the Numbers 10 is the capstone, a text detective: combining the tools to identify the language, author and topic of mystery passages.