Neighbouring Words

Words by the Numbers

Chapter 4 · Neighbouring Words

Words by the Numbers 3 ended by saying that real language identifiers look at groups of letters, not single ones. The same step works for words: stop counting words one at a time and count the pairs and triples that sit next to each other. Some pairs are just common words that happen to be common (of the); others are pairs that stick together far more than their parts would explain (floating point). Telling the two apart is the whole chapter. The maths is light: multiplication, division, a square root and a base-2 logarithm, all done by Python.

What was run, and what to trust

Every Python snippet in this chapter and in the three exercise solutions was executed (Python 3.14), and the output in the comments is what Python printed. The real text counted is the reference documentation that ships inside Python (the pydoc_data.topics module), about 74,500 word tokens of technical English; it is not typical prose, and its counts change a little between Python versions, so expect small differences on your machine. Word pairs never cross from one documentation topic into the next. The tiny sentences in the first snippet and in Exercise 1 are invented, illustrative examples. Background facts come from web searches that returned summaries of web pages; such fetched pages are often truncated or model-summarised, so treat the wording as a paraphrase. A search confirmed the details of the Church and Hanks paper and the low-frequency weakness of the association score used below; it did not return anything on Firth or Halliday, so those two attributions are my recollection and are marked (check). Statements marked (check) were not confirmed against a source.

Pairs and Triples of Words

A bigram is two neighbouring words, a trigram is three, and the general name is n-gram. Making them takes one trick: line the list of words up against itself shifted by one place, and zip the two lists together. A text of n words has n − 1 bigrams and n − 2 trigrams, because the last word has no right-hand neighbour.

from collections import Counter

text = "the cat sat on the mat and the cat saw the dog"
words = text.split()
bigrams = list(zip(words, words[1:]))
trigrams = list(zip(words, words[1:], words[2:]))
print(len(words), "words,", len(bigrams), "bigrams,", len(trigrams), "trigrams")
print(bigrams[:4])
print(trigrams[:3])
print(Counter(bigrams).most_common(2))
# 12 words, 11 bigrams, 10 trigrams
# [('the', 'cat'), ('cat', 'sat'), ('sat', 'on'), ('on', 'the')]
# [('the', 'cat', 'sat'), ('cat', 'sat', 'on'), ('sat', 'on', 'the')]
# [(('the', 'cat'), 2), (('cat', 'sat'), 1)]
    

The sentence has 12 words, so 11 bigrams and 10 trigrams. the cat is the commonest bigram, with a count of 2, because the cat turns up twice. Everything else about n-grams is this same idea scaled up, so the real question is what the counts tell you.

The Commonest Pairs Are Dull

Run the same idea over the whole documentation text. The snippet builds word, bigram and trigram counts, prints how many different bigrams and trigrams there are, how many appear only once, and the top few of each.

import re
from collections import Counter
from pydoc_data.topics import topics

def tokens(text):
    return re.findall(r"[a-z]+(?:'[a-z]+)?", text.lower())

uni, bi, tri = Counter(), Counter(), Counter()
for doc in topics.values():          # n-grams never cross from one document to the next
    w = tokens(doc)
    uni.update(w)
    bi.update(zip(w, w[1:]))
    tri.update(zip(w, w[1:], w[2:]))
N = sum(uni.values())
print("tokens:", N, "| distinct bigrams:", len(bi), "| distinct trigrams:", len(tri))
print("bigrams seen once:", f"{sum(1 for c in bi.values() if c == 1) / len(bi):.0%}",
      "| trigrams seen once:", f"{sum(1 for c in tri.values() if c == 1) / len(tri):.0%}")
print("top bigrams: ", [(" ".join(g), c) for g, c in bi.most_common(8)])
print("top trigrams:", [(" ".join(g), c) for g, c in tri.most_common(6)])
# tokens: 74538 | distinct bigrams: 27520 | distinct trigrams: 46967
# bigrams seen once: 53% | trigrams seen once: 66%
# top bigrams:  [('of the', 532), ('in the', 447), ('to the', 225), ('if the', 209), ('in version', 205), ('can be', 193), ('it is', 171), ('the same', 168)]
# top trigrams: [('changed in version', 128), ('self other object', 80), ('added in version', 74), ('the built in', 55), ('can be used', 43), ('is equivalent to', 36)]
    

