Important Words

Words by the Numbers

Chapter 8 · What Makes a Word Important

Words by the Numbers 7 scored how hard a text is to read. This chapter asks which words in a text matter. The most frequent words are almost never the answer: the tops nearly every count, as Words by the Numbers 2 showed, and tells you nothing about a text. What you want is a word that is frequent here and rare elsewhere. Putting those two ideas into one number gives TF-IDF, the weighting behind keyword extraction and a good deal of classic search. The maths is one logarithm and one multiplication, and by the end you will have a working search ranker in a few dozen lines.

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. Everything between the Gutenberg start and end markers is used, so title pages, contents lists and illustration markers are in the data (one of them shows up as a "keyword" in Exercise 2). The four mini-documents in the first snippet are invented, illustrative examples, and so are the search queries, which I chose, together with the book I expected each to come from. The tokeniser is a simple lower-casing regular expression, so other tokenisers would give different counts. The history comes 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. The searches supported the title, journal and date of the 1972 paper that introduced inverse document frequency; they supported Luhn's role only through one explainer page, and they showed one source conflict, noted below. Statements marked (check) were not confirmed against a source.

Frequent Here, Rare Elsewhere

The idea of weighting a word by how few documents contain it comes from Karen Spärck Jones. Her paper "A statistical interpretation of term specificity and its application in retrieval" appeared in the Journal of Documentation in 1972 (volume 28, pages 11 to 21, per the search). It counted the documents in a collection that contain a term and gave rare terms more weight; the name inverse document frequency came later. One explainer page credits the other half of the recipe, counting how often a term occurs in a document, to Hans Peter Luhn of IBM in the 1950s (the date 1957 appeared in my query, not in a page I could read, and only that one page mentioned Luhn, so check it). Search engines went on to refine the weighting. A family of formulas called BM25, from the Okapi system at City University London, is a descendant; the sources conflict on the date, giving 1994 in some places and 1995 in others, so I leave it at "mid 1990s". I did not check how modern search engines are built beyond that.

The Maths, Worked by Hand

Take a collection of N documents. For a word in one document, three numbers matter.

tf, the term frequency: how many times the word occurs in the document, divided by the document's length in words (dividing makes long and short documents comparable).
df, the document frequency: how many documents contain the word at least once.
idf, the inverse document frequency: ln(N / df), the natural logarithm of N divided by df. A word in every document has ln(1) = 0; a word in one of four documents has ln(4) = 1.386.

The score is tf × idf. The logarithm is there so that rarity helps without taking over: a word in 1 document out of 1,000 is not 1,000 times as informative as a word in every document, it is worth ln(1000) = 6.9. The base of the logarithm only rescales every score by the same factor, so the ranking does not depend on it. The first snippet applies this to four invented mini-documents about cats, dogs and a bank.

import math
from collections import Counter

docs = {                                   # invented, illustrative mini-documents
    "A": "the cat sat on the mat and the cat purred",
    "B": "the dog sat on the log and the dog barked",
    "C": "the bank raised the interest rate on the loan",
    "D": "the cat chased the dog around the bank",
}
words = {name: text.split() for name, text in docs.items()}
N = len(docs)
df = Counter(w for ws in words.values() for w in set(ws))     # in how many documents does each word appear?

def idf(word):
    return math.log(N / df[word])                             # natural log

print("document frequency and idf:")
for w in ("the", "sat", "cat", "dog", "bank", "purred"):
    print(f"  {w:7} df {df[w]}  idf {idf(w):.3f}")

print("top words by tf-idf:")
for name, ws in words.items():
    counts = Counter(ws)
    score = {w: (c / len(ws)) * idf(w) for w, c in counts.items()}
    top = sorted(score.items(), key=lambda kv: -kv[1])[:3]
    print(f"  {name}: " + ", ".join(f"{w} {s:.3f}" for w, s in top))
# document frequency and idf:
#   the     df 4  idf 0.000
#   sat     df 2  idf 0.693
#   cat     df 2  idf 0.693
#   dog     df 2  idf 0.693
#   bank    df 2  idf 0.693
#   purred  df 1  idf 1.386
# top words by tf-idf:
#   A: cat 0.139, mat 0.139, purred 0.139
#   B: dog 0.139, log 0.139, barked 0.139
#   C: raised 0.154, interest 0.154, rate 0.154
#   D: chased 0.173, around 0.173, cat 0.087
    

