Chapter 2Corpora and Preprocessing

The corpus is the raw material

Every method in this book starts from the same ingredient, which is a large body of text, and that holds just as much for counting bigrams as it does for training a transformer. A corpus, plural corpora, is a collection of text gathered for study or training, and it is the empirical ground the whole field stands on.

Two things make it central. The distributional hypothesis of Chapter 6 makes meaning depend on how words actually get used, and every model in Part III learns its parameters by counting or predicting over text. The corpus is therefore not a backdrop but the source of everything the system will ever know.

Train a model only on legal contracts and it will speak like a contract, while training it on the open web means it inherits the web’s knowledge and its prejudices together. Choosing the corpus is the most consequential decision you will make.

The field’s corpora tell its history rather neatly. The Brown Corpus of 1961 held a carefully balanced million words of American English, and the Penn Treebank annotated Wall Street Journal text with syntactic structure, which made both of them workhorses of the statistical era. Parallel corpora made statistical machine translation possible, the classic one being the Canadian Hansards, which pairs English and French transcripts of parliament.

Then the scale exploded. Large language models are pretrained on web scale corpora such as Common Crawl, C4, The Pile, RefinedWeb and FineWeb, which are measured in trillions of tokens rather than millions of words.

That jump matters twice over, because it is one of the deepest reasons the models of Part IV can do what earlier ones could not, and it is also why their failures of bias and provenance are so hard to audit. The book’s final chapters take that up.

Preprocessing: decisions that shape the data

Raw text is rarely fed to a model as it stands. Between the corpus and the model sits preprocessing, a sequence of transformations that put the text into some canonical form.

The classical pipeline for English is a familiar list:

• tokenisation, splitting text into words or tokens

• case folding, lowercasing everything

• stemming, crudely stripping suffixes, so running becomes run

• lemmatisation, mapping a word to its dictionary root, so best becomes good

• stripping punctuation and normalising whitespace

• expanding contractions, so isn’t becomes is not

• removing stop words, the very frequent low content words such as the and of

Stemming against lemmatisation

Two of those steps get confused with each other constantly, so it is worth seeing them side by side on real words.

A stemmer chops, applying suffix rules without ever consulting a dictionary. The Porter stemmer is the classic example, and it is fast, language specific, and wholly indifferent to whether the result is a word.

A lemmatiser looks up instead, mapping a word to its dictionary headword, its lemma, using a vocabulary and usually the part of speech as well. It is slower and it needs that dictionary, but its output is always a real word.

Here is what they do to the same eight inputs.

Three lessons fall out of that table.

First, the stemmer produces non words, since univers, wa and studi are not English. That costs nothing if the output is only ever an index key, and it is unacceptable if a human will read it.

Second, the stemmer cannot handle irregular forms, so it leaves better and mice untouched for want of any suffix to strip. Only a dictionary knows that better is a form of good, or that mice is the plural of mouse.

Third, and most damaging, the stemmer over merges. Organization becomes organ, so a document about corporate structure now shares a term with a document about the human body, and university becomes univers, which swallows universal and universe along with it.

Which one you want depends on the job. A search engine usually prefers the stemmer, because recall matters more than precision, the output is never shown to anyone, and speed counts. A grammar checker or a machine translation system needs the lemmatiser, since it must know that was is a form of be before it can reason about tense.

Every step costs you something

None of these steps is automatically correct, because each one destroys information along with the noise.

Case folding is the cautionary classic, since lowercasing collapses US the country into us the pronoun, and Apple the company into apple the fruit. That is a small convenience bought with a real distinction.

Removing stop words carries a subtler cost, because it discards exactly the function words that carry the syntax. Strip them from “the cat sat on the mat” and you get “cat sat mat”, which still says roughly what the sentence was about, so no harm is done. Now strip them from “the man bit the dog” and from “the dog bit the man”, and both collapse to “man bit dog”. The two sentences said opposite things, and preprocessing has just made them identical.

The governing principle, then, is that preprocessing is task dependent. A topic classifier benefits from collapsing variants and dropping function words, while a system that must respect case, punctuation or grammar is ruined by those same steps. Understand the problem first and choose the pipeline second.

One historical shift reverses the classical advice entirely. Modern LLM pipelines do minimal preprocessing, keeping the case, the punctuation and the stop words, and leaning instead on subword tokenisation, which is the byte pair encoding of Chapter 5 that turns raw text into units a model can consume.

The reason for the reversal is worth stating. Aggressive cleaning made sense when models were small and every dimension was precious, whereas a large model can simply learn that Apple and apple differ by context. Throwing that distinction away at the door is then a loss rather than a gain, which is why the field has moved steadily towards doing less to the text and letting the model do more.

Measuring string distance

Two of the tasks above need a different kind of tool altogether. Correcting misspellings and removing near duplicate documents both ask how close two strings are as sequences of characters, and the vector similarities of later chapters cannot answer that question.

The classical tool is minimum edit distance, also called Levenshtein distance, which is the smallest number of single character insertions, deletions and substitutions that turn one string into another.

A small dynamic program computes it. Let $D[i,j]$ be the distance obtained by comparing the first $i$ characters of source $s$ with the first $j$ of target $t$. Then

$$\begin{equation} D[i,j] = \min\!\begin{cases} D[i-1,j] + \mathrm{del}(s_i) & \text{(delete } s_i) \\ D[i,j-1] + \mathrm{ins}(t_j) & \text{(insert } t_j) \\ D[i-1,j-1] + \mathrm{sub}(s_i,t_j) & \text{(match or substitute)} \end{cases} \label{eq:editdist} \quad\text{(2.1)} \end{equation}$$

