The laws of text: Zipf and Heaps

1A few words do most of the work

Sort the book's words from the most frequent to the least. A word's place in that list is its rank, r, and the number of times it appears is its frequency, f_r. Each appearance is a token: the book has 404,923 tokens of 14,921 different words. “The”, rank 1, accounts for 20,747 of them, “and”, rank 2, for 16,917, and “though”, rank 100, for 551. In 1949 George Kingsley Zipf observed that in long texts the frequency falls with the rank in the same way, as a power of it:

The constant C sets the scale and the exponent α how fast the frequencies fall; in long texts α is usually close to 1. With α = 1, rank times frequency is the same for every word: a word with ten times the rank appears a tenth as often. Zipf explained it with what he called the principle of least effort. Speaking costs least when the same handy words serve again and again, instead of the exact word for each thing, so a few words end up everywhere and the many words for particular things each turn up rarely.

To fit a word used twenty thousand times and a word used once in one picture, the figure's axes multiply by ten at each step. Drag the red dot along the book's words and watch rank times frequency.

From rank 3 to rank 1,000 the frequency falls from 13,261 to 37, yet the product stays between half and twice 40,000 (its median is 41,124): over that stretch α is close to 1. The law describes the list as a whole, not each word in it. The first word appears about half as often as the rest of the list suggests, and past a few thousand ranks whole runs of words share one small frequency, down to the 5,473 words that appear only once. Section 2 measures α.

2A straight line on log scales

On the figure's axes the words fell close to a straight line, and the law says why. Take logarithms of both sides, in base 10 like the axes:

With x_r = log r and y_r = log f_r, this is a line: its slope is −α, and its height at r = 1, where x_r = 0, is log C. Estimating α and C means finding the line that follows the points best. Least squares takes the line that makes the vertical distances from the points to it, squared and added up, as small as possible, and for a line the answer has a closed form:

Here x and y are the means of the x_r and of the y_r. Squaring makes a large miss count more than two small ones, and treats misses above and below the line alike.

The figure fits the 1,000 most frequent words; the rest of the list is faint. It starts from section 1's guess, α = 1 and C = 40,000. Drag the blue grips to bring the line closer to the red points: the thin red strokes are the distances being squared. Least squares jumps to the best line.

For this book least squares gives α = 1.11 and C = 81,653. Through the middle of the list the line is close: at rank 1,000 it gives 38, where “required” appears 37 times. But it passes far above the first word, 81,653 against the 20,747 of “the”, the unevenness section 1 found at the top of the list.

C and the length of the book

If the law has to account for every token of the book, C is not free: the frequencies of the V different words must add up to n, the number of tokens. That fixes it:

With α = 1 the sum is close to ln V + γ, where γ ≈ 0.577 is a constant. For this book ln 14,921 + 0.577 ≈ 10.19, so C = 404,923 / 10.19 ≈ 39,700: the 40,000 that rank times frequency kept returning to in section 1.

3The vocabulary keeps growing

Now read the book from the start and count the different words met so far. After n tokens the vocabulary has V words, and V grows for as long as there is text: names, rare words and new forms of known words keep turning up. But it grows ever more slowly, as a power of n below 1. This is Heaps' law:

The constant k and the exponent β depend on the text and its language; β is usually between 0.4 and 0.6. On log scales this law is a line too, log V = log k + β log n, so least squares finds β and k as it found α and C. What β means shows when the text doubles:

Twice the text brings 2^β times the words, not twice as many. The figure shows the book's vocabulary as it is read, with Heaps' law fitted to it in blue and, faint, the Spanish original's. Drag the red dot through the book; the ring marks twice as far.

For this translation least squares gives β = 0.52 and k = 18.5, so doubling the text multiplies the vocabulary by about 2^0.52 ≈ 1.43; the counted ratios, from 10,000 tokens on, run from 1.34 to 1.57. The two numbers are tied: a slightly smaller β with a larger k draws nearly the same curve over the book, and with β fixed at 0.5 the best k is 23.7. The Spanish original uses 22,605 different words in fewer tokens, with β = 0.62, because Spanish inflects: a verb takes dozens of forms, and each counts as a different word. The next note is about those forms.

4The tail never runs out

Zipf's law and Heaps' law look at the same thing from two sides. Zipf's law sorts the words by frequency and finds a long tail of rare ones; Heaps' law follows the text and finds new words arriving all along. The new words come from that tail: each stretch of text draws a few words from a list too long to empty. Split the vocabulary met so far by how often each word has been seen, and the words seen once stay a large part of it however far you read.

Drag the red dot along the book and watch the red part of the bar.

After the first 1,000 tokens, 77% of the words met have been seen once; after 100,000, 46%; at the end, 37%. The share falls, but slowly, and new words keep coming: 315 in the 10,000 tokens before token 100,000, and still 155 in the book's last 10,000. A system that learns its vocabulary from one text will meet words it has never seen in the next, a problem later notes return to.

5Summary

The note's formulas next to their NumPy equivalents. tokens holds the book's words in order; n and v hold, at a series of points of the book, the tokens read and the different words met.