Chapter 2Corpora and Preprocessing

The corpus is the raw material

Every method in this book starts with the same ingredient. A large body of text. This is true of counting bigrams and of training a transformer alike.

A corpus, plural corpora, is a collection of text gathered for study or training. 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 get used. And every model in Part III learns its parameters by counting or predicting over text. So the corpus is not a backdrop. It is the source of everything the system will ever know.

Train a model only on legal contracts and it will speak like a contract. Train it on the open web and 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. The Brown Corpus of 1961 held a carefully balanced million words of American English. The Penn Treebank annotated Wall Street Journal text with syntactic structure. Both were the workhorses of the statistical era. Parallel corpora made statistical machine translation possible. The classic one is the Canadian Hansards, which pairs English and French transcripts of parliament.

Then the scale exploded. Large language models are pretrained on web scale corpora: Common Crawl, C4, The Pile, RefinedWeb, FineWeb. These are measured in trillions of tokens, not millions of words.

That jump matters twice over. It is one of the deepest reasons the models of Part IV can do what earlier ones could not. 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. It is a sequence of transformations that put text into a 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. It applies suffix rules and never consults a dictionary. The Porter stemmer is the classic. It is fast, it is language specific, and it does not care whether the result is a word.

A lemmatiser looks up. It maps a word to its dictionary headword, its lemma, using a vocabulary and usually the part of speech. It is slower and it needs a 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. univers, wa and studi are not English. That is fine if the output is only ever an index key. It is unacceptable if a human will read it.

Second, the stemmer cannot handle irregular forms. It leaves better and mice untouched, because there is no suffix to strip. Only a dictionary knows that better is a form of good, and 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. University becomes univers, which also swallows universal and universe.

So which do you want? A search engine usually prefers the stemmer. 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. 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. Each one destroys information as well as noise.

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

Removing stop words has a subtler cost. It discards exactly the function words that carry the syntax.

Strip them from “the cat sat on the mat”. You get “cat sat mat”, which still says roughly what the sentence was about. No harm done.

Now strip them from “the man bit the dog” and from “the dog bit the man”. Both become “man bit dog”. The sentences said opposite things, and preprocessing has made them identical.

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

One historical shift reverses the classical advice. Modern LLM pipelines do minimal preprocessing. They keep the case. They keep the punctuation. They keep the stop words. Instead they lean on subword tokenisation. That is the byte pair encoding of Chapter 5. It turns raw text into units a model can consume.

Why the reversal? Aggressive cleaning made sense when models were small and every dimension was precious. A large model can learn that Apple and apple differ by context. Throwing that distinction away at the door is then a loss, not a gain. 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. Correcting misspellings and removing near duplicate documents both ask how close two strings are as sequences of characters. The vector similarities of later chapters cannot answer that.

The classical tool is minimum edit distance, also called Levenshtein distance. It 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 a distance. It compares 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 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$. Their reasoning is that a substitution is really a deletion plus an insertion. 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$ are adjacent on the keyboard and confusable by ear. Biological sequence alignment uses a whole substitution matrix.

So always state your penalties. 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, plus one for the empty string. It gets one column per character of the target, plus one for the empty string. So it is $4$ rows by $5$ columns.

Step 1: the first four cells.

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

Now compute the first real cell, $D[1,1]$. It compares c with c. Take the smallest of three options: delete gives $D[0,1]+1 = 2$, insert gives $D[1,0]+1 = 2$, and match gives $D[0,0]+0 = 0$. The match wins.

Step 2: the first pass.

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

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

Step 3: the finished table.

Fill the remaining rows the same way. Cells on the cheapest path are in bold, and the answer is boxed.

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

The trace.

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

Forwards, the alignment is plain. Keep c, keep a, insert r, keep t. One insertion, so distance $1$.

The moves have meanings. A diagonal step consumes one character from each string. A left step consumes one from the target only, which is an insertion. An upward step consumes one from the source only, which 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 k for s. Substitute e for i. Insert a final g. The table is $7$ by $8$. Building it by hand is the fastest way to be sure you have the recurrence right.

A spelling corrector uses exactly this. It returns the dictionary word at minimum edit distance from the misspelling. Corpus deduplication uses a relative of it to flag documents that differ only in boilerplate.

The same dynamic programming idea comes back later. Generalise it from characters to words, and from distance to reward. You get sequence alignment, which recurs throughout computational linguistics.

Knowing your corpus

Measure the text before you model it. A handful of simple statistics already say 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. The type token ratio is the vocabulary divided by the token count, and it is a first index of lexical variety.

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

Both answers turn out to obey strikingly regular mathematical laws. The same laws hold 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 lot of what follows. They explain why the long tail of rare words never goes away. They explain 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 give a thorough account of corpora, tokenisation and the statistical preprocessing pipeline. Jurafsky and Martin cover text normalisation and its pitfalls with many worked examples. Want to know how modern pretraining data is assembled and filtered? The documentation of the web scale corpora named above is the best guide.