Look at document A, "the cat sat on the mat and the cat purred", which has 10 words. The table below does the sums for five of its words. The word the occurs 3 times, the most of any word, but it is in all four documents, so its idf is zero and so is its score. cat occurs twice in A and in one other document (df = 2); mat and purred occur once each and nowhere else (df = 1). The ranking comes out as a tie: a word that is twice as frequent in the document but twice as widespread (idf 0.693 against 1.386) scores exactly the same as a word that occurs once and nowhere else. That is the trade the formula makes, and the rest of the chapter is about whether it is a good one.

Word in A	Count	tf (of 10)	df (of 4)	idf	tf × idf
the	3	0.300	4	0.000	0.000
on	1	0.100	3	0.288	0.029
sat	1	0.100	2	0.693	0.069
cat	2	0.200	2	0.693	0.139
mat	1	0.100	1	1.386	0.139

Weight	Rewards	Fails on
tf alone	words the author repeats	puts the and of at the top
idf alone	words few documents use	rewards a one-off typo as much as a key term
tf × idf	words repeated here and rare elsewhere	depends on what the other documents are

Keywords from Whole Books

Now real text. The next snippet treats each of the four books (the same ones as Words by the Numbers 7) as one document, so N = 4, and prints for each book its most frequent words next to its top words by TF-IDF. With only four documents, idf can take just four values: 0 for a word in all four books, 0.288 for three, 0.693 for two and 1.386 for one.

import 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 tokens(text):
    text = text.replace("\u2019", "'")
    return re.findall(r"[a-z]+(?:'[a-z]+)?", text.lower())

counts = {title: Counter(tokens(load(n))) for title, n in BOOKS.items()}
N = len(counts)
df = Counter(w for c in counts.values() for w in c)

def tfidf(title):
    c = counts[title]
    total = sum(c.values())
    return {w: (k / total) * math.log(N / df[w]) for w, k in c.items()}

for title, c in counts.items():
    raw = ", ".join(w for w, _ in c.most_common(6))
    top = sorted(tfidf(title).items(), key=lambda kv: -kv[1])[:6]
    print(f"{title}")
    print(f"  most frequent: {raw}")
    print(f"  tf-idf top:    " + ", ".join(w for w, _ in top))

print("words in all four books:", sum(1 for w in df if df[w] == N), "of", len(df))
print("words in only one book: ", sum(1 for w in df if df[w] == 1))
# Alice in Wonderland
#   most frequent: the, and, to, a, she, it
#   tf-idf top:    alice, mock, turtle, hatter, gryphon, rabbit
# The Time Machine
#   most frequent: the, i, and, of, a, to
#   tf-idf top:    traveller, morlocks, weena, machine, sphinx, medical
# Pride and Prejudice
#   most frequent: the, to, of, and, her, i
#   tf-idf top:    elizabeth, darcy, bennet, jane, bingley, mrs
# The Federalist Papers
#   most frequent: the, of, to, and, in, a
#   tf-idf top:    states, government, national, federal, executive, members
# words in all four books: 898 of 14115
# words in only one book:  8709
    

Book	Most frequent words	Top by TF-IDF
Alice in Wonderland	the, and, to, a, she, it	alice, mock, turtle, hatter, gryphon, rabbit
The Time Machine	the, i, and, of, a, to	traveller, morlocks, weena, machine, sphinx, medical
Pride and Prejudice	the, to, of, and, her, i	elizabeth, darcy, bennet, jane, bingley, mrs
The Federalist Papers	the, of, to, and, in, a	states, government, national, federal, executive, members

The difference is dramatic. Raw frequency gives the same kind of list for every book. TF-IDF gives you, at a glance, names and places in the three novels (a Mock Turtle, a Gryphon, the Morlocks, the Bennets) and the vocabulary of government in the essays. Only 898 of the 14,115 distinct words occur in all four books, so they all score zero, and 8,709 occur in just one. The method is also blunt here: with so few documents, mrs ranks as a keyword of Pride and Prejudice simply because the other books use it less, and the Federalist list is generic (states, government) because the other three books say little about the subject. Keywords depend on the collection you compare against, a point Exercise 2 pushes further.