with base cases $D[i,0] = i$ and $D[0,j] = j$. The answer sits in the bottom right cell, $D[|s|,|t|]$.

The penalties

The three functions $\mathrm{del}$, $\mathrm{ins}$ and $\mathrm{sub}$ are the penalties, or costs. They are a choice, not a law. Levenshtein distance takes the simplest choice:

$$\begin{equation} \mathrm{del}(a) = 1, \qquad \mathrm{ins}(b) = 1, \qquad \mathrm{sub}(a,b) = \begin{cases} 0 & \text{if } a = b \quad \text{(a match is free)}\\ 1 & \text{otherwise} \end{cases} \label{eq:editcosts} \quad\text{(2.2)} \end{equation}$$

A match costs nothing, so when two characters agree the diagonal move is the one that carries the alignment forward.

Other choices are common, and they change the answer. Jurafsky and Martin often set $\mathrm{sub} = 2$, reasoning that a substitution is really a deletion plus an insertion, and under that setting kitten to sitting costs $5$ rather than $3$. Spelling correctors sometimes make $\mathrm{sub}(m, n)$ cheaper than $\mathrm{sub}(m, q)$, because $m$ and $n$ sit adjacent on the keyboard and are confusable by ear, while biological sequence alignment uses a whole substitution matrix.

Always state your penalties, because a distance quoted without them is not a number anyone can reproduce. Everything below uses Equation (2.2).

In words, the cheapest way to align two prefixes is the cheapest of three smaller alignments plus one more edit. Fill the table left to right and top to bottom, and the whole thing costs $O(|s|\,|t|)$ time.

A worked example: cat to cart

Take $s = \texttt{cat}$ and $t = \texttt{cart}$. The table gets one row per character of the source and one column per character of the target, each plus one for the empty string, which makes it $4$ rows by $5$ columns.

Step 1: the first four cells.

Start in the corner, where the base cases fill the top row and the left column, giving $D[0,0]=0$, $D[0,1]=1$ and $D[1,0]=1$. Those say that turning an empty string into c costs one insertion, and that turning c into an empty string costs one deletion.

Now compute the first real cell, $D[1,1]$, which compares c with c. Take the smallest of three options, where deleting gives $D[0,1]+1 = 2$, inserting gives $D[1,0]+1 = 2$, and matching gives $D[0,0]+0 = 0$. The match wins.

Step 2: the first pass.

Carry that row across, where each new cell asks the same three way question about a longer prefix of the target.

Along the row for c, once the c itself has matched, every further column costs one more insertion, because the source has run out of letters to align, and so the row climbs $0, 1, 2, 3$.

Step 3: the finished table.

Fill the remaining rows the same way, with cells on the cheapest path shown in bold and the answer boxed.

The boxed cell is the answer, so the edit distance from cat to cart is $\mathbf{1}$.

Step 4: the trace.

The number alone does not say which edits were made, and for that you walk backwards from the boxed cell, each time to whichever neighbour produced it.

Read forwards, the alignment is plain: keep c, keep a, insert r, keep t. That is one insertion, so the distance is $1$.

Each move carries a meaning. A diagonal step consumes one character from each string, a left step consumes one from the target only and is therefore an insertion, and an upward step consumes one from the source only and is a deletion.

Try it yourself. The script that produced these three tables and the trace is code/worked_examples/edit_distance.py. Run it on your own pair of words, or change the penalties and watch the answer move.

Run it in ColabNotebookSource

The canonical larger example is kitten to sitting, whose distance is $3$ under these penalties: substitute s for k, substitute i for e, then insert a final g. That table runs $7$ by $8$, and building it by hand is the fastest way to be sure you have the recurrence right.

A spelling corrector uses exactly this machinery, returning the dictionary word at minimum edit distance from the misspelling, and corpus deduplication uses a relative of it to flag documents that differ only in boilerplate.

The same dynamic programming idea comes back later in the book. Generalise it from characters to words, and from distance to reward, and you have sequence alignment, which recurs throughout computational linguistics.

Knowing your corpus

Measure the text before you model it, because a handful of simple statistics already says a great deal.

The token count is the total number of word occurrences, the vocabulary size, or type count, is the number of distinct words, and the type token ratio is the vocabulary divided by the token count, which serves as a first index of lexical variety.

These are not idle tallies, because two real questions follow from them. How does the vocabulary grow as the text gets longer, and how steeply do word frequencies fall from the most common word to the rarest?

Both answers turn out to obey strikingly regular mathematical laws that hold equally for a Victorian novel and for a web crawl. They are Zipf’s law and Heaps’ law, and Chapter 3 is about them.

Those laws explain a good deal of what follows, including why the long tail of rare words never goes away and why the subword tokenisers of Chapter 5 are a practical necessity rather than a nicety. Measuring the corpus is the first step towards seeing why the later methods take the shape they do.

Further reading.

Manning and Schütze (Manning and Schütze 1999) give a thorough account of corpora, tokenisation and the statistical preprocessing pipeline. Jurafsky and Martin (Jurafsky and Martin 2025) cover text normalisation and its pitfalls with many worked examples. For how modern pretraining data is actually assembled and filtered, the documentation of the web scale corpora named above remains the best guide.

Code for this chapter

Each one reproduces the tables above. Open it in Colab, change an input and watch which numbers move.

• edit_distance.pyEdit distance, every cell

  The three tables and the backtrace for cat to cart, with the recurrence spelled out rather than optimised.

  standard library only Run it in Colab Notebook Source

From Natural Language Processing: From Corpus Statistics to Grounded LLMs, by Ramaseshan Ramachandran.