Regular Expressions and 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.¹ 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$.² 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.)

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:

So /colou?r/ matches color and colour; /a*/ matches $\epsilon ,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, notguppy 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:

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.

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}$,

Tightening to cut $\mathrm{FP}$ raises precision; loosening to cut $\mathrm{FN}$ raises recall. Every pattern trades one against the other.³

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.⁴

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.⁵

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$.

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.

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.

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.⁶ A sampling of its rules:

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.⁷ 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.

• 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.
• 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.⁸ 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.