A Tiny Search Engine

Searching is keyword extraction run backwards. Instead of asking which words characterise a document, you give the words and ask which documents they characterise. The standard structure is an inverted index: a dictionary from each word to the documents containing it and the count in each, so a query only touches the documents that contain its words. To make the collection big enough to be interesting, the next snippet cuts every book into 500-word pieces and treats each piece as a document, 755 in all. A piece's score for a query is the sum, over the query words, of (1 + ln(count)) × idf. The 1 + ln(count) is a common softening (check how widely it is used): the tenth occurrence of a word should not count ten times as much as the first.

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}

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
    text = raw[start:raw.index("*** END OF")]
    return text.translate({0x2018: 39, 0x2019: 39, 0x201c: 34, 0x201d: 34})   # curly to plain quotes

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

# Every 500-word piece of every book is one "document"
SIZE = 500
docs = []                                       # (book title, piece number, words)
for title, number in BOOKS.items():
    words = load(number).split()
    for i in range(0, len(words) - SIZE + 1, SIZE):
        docs.append((title, i // SIZE, words[i:i + SIZE]))

index = defaultdict(dict)                       # word -> {doc id: count in that doc}
for d, (_, _, ws) in enumerate(docs):
    for w, k in Counter(tokens(" ".join(ws))).items():
        index[w][d] = k
N = len(docs)

def search(query, top=3, use_idf=True):
    scores = defaultdict(float)
    for w in tokens(query):
        idf = math.log(N / len(index[w])) if (use_idf and w in index) else 1.0
        for d, k in index.get(w, {}).items():
            scores[d] += (1 + math.log(k)) * idf
    return sorted(scores.items(), key=lambda kv: -kv[1])[:top]

print(f"{N} documents, {len(index):,} distinct words")
EXPECT = {"white rabbit": "Alice in Wonderland", "time traveller": "The Time Machine",
          "darcy bingley": "Pride and Prejudice", "union states constitution": "The Federalist Papers"}
for query, book in EXPECT.items():
    hits = search(query, top=10)
    right = sum(docs[d][0] == book for d, _ in hits)
    print(f"\nquery: {query!r}  ({right} of top 10 from {book})")
    for d, s in hits[:3]:
        title, piece, ws = docs[d]
        found = ", ".join(f"{w} x{index[w].get(d, 0)}" for w in tokens(query))
        print(f"  {s:6.2f}  {title} #{piece}  [{found}]")

print("\nquery 'the of and to rabbit': how many of the top 10 come from Alice in Wonderland?")
for use_idf in (True, False):
    hits = search("the of and to rabbit", top=10, use_idf=use_idf)
    right = sum(docs[d][0] == "Alice in Wonderland" for d, _ in hits)
    print(f"  {'with idf' if use_idf else 'no idf  '}: {right} of 10")

hits = search("the of", top=len(docs))
print("query 'the of' with idf: documents with a score above zero:", sum(s > 1e-9 for _, s in hits))
# 755 documents, 14,082 distinct words
#
# query: 'white rabbit'  (10 of top 10 from Alice in Wonderland)
#    17.88  Alice in Wonderland #50  [white x6, rabbit x6]
#    15.41  Alice in Wonderland #12  [white x3, rabbit x5]
#    14.87  Alice in Wonderland #0  [white x1, rabbit x9]
#
# query: 'time traveller'  (10 of top 10 from The Time Machine)
#    13.92  The Time Machine #4  [time x11, traveller x7]
#    13.79  The Time Machine #9  [time x9, traveller x7]
#    12.74  The Time Machine #2  [time x14, traveller x5]
#
# query: 'darcy bingley'  (10 of top 10 from Pride and Prejudice)
#    10.31  Pride and Prejudice #18  [darcy x6, bingley x7]
#     9.72  Pride and Prejudice #39  [darcy x5, bingley x6]
#     9.66  Pride and Prejudice #14  [darcy x4, bingley x7]
#
# query: 'union states constitution'  (10 of top 10 from The Federalist Papers)
#     9.46  The Federalist Papers #196  [union x6, states x6, constitution x4]
#     9.10  The Federalist Papers #165  [union x4, states x10, constitution x3]
#     8.59  The Federalist Papers #346  [union x1, states x14, constitution x7]
#
# query 'the of and to rabbit': how many of the top 10 come from Alice in Wonderland?
#   with idf: 10 of 10
#   no idf  : 4 of 10
# query 'the of' with idf: documents with a score above zero: 0
    

Query (mine)	Expected book (mine)	Top 10 from that book
white rabbit	Alice in Wonderland	10
time traveller	The Time Machine	10
darcy bingley	Pride and Prejudice	10
union states constitution	The Federalist Papers	10
the of and to rabbit, with idf	Alice in Wonderland	10
the of and to rabbit, without idf	Alice in Wonderland	4

Four things to take from the output. First, the ranker works on short queries, and the counts show why: the top piece for white rabbit has six of each word. Second, idf is what rescues the query that is padded with function words. Without it, the, of, and and to add the same weight as rabbit in every piece, and only 4 of the top 10 come from the right book; with it, all 10 do, because those four words appear in so many pieces that they weigh almost nothing. The last line of output is the extreme case: for the query "the of" every piece scores exactly zero, because both words are in all 755 pieces (ln(755 / 755) = 0). Third, the test is easy and I rigged it a little: the four books differ sharply in vocabulary, the queries are mine, and "right book" is a stand-in for "relevant", which is not the same thing. Fourth, the snippet scores every piece of a book on its own words, with no notion of word order, phrases or meaning, so a query like "white rabbit" would also reward a piece with six whites about something else (that was not tested here).

Common mistakes

Computing idf from a collection too small or too odd to mean anything (four documents gives only four idf values); forgetting that keywords depend on the other documents, so the same text gets different keywords in a different collection; taking ln(N / df) of a word that is not in the index (a division by zero, or a quiet skip as the snippet does); comparing scores across queries as if they were probabilities (they are only for ranking within one query); leaving markup, headers and page numbers in the text, so that illustration becomes a keyword; ignoring word forms (rabbit and rabbits are separate words here); not normalising by document length when documents differ in size; and judging a ranker only on queries you designed to succeed.

Exercise 1

Using the four invented mini-documents, compute idf for df = 1 to 4 under two formulas: the plain ln(N / df) and a smoothed ln(1 + N / df). Print the top three words per document under each. Which variant lets the back into the top three, and is that a good thing?

📄 View solution

Exercise 2

Use the 755 pieces as the collection and extract keywords for each book by adding up the TF-IDF of each word over the book's pieces. Print the top eight, first with every word allowed and then ignoring any word that occurs in more than 20% of the pieces. Which words appear in the first list and not in the second, and why did the first list differ from the one built on four documents?

📄 View solution

Exercise 3

Evaluate the search ranker on eight natural-language queries (two per book, each padded with words like the and and). For three scoring schemes (raw count, softened count, softened count times idf), print how many of the top 10 pieces come from the book you expected, with a total at the bottom. Which scheme degrades most when the query is full of common words?

📄 View solution

Quick Reference

tf: count of the word in the document divided by the document's length
df: number of documents containing the word at least once
idf: math.log(N / df); zero for a word in every document, ln(4) = 1.386 for one in one of four
TF-IDF: tf * idf; high for words frequent here and rare elsewhere
Collection matters: keywords change when the other documents change (with four books, mrs was a keyword of one)
Inverted index: {word: {doc_id: count}}, so a query only visits the documents that contain its words
Ranking: sum (1 + math.log(count)) * idf over the query words; in the test, 10 of 10 right with idf and 4 of 10 without on a query padded with common words
Variants: smoothed idf such as ln(1 + N / df) keeps common words from scoring zero (Exercise 1); BM25 is a descendant used in search engines
Source conflict: the Okapi BM25 work is dated 1994 in some sources and 1995 in others

Coming next

Words by the Numbers 9 is about information and compression: surprise and entropy, Shannon's guessing games, and how much English can be squeezed.