The top bigrams are the pairs you would predict from Words by the Numbers 2: small grammatical words next to each other (of the, in the, to the). The documentation also shows its own habits: in version and changed in version come from the repeated notes of the form “Changed in version 3.x” (the version text is my reading of the output; check). Notice the last point about sparsity: 53% of the bigrams, and 66% of the trigrams, occur exactly once. The more words you glue together, the more of the possible combinations you have never seen.

Unit	Distinct kinds	Seen only once
Words	thousands (Words by the Numbers 2)	a large share of the kinds (check)
Bigrams	27,520	53%
Trigrams	46,967	66%

Collocations

A collocation is a pair (or longer group) of words that go together more than their meanings alone would require. The idea has a famous slogan, usually credited to the British linguist J. R. Firth: you shall know a word by the company it keeps (my recollection; the exact wording and year not confirmed; check). A standard textbook illustration, usually credited to M. A. K. Halliday, is that English speakers say strong tea and heavy rain, but not powerful tea (also from memory; check). Nothing in the meaning of strong forbids strong rain; it is simply not what people say. Dictionary makers care about this, and in 1990 Kenneth Church and Patrick Hanks published a paper in Computational Linguistics (volume 16, pages 22 to 29, per the search result) proposing to estimate such word associations automatically from large text collections, using a measure based on mutual information. That measure is the one coming up.

More Than Chance

To say a pair is “more than chance” you need a figure for chance. Suppose the words were shuffled into random order. Word a makes up a share c(a) ÷ N of the text and word b makes up c(b) ÷ N, so the pair a b should turn up about c(a) × c(b) ÷ N times, the expected count. Compare it with the count actually seen. The usual way to compare is a ratio on a log scale, pointwise mutual information (PMI): log₂(seen ÷ expected). A PMI of 0 means chance, 1 means twice as often as chance, 2 four times, and so on.

import math, re
from collections import Counter
from pydoc_data.topics import topics

def tokens(text):
    return re.findall(r"[a-z]+(?:'[a-z]+)?", text.lower())

uni, bi = Counter(), Counter()
for doc in topics.values():
    w = tokens(doc)
    uni.update(w)
    bi.update(zip(w, w[1:]))
N = sum(uni.values())

def pmi(pair):
    a, b = pair
    expected = uni[a] * uni[b] / N        # pairs expected if words were shuffled
    return math.log2(bi[pair] / expected)

for pair in [("of", "the"), ("in", "the"), ("is", "a")]:
    a, b = pair
    print(f"{' '.join(pair):7} seen {bi[pair]:5d} | expected {uni[a] * uni[b] / N:7.1f} | PMI {pmi(pair):5.2f}")
for floor in (1, 5, 30):
    ranked = sorted((p for p in bi if bi[p] >= floor), key=pmi, reverse=True)[:5]
    print(f"min count {floor:2d}:", [(" ".join(p), bi[p], round(pmi(p), 1)) for p in ranked])
# of the  seen   532 | expected   109.0 | PMI  2.29
# in the  seen   447 | expected   108.8 | PMI  2.04
# is a    seen   162 | expected    59.8 | PMI  1.44
# min count  1: [('generation phase', 1, 16.2), ('fstring tstring', 1, 16.2), ('pyarg parsetuple', 1, 16.2), ('invariants lexicographical', 1, 16.2), ('raymond hettinger', 1, 16.2)]
# min count  5: [('latin capital', 5, 13.9), ('post mortem', 7, 13.4), ('triple quoted', 9, 12.7), ('logical flow', 5, 12.7), ('third party', 5, 12.6)]
# min count 30: [('floating point', 36, 9.8), ('e g', 51, 8.6), ('finally clause', 32, 8.2), ('except clause', 48, 7.4), ('type params', 32, 7.4)]
    

Even of the beats chance: 532 seen against about 109 expected, a ratio near 4.9 (PMI 2.29). That makes sense, because English grammar does put the after of more often than a shuffle would. The more important lesson is in the last three lines. With no minimum count, the top five pairs all have a PMI of 16.2 and each was seen once, and that is not a coincidence: a pair seen once between two words that each appear once has PMI log₂(N), and log₂(74,538) is about 16.2. Those are rare words, not collocations. Raising the minimum count to 5 gives latin capital, post mortem and triple quoted; at 30 it gives floating point, finally clause and except clause, which really are the kind of fixed phrase you hoped to find. The search I ran says the same thing about PMI in general: it tends to favour low-frequency events, so it is usually paired with a frequency threshold.

Minimum count	Top pair found	What it shows
1	generation phase (seen once, PMI 16.2)	rare words sitting together by accident
5	latin capital (seen 5 times, PMI 13.9)	real phrases, but narrow ones
30	floating point (seen 36 times, PMI 9.8)	established technical phrases

Does a Shuffle Agree?

The expected count is an arithmetic shortcut. You can also test it directly: shuffle the words inside each documentation topic, count the pairs again, and see what a text without word order produces. If floating point really is a phrase, shuffled text should almost never produce it. The same snippet also computes a second score, the t-score: (seen − expected) ÷ √seen. It rewards pairs that are both clearly above chance and frequent, so it needs no hand-picked minimum beyond a small floor of 5.

import math, random, re
from collections import Counter
from pydoc_data.topics import topics

def tokens(text):
    return re.findall(r"[a-z]+(?:'[a-z]+)?", text.lower())

docs = [tokens(doc) for doc in topics.values()]
uni, real = Counter(), Counter()
for w in docs:
    uni.update(w)
    real.update(zip(w, w[1:]))
N = sum(uni.values())

random.seed(1)
shuffled = Counter()
for w in docs:
    w = w[:]
    random.shuffle(w)                  # same words, order destroyed
    shuffled.update(zip(w, w[1:]))

print("pair             real  shuffled")
for pair in [("of", "the"), ("in", "the"), ("floating", "point"), ("except", "clause")]:
    print(f"{' '.join(pair):15} {real[pair]:5d} {shuffled[pair]:9d}")

def t_score(pair):
    expected = uni[pair[0]] * uni[pair[1]] / N
    return (real[pair] - expected) / math.sqrt(real[pair])

top = sorted((p for p in real if real[p] >= 5), key=t_score, reverse=True)[:8]
print("t-score top:", [(" ".join(p), real[p], round(t_score(p), 1)) for p in top])
# pair             real  shuffled
# of the            532       112
# in the            447       109
# floating point     36         0
# except clause      48         3
# t-score top: [('of the', 532, 18.3), ('in the', 447, 16.0), ('in version', 205, 14.0), ('can be', 193, 13.7), ('it is', 171, 12.1), ('the same', 168, 12.0), ('is not', 167, 11.8), ('changed in', 128, 11.1)]
    

A shuffle (one seed, so one run, not an average) makes of the 112 times, close to the expected 109, and floating point zero times against 36 in the real text. The t-score list is almost the opposite of the PMI list: it is topped by of the, in the and in version, because those are frequent and reliably above chance, while PMI preferred rare, tightly bound pairs. Neither is wrong; they answer different questions.

Score	Favours	Top of the list here
Raw count	common words next to each other	of the, in the, to the
PMI	tightly bound but rare pairs; needs a minimum count	floating point, finally clause (minimum 30)
t-score	frequent pairs clearly above chance	of the, in the, in version

Common mistakes

Forgetting that the last word of a text has no right-hand neighbour (n words give n − 1 bigrams); letting pairs run across the boundary between two unrelated documents; ranking by PMI with no minimum count and getting a list of rare words; treating a high raw count as proof of a collocation when it may only be two common words; and reading “above chance” as “meaningful”, since of the beats chance without being a phrase anyone would put in a dictionary.

Exercise 1

Write a short invented passage of your own (two sentences). Build its bigrams and trigrams, then print how many words, bigrams and trigrams it has, how many bigrams are distinct, the commonest bigrams, and every word that follows one chosen word.

📄 View solution

Exercise 2

On the documentation text, print the six commonest bigrams by raw count, then the six commonest that contain none of a list of small common words, then the six best by PMI among pairs seen at least 10 times. Which list looks most like a list of phrases?

📄 View solution

Exercise 3

Shuffle the words inside each documentation topic twenty times, with a different random seed each time. For four chosen pairs, report the real count, the highest count any shuffle produced, and how many shuffles matched or beat the real count.

📄 View solution

Quick Reference

Bigrams, trigrams: zip(words, words[1:]) and zip(words, words[1:], words[2:]); n words give n − 1 and n − 2
Sparsity: longer n-grams repeat less (here 53% of bigrams and 66% of trigrams were seen once)
Expected count of a pair: count(a) * count(b) / N
PMI: math.log2(seen / expected); 0 is chance, 1 is twice chance; always set a minimum count
t-score: (seen - expected) / math.sqrt(seen); favours frequent pairs
Shuffle test: random.shuffle(words) inside each document, then recount
Caution: a pair above chance is not necessarily a phrase; look at the list yourself

Coming next

Words by the Numbers 5 is about Markov text: predicting the next word, building a Markov chain generator, and why its output sounds almost right.