---
title: Regular Expressions and Text Normalization
module: Foundations
moduleNumber: 1
lessonNumber: 2
order: 102
summary: >
  Before any model touches text, the text has to be found and cleaned. Regular
  expressions give an algebra for describing string patterns; tokenization,
  case folding, and stemming turn raw characters into the units a model counts;
  and byte-pair encoding builds a subword vocabulary that spells out any word.
  Measuring how far apart two strings are — minimum edit distance — is the
  next lesson.
topics: [Foundations]
sources:
  - book: Jurafsky & Martin
    ref: "Ch. 2 — Regular Expressions, Text Normalization, Edit Distance; §2.1 Regular Expressions"
  - book: Jurafsky & Martin
    ref: "§2.4 Text Normalization"
---

Every language-processing system takes the same input: a stream of characters. Few
downstream operations are defined on characters — they need words, sentences, prices,
or a distance between two strings. This lesson supplies three layers between the
character stream and the first model: a pattern language for _finding_ structure
(regular expressions), a set of tasks for _imposing_ structure (text normalization),
and one algorithm for _comparing_ strings (minimum edit distance).

Weizenbaum's ELIZA, the earliest dialogue system, was a cascade of
pattern-and-substitute rules — mapping "I need X" to "What would it mean to you if you
got X?" — and nothing more.[^jm-eliza] The pattern-matching layer persists in modern
systems as the entry point where text enters the pipeline.

## Regular expressions

A **regular expression** (RE) is an algebraic notation characterizing a set of
strings — a **regular language** $L(r) \subseteq \Sigma^\ast$ over an alphabet
$\Sigma$.[^jm-re] Given a **pattern** and a **corpus** of text, an engine returns
every substring $w$ with $w \in L(r)$. Every RE compiles to an equivalent
finite-state automaton, which is why matching runs in time linear in the input. The
notation is portable across `grep`, editors, and Python; patterns are written between
slash delimiters, `/like this/` (the slashes are not part of the pattern).

The simplest pattern is a literal sequence of characters: `/woodchuck/` matches the
string `woodchuck` wherever it appears. Regular expressions are **case sensitive**,
so `/woodchuck/` will not match `Woodchuck`. Everything past literals is built from
a small set of operators that let one pattern stand for many strings.

### Character classes, ranges, and negation

Square brackets specify a **disjunction of characters** — a single position that may
be any one of a set. `/[wW]/` matches `w` or `W`, so `/[wW]oodchuck/` catches both
capitalizations. Inside brackets a dash denotes a **range** over the character
ordering: `/[a-z]/` is any lowercase letter, `/[A-Z]/` any uppercase letter,
`/[0-9]/` any single digit. A caret as the _first_ character inside the brackets
**negates** the class: `/[^a-z]/` matches any single character that is _not_ a
lowercase letter. (A caret anywhere else inside brackets is just a literal caret.)

| Pattern | Matches | Example |
| --- | --- | --- |
| `/[wW]/` | `w` or `W` | **W**oodchuck |
| `/[abc]/` | one of `a`, `b`, `c` | in uomini, in sold**a**ti |
| `/[0-9]/` | a single digit | Chapter **1** |
| `/[A-Z]/` | an uppercase letter | **D**renched Blossoms |
| `/[^A-Z]/` | any non-uppercase char | O**y**fn pripetchik |
| `/[^Ss]/` | neither `S` nor `s` | **I** have no reason |

Because a handful of classes come up constantly, there are backslash **aliases**:
`\d` is `[0-9]`, `\w` is a word character `[a-zA-Z0-9_]`, `\s` is whitespace, and
each has an uppercase-negated twin (`\D`, `\W`, `\S`). To match a character that is
itself an operator — a literal period, star, or bracket — precede it with a
backslash: `/\./`, `/\*/`, `/\[/`.

### Counters — optionality, Kleene star and plus

A **counter** following an element sets its multiplicity. For an element $e$, the
counters denote:

| Counter | Repetitions of $e$ | Language |
| --- | --- | --- |
| `e?` | $0$ or $1$ | $\{\varepsilon\} \cup L(e)$ |
| `e*` | $0$ or more (Kleene star) | $\bigcup_{n\ge 0} L(e)^n$ |
| `e+` | $1$ or more (Kleene plus) | $\bigcup_{n\ge 1} L(e)^n$ |
| `e{n}` | exactly $n$ | $L(e)^n$ |
| `e{n,m}` | between $n$ and $m$ | $\bigcup_{k=n}^{m} L(e)^k$ |
| `e{n,}` | at least $n$ | $\bigcup_{k\ge n} L(e)^k$ |

So `/colou?r/` matches `color` and `colour`; `/a*/` matches $\varepsilon, a, aa,
\dots$; and `/[0-9]+/` is the idiom for an integer. The wildcard `/./` (an
unescaped period) matches any single character, so `/beg.n/` matches `begin`,
`begun`, and `beg'n` alike, and `/aardvark.*aardvark/` matches any line where
`aardvark` appears twice.

The star is **greedy**: against `once upon a time`, `/[a-z]*/` matches the longest
prefix run. The non-greedy variants `*?` and `+?` match the _fewest_ characters
possible, which matters when a later subpattern must consume the remainder.

### Anchors, disjunction, and grouping

**Anchors** match a _position_ rather than a character. The caret `^` (outside
brackets) matches the start of a line, `$` matches the end, `\b` matches a word
boundary, and `\B` a non-boundary. So `/^The/` finds `The` only at the start of a
line, and `/\bthe\b/` matches the word `the` but not `the` buried inside `other` or
`theology`.

The **disjunction** operator `|` (the pipe) matches either of two whole patterns:
`/cat|dog/` matches `cat` or `dog`. Disjunction has very low precedence — it splits
the pattern at the widest scope — so `/guppy|ies/` matches `guppy` or `ies`, _not_
`guppy` or `guppies`. To scope the disjunction, use **grouping** parentheses:
`/gupp(y|ies)/` matches `guppy` and `guppies`, because the parentheses make
`(y|ies)` behave as a single element. Grouping also lets a counter apply to a whole
sub-pattern rather than one character: `/(ab)+/` matches `ab`, `abab`, `ababab`.

Parentheses have a second job. A **capture group** stores whatever its sub-pattern
matched in a numbered **register**, referred to later by `\1`, `\2`, and so on. This
makes substitutions expressive: the substitution `s/([0-9]+)/<\1>/` wraps every
integer in angle brackets, and `/the (.*)er they were, the \1er they will be/`
forces the two blanks to match the _same_ string, so it accepts "the bigger they
were, the bigger they will be" but rejects a mismatched pair. When you want the
grouping but not the register, a **non-capturing group** `(?:...)` groups without
consuming a register number.

The precedence order, highest to lowest, is the one fact that resolves most
ambiguous patterns:

| Precedence | Operators | Example |
| --- | --- | --- |
| highest | parentheses | `(...)` |
| | counters | `* + ? {n,m}` |
| | sequences and anchors | `the`, `^my`, `end$` |
| lowest | disjunction | `\|` |

Because counters bind tighter than sequences, `/the*/` matches `th`, `the`, `thee`,
`theee` — the star attaches to `e`, not to the whole word. Because sequences bind
tighter than disjunction, `/the|any/` matches `the` or `any`, not `th` followed by
`e`-or-`a` followed by `ny`.

$$
% caption: The regular-expression operator precedence hierarchy: parentheses bind
% tightest, then counters, then sequences and anchors, and disjunction loosest —
% the order that resolves an otherwise ambiguous pattern.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  lvl/.style={draw, minimum width=44mm, minimum height=9mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[lvl, draw=acc, text=acc, thick] (a) at (0,3.0)  {parentheses \texttt{(...)}};
  \node[lvl] (b) at (0,1.8)  {counters \texttt{*} \texttt{+} \texttt{?} \texttt{n..m}};
  \node[lvl] (c) at (0,0.6)  {sequences, anchors};
  \node[lvl] (d) at (0,-0.6) {disjunction (pipe)};
  \draw[->, black] (a) -- (b);
  \draw[->, black] (b) -- (c);
  \draw[->, black] (c) -- (d);
  \node[anchor=west, font=\footnotesize, text=acc] at (2.9,3.0)  {binds tightest};
  \node[anchor=west, font=\footnotesize, text=black] at (2.9,-0.6) {binds loosest};
\end{tikzpicture}
$$

Two more operators round out the language. **Substitution**, written
`s/pattern/replacement/`, rewrites every match — `s/colour/color/` Americanizes a
document. **Lookahead assertions** test whether a pattern matches _without_
consuming any input: `(?=...)` is positive lookahead, `(?!...)` negative, both
zero-width. Negative lookahead expresses exclusions cleanly — `/^(?!Volcano)[A-Za-z]+/`
matches any opening word that is not `Volcano`.

Pattern design balances two error types. A loose pattern produces **false positives**
($\mathrm{FP}$, matching excluded strings); a tight pattern produces **false
negatives** ($\mathrm{FN}$, missing intended strings). With true positives
$\mathrm{TP}$,

$$
\text{precision} = \frac{\mathrm{TP}}{\mathrm{TP} + \mathrm{FP}}, \qquad
\text{recall} = \frac{\mathrm{TP}}{\mathrm{TP} + \mathrm{FN}}.
$$

Tightening to cut $\mathrm{FP}$ raises precision; loosening to cut $\mathrm{FN}$
raises recall. Every pattern trades one against the other.[^jm-precision]

## Text normalization

Before almost any language processing, the text must be **normalized** into a
standard form. Three tasks make up nearly every normalization pipeline: **tokenizing**
words, **normalizing** word formats, and **segmenting** sentences.[^jm-norm]

### Tokenization

**Tokenization** is the task of segmenting running text into words, or **tokens**.
The naive rule — split on whitespace — fails immediately, in both directions. It
splits too little: `Ph.D.`, `AT&T`, and `m.p.h.` contain internal punctuation that
belongs to the token, and prices like `$45.55` or dates like `01/02/06` must not be
diced at the period. It also splits too much: `New York` and `rock 'n' roll` are
arguably single tokens despite their spaces, and a **clitic** contraction like
`what're` should expand to the two tokens `what` and `are`. Punctuation itself is
usually worth keeping as its own token — commas cue parsers, periods cue sentence
boundaries, question marks carry meaning — rather than discarded.

Tokenization runs first, so it must be fast: the standard approach compiles a
deterministic RE into a finite-state automaton. The **Penn Treebank** standard
separates clitics (`doesn't` → `does` `n't`), keeps hyphenated words together, and
splits off punctuation. Two counts recur throughout the subject: the number of
distinct words, the **types** or vocabulary size $|V|$, and the total number of
running words, the **tokens** $N$. Empirically the two grow together as $|V| \propto
N^{\beta}$ with $\beta \approx 0.67$–$0.75$ (Herdan's law), so vocabulary keeps
expanding with corpus size.

Not every language separates words with spaces. Chinese writes characters (**hanzi**)
with no delimiters, and boundary judgments disagree even among native speakers; many
Chinese tasks take each character as the token. Japanese and Thai require dedicated
**word-segmentation** models. These difficulties motivate a third option that
sidesteps the definition of a "word" altogether.

### Byte-pair encoding

Words are a leaky abstraction for a model. A system trained on `low`, `new`, and
`newer` but never `lower` cannot represent `lower` at test time — the **unknown-word**
(out-of-vocabulary) problem. Modern tokenizers avoid it with a vocabulary of
**subwords**: units smaller than words, often morphemes like `-er` or `-est`, so any
unseen word is spelled from known pieces.[^jm-bpe]

The dominant scheme is **byte-pair encoding** (BPE), in two halves: a _token learner_
inducing a vocabulary $V$ from a corpus, and a _token segmenter_ applying it to new
text. The learner initializes $V$ to the character set, then for $k$ iterations
selects the most frequent adjacent symbol pair, merges it into a new symbol, and adds
it to $V$. This yields $|V| = |\Sigma| + k$.

```algorithm
caption: $\textsc{Byte-Pair-Encoding}(C, k)$ — learn a subword vocabulary from corpus $C$ with $k$ merges
input: corpus $C$ (words as character sequences with a word-end marker), number of merges $k$
$V \gets$ set of all distinct characters in $C$
for $i = 1$ to $k$ do
  $(t_L, t_R) \gets$ most frequent adjacent pair of symbols in $C$
  $t_{\text{new}} \gets t_L + t_R$ // concatenate into one new symbol
  $V \gets V \cup \{t_{\text{new}}\}$
  replace every occurrence of $(t_L, t_R)$ in $C$ with $t_{\text{new}}$
return $V$
```

Run inside words with a special end-of-word marker `_`, on a tiny corpus of counted
word tokens (`low` × 5, `lowest` × 2, `newer` × 6, `wider` × 3, `new` × 2), the
first merges are easy to trace by hand. The pair `e r` is most frequent (9
occurrences, across `newer` and `wider`), so it merges to `er`; then `er _` merges
to `er_`; then `n e` to `ne`, and so on.

$$
% caption: The first three BPE merges on the corpus low/lowest/newer/wider/new.
% The most frequent adjacent pair is merged into a single symbol, added to the
% vocabulary, and rewritten throughout the corpus, then the count repeats.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=30mm, minimum height=8mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (s0) at (0,3.2) {\texttt{e r} (count 9)};
  \node[box] (s1) at (0,1.6) {\texttt{er \_} (count 9)};
  \node[box] (s2) at (0,0.0) {\texttt{n e} (count 8)};
  \node[box, draw=acc, text=acc, thick] (v0) at (5.4,3.2) {add \texttt{er}};
  \node[box, draw=acc, text=acc, thick] (v1) at (5.4,1.6) {add \texttt{er\_}};
  \node[box, draw=acc, text=acc, thick] (v2) at (5.4,0.0) {add \texttt{ne}};
  \draw[->, acc, thick] (s0) -- (v0) node[midway, above, font=\scriptsize] {merge};
  \draw[->, acc, thick] (s1) -- (v1) node[midway, above, font=\scriptsize] {merge};
  \draw[->, acc, thick] (s2) -- (v2) node[midway, above, font=\scriptsize] {merge};
  \draw[->, black] (v0.south) .. controls (5.4,2.6) and (0,2.4) .. (s1.north);
  \node[font=\scriptsize, text=black, anchor=south] at (3.2,2.62) {recount};
  \draw[->, black] (v1.south) .. controls (5.4,1.0) and (0,0.8) .. (s2.north);
  \node[font=\scriptsize, text=black, anchor=south] at (3.2,1.02) {recount};
\end{tikzpicture}
$$

The segmenter applies the learned merges, in the order learned, to new text. A word
seen in training collapses back to a few symbols; a genuinely novel word like
`lower` is left as the pieces `low` and `er_`. With thousands of merges on a real
corpus the effect is that common words become single tokens and only the rare and
unknown ones get spelled out of parts — exactly the behavior a language model needs.

To see the segmenter run, take the learned merge list (in order) `e r` → `er`,
`er _` → `er_`, `n e` → `ne`, `ne w` → `new`, `l o` → `lo`, `lo w` → `low`, and
apply it to the unseen word `lower_`. Start from characters, `l o w e r _`, and scan
for the first applicable merge in learned order. `e r` fires, giving `l o w er _`;
then `er _` fires, giving `l o w er_`; `n e` and `ne w` do not apply; `l o` fires,
giving `lo w er_`; `lo w` fires, giving `low er_`. No further merge applies, so
`lower_` segments as `low` + `er_` — two known pieces the model has embeddings for,
even though `lower` never appeared in training. The unknown-word problem is dissolved:
there is no out-of-vocabulary word, only a longer or shorter spelling out of subwords.

$$
% caption: Segmenting the unseen word lower with the learned merge list. Starting
% from characters, each learned merge is applied in order where it fits; the word
% ends as low + er, two in-vocabulary pieces, with no unknown token.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  row/.style={font=\footnotesize\ttfamily, anchor=west},
  op/.style={font=\scriptsize, text=black, anchor=west}]
  \definecolor{acc}{HTML}{2348F2}
  \node[row] at (0,3.0)  {l o w e r \_};
  \node[op]  at (4.4,3.0) {start: characters};
  \node[row] at (0,2.2)  {l o w er \_};
  \node[op]  at (4.4,2.2) {apply e+r};
  \node[row] at (0,1.4)  {l o w er\_};
  \node[op]  at (4.4,1.4) {apply er+\_};
  \node[row] at (0,0.6)  {lo w er\_};
  \node[op]  at (4.4,0.6) {apply l+o};
  \node[row, text=acc] at (0,-0.2) {low er\_};
  \node[op]  at (4.4,-0.2) {apply lo+w, done};
  \draw[->, acc] (1.4,2.82) -- (1.4,2.38);
  \draw[->, acc] (1.4,2.02) -- (1.4,1.58);
  \draw[->, acc] (1.4,1.22) -- (1.4,0.78);
  \draw[->, acc] (1.4,0.42) -- (1.4,-0.02);
\end{tikzpicture}
$$

### Word normalization, lemmatization, and stemming

Even after tokenizing, the same word appears in many surface forms. **Word normalization** puts
tokens into a standard form: mapping `US`, `U.S.`, and `USA` to one representation,
or collapsing `uh-huh` and `uhhuh`. **Case folding** — mapping everything to
lowercase — is the bluntest version, and it helps for information retrieval, where a
searcher wants `Woodchuck` and `woodchuck` treated alike. But case folding is not
always wanted: for sentiment analysis and machine translation the difference between
`US` the country and `us` the pronoun can outweigh the generalization it buys.

A deeper normalization collapses inflected forms. **Lemmatization** determines that
two words share a root despite surface differences: `am`, `are`, and `is` all reduce
to the **lemma** `be`; `dinner` and `dinners` to `dinner`. Done properly it requires
**morphological parsing** — decomposing a word into its **morphemes**, the smallest
meaning-bearing units, split into **stems** (the core meaning) and **affixes** (the
`-s`, `-ed`, `-ing` that modify it). Lemmatizing "He is reading detective stories"
yields "He be read detective story."

Full morphological parsing is expensive; **stemming** is the cheaper shortcut,
chopping affixes off the word end. The **Porter stemmer** is the classic instance: a
cascade of rewrite rules applied in series, each pass feeding the next.[^jm-porter] A
sampling of its rules:

| Rule | Example |
| --- | --- |
| `ATIONAL` → `ATE` | relational → relate |
| `ING` → $\varepsilon$ (if stem has a vowel) | motoring → motor |
| `SSES` → `SS` | grasses → grass |

Stemming is fast and dictionary-free, but it errs in both directions — **over-generalizing**
(`organization` → `organ`, `policy` → `police`) and **under-generalizing** (`European`
and `Europe` left unmerged). It is a useful approximation, not a substitute for real
morphology.

### The subword tokenizers behind modern models

The byte-pair encoding above was introduced for text _compression_ (Gage, 1994); its
adaptation to NLP is more recent and is worth stating precisely, because the exact
tokenizer a model uses shapes what it can represent. Sennrich, Haddow & Birch (2016,
ACL) reintroduced BPE as a tokenization method for neural machine translation, and
their motivation was the same open-vocabulary problem the previous section named:
a translation model with a fixed word vocabulary cannot emit a word it never saw,
and it is the rare words — names, compounds, morphologically rich forms — that
matter most.[^sennrich] Splitting into subword units let a single fixed-size
vocabulary spell out any word, and it improved translation of rare and unseen words.
That paper is why nearly every transformer since tokenizes into subwords.

Three variants dominate, differing in the merge or split criterion.

| Tokenizer | Direction | Criterion for a pair $(a,b)$ | Used by |
| --- | --- | --- | --- |
| **BPE** | bottom-up merge | maximize count $c(ab)$ | GPT-2, GPT-3 |
| **WordPiece** | bottom-up merge | maximize $\dfrac{c(ab)}{c(a)\,c(b)}$ (PMI-like) | BERT |
| **Unigram LM** | top-down prune | minimize corpus likelihood loss from removing a subword | T5, ALBERT |

- **BPE** greedily merges the highest-count adjacent pair, $k$ times — simple and
  deterministic.
- **WordPiece** (Schuster & Nakajima, 2012) instead merges the pair that most
  increases training-corpus likelihood under a unigram model, i.e. the pair maximizing
  the count ratio $c(ab)/(c(a)\,c(b))$ — the same pointwise-mutual-information quantity
  used in the
  [sentiment lexicons](/natural-language-processing/classification/sentiment-and-affect-lexicons).
- **Unigram-LM** tokenization (Kudo, 2018) works top-down: fit a unigram distribution
  over a large candidate vocabulary, then iteratively prune the subwords whose removal
  costs the corpus likelihood least.[^kudo] It scores every segmentation and can retain
  several, enabling subword sampling during training.

The **SentencePiece** library (Kudo & Richardson, 2018) packages these so the
tokenizer runs directly on raw text — treating the space as an ordinary symbol (often
written as a visible underscore-like marker) — so the same tokenizer works on
languages without spaces and the process is fully reversible from tokens back to the
exact input string. The practical upshot: the "word" that this lesson opened with is
not the unit modern models operate on. They operate on subwords chosen to balance a
fixed vocabulary size against the ability to spell out anything, and the choice among
BPE, WordPiece, and unigram-LM is a real engineering decision, not a detail.

### Sentence segmentation

The last normalization task is **sentence segmentation**: breaking text into
sentences. Question marks and exclamation points are nearly unambiguous sentence
boundaries. The period is the hard case, because `.` marks both an end of sentence
and an abbreviation — `Mr.`, `Inc.`, `Ph.D.` — and sometimes both at once. Segmenters
therefore decide, per period, whether it belongs to the preceding token or ends the
sentence, using an abbreviation dictionary (hand-built or learned) or a classifier.
In practice sentence and word tokenization are settled jointly: a sentence ends when
a sentence-final punctuation mark is _not_ already glued into a token like an
abbreviation or a number.

[^jm-eliza]: **Jurafsky & Martin**, _Speech and Language Processing_ (3rd ed.), Ch. 2 — ELIZA as a cascade of regular-expression substitutions, the earliest pattern-based dialogue system.
[^jm-re]: **Jurafsky & Martin**, §2.1 — Regular Expressions: character classes, ranges, negation, Kleene star and plus, anchors, disjunction, grouping, capture groups, substitution, and lookahead.
[^jm-precision]: **Jurafsky & Martin**, §2.1.3 — false positives and false negatives, and the precision/recall tradeoff that governs pattern design.
[^jm-norm]: **Jurafsky & Martin**, §2.4 — Text Normalization: the three standard steps of tokenizing words, normalizing word formats, and segmenting sentences.
[^jm-bpe]: **Jurafsky & Martin**, §2.4.3 — Byte-Pair Encoding: the unknown-word problem, subword tokenization, and the token-learner / token-segmenter split, with the low/newer/wider worked corpus.
[^jm-porter]: **Jurafsky & Martin**, §2.4.4 — Word Normalization, Lemmatization and Stemming: morphological parsing into stems and affixes, the Porter stemmer's cascade of rewrite rules, and its over- and under-generalization errors.
[^sennrich]: **R. Sennrich, B. Haddow, A. Birch**, "Neural Machine Translation of Rare Words with Subword Units," _Proceedings of ACL_, 2016 — reintroduces byte-pair encoding (originally Gage, "A New Algorithm for Data Compression," 1994) as an open-vocabulary tokenization for neural MT, improving translation of rare and unseen words by spelling them from subword units in a single fixed vocabulary.
[^kudo]: **T. Kudo**, "Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates," _Proceedings of ACL_, 2018 — the unigram-language-model tokenizer, which fits a unigram distribution over a candidate subword vocabulary and prunes by likelihood, and can sample among segmentations; packaged with BPE in T. Kudo & J. Richardson, "SentencePiece," _EMNLP (system demonstrations)_, 2018. WordPiece is M. Schuster & K. Nakajima, "Japanese and Korean voice search," _ICASSP_, 2012.