Text Preprocessing and Tokenization

Text preprocessing is the umbrella term for the transformations applied to raw text before any statistical or learned model sees it. It has three canonical stages. Normalization standardizes superficial variation — case, Unicode encoding, whitespace, accents — so that `Café`, `café`, and `CAFÉ` are not treated as three unrelated symbols unless that distinction matters for the task. Sentence segmentation (or sentence boundary detection) splits a document into individual sentences, which matters because many downstream algorithms — parsers, translation systems, many classic language models — operate one sentence at a time. Tokenization is the final and most consequential step: splitting a sentence (or document) into a sequence of tokens, the atomic units the model will assign IDs to and embed as vectors. The central design tension in tokenization is granularity. A word-level tokenizer treats each token as a full word, delimited roughly by whitespace and punctuation; it produces intuitive units but suffers from an unbounded vocabulary and cannot represent words never seen during training (the out-of-vocabulary, or OOV, problem). A character-level tokenizer uses individual characters as tokens; its vocabulary is tiny and there is no OOV problem, but sequences become very long and the model must learn to compose meaning from scratch out of characters, which is statistically harder. Subword tokenization is the modern compromise: common words remain single tokens, while rare or novel words are decomposed into meaningful or frequency-derived pieces (`unfriendable` → `un`, `friend`, `able`). This gives a bounded vocabulary, no OOV problem (any string can be built from a base alphabet), and reasonably short sequences. Formally, given a raw string $s$ over an alphabet $\Sigma$ (typically Unicode code points, or bytes), tokenization defines a function

mapping the string to a sequence of tokens drawn from a fixed vocabulary $V$, such that the tokens can be deterministically reassembled (or nearly so) into $s$. The vocabulary $V$ and the function $T$ are typically learned jointly from a large text corpus rather than hand-specified, which is what distinguishes modern subword tokenizers from older whitespace-and-regex tokenizers. This connects directly forward to Morphology and Stemming, since good subword splits often approximate morpheme boundaries, and to N-gram Language Models and the Bag-of-Words Model, both of which are defined over whatever token sequence this pipeline produces.

The pipeline runs in three ordered stages. Each stage is described below with its dominant classical algorithm, followed by the modern subword algorithm (Byte-Pair Encoding) used at training and inference time in most contemporary systems.

Stage 1 — Normalization. Typical steps, applied in this order because later steps assume earlier ones are done: 1. Unicode normalization — collapse equivalent representations of the same character (e.g., `é` as one code point vs. `e` + combining accent) into a canonical form (commonly Unicode Normalization Form NFC or NFKC). 2. Case folding — optionally lowercase all text, trading away case information (useful for retrieval, harmful for tasks where `US` vs `us` or named-entity capitalization matters). 3. Whitespace and control-character cleanup — collapse runs of whitespace, strip non-printing characters. 4. Punctuation and contraction handling — decide whether `it's` becomes one token, two (`it`, `'s`), or is left untouched, and whether trailing punctuation is split off a word.

Stage 2 — Sentence segmentation. The naive approach splits on `.`, `!`, `?`. The problem is that `.` is wildly ambiguous: it ends sentences, but also appears in abbreviations (`Dr.`), decimal numbers (`3.14`), ellipses (`...`), initials (`J. R. R. Tolkien`), and URLs. A robust segmenter therefore treats sentence-boundary detection as a binary classification problem: for every candidate boundary character, decide boundary or not boundary using features like:

• Is the token before the `.` in a known abbreviation list (`Dr`, `Mr`, `vs`, `etc`)?
• Is the character after the `.` uppercase, lowercase, or a digit?
• Is the `.` followed by whitespace and then a capital letter?
• Length and case pattern of the preceding token.

This can be implemented with hand-written rules, a decision tree, or a small logistic-regression classifier trained on labeled boundary/non-boundary examples — the same statistical-classifier idea reused throughout classical NLP.

Stage 3 — Word/subword tokenization. The classical rule-based approach applies an ordered cascade of regular expressions (split on whitespace, then peel off punctuation, then special-case contractions and abbreviations). The modern data-driven approach is Byte-Pair Encoding (BPE): start from individual characters (or bytes) and iteratively merge the most frequent adjacent pair into a new symbol, building a vocabulary of subword units directly from corpus statistics. ``` ALGORITHM: Byte-Pair Encoding — Vocabulary Learning INPUT: corpus of words with frequencies, e.g. {"low": 5, "lower": 2, "newest": 6, "widest": 3} target vocabulary size V OUTPUT: ordered list of merge rules, final vocabulary 1. Represent every word as a sequence of characters, plus a special end-of-word marker "_", e.g. "low" -> [l, o, w, _] 2. vocab <- set of all individual characters/symbols seen 3. merges <- empty ordered list 4. while |vocab| < V: pairs <- count all adjacent symbol-pair occurrences across the ENTIRE corpus (respecting word frequencies) if pairs is empty: break // no more pairs to merge best <- pair with the highest count // ties broken deterministically new_symbol <- concatenate(best.left, best.right) replace every occurrence of best in the corpus with new_symbol add new_symbol to vocab append best -> new_symbol to merges 5. return merges, vocab ``` ``` ALGORITHM: Byte-Pair Encoding — Tokenizing New Text (inference) INPUT: word w, learned ordered list of merges OUTPUT: sequence of subword tokens 1. symbols <- list of characters of w, with end-of-word marker "_" 2. for each merge rule (a, b) -> ab, IN THE ORDER LEARNED during training: while (a, b) occurs as adjacent symbols in `symbols`: replace that occurrence with the merged symbol ab 3. return symbols ``` Two correctness-critical details are easy to miss. First, in training, pair counts must be computed over the whole corpus (weighted by word frequency) at every iteration, not just once at the start — after a merge, new adjacent pairs appear that did not exist before. Second, in inference, merges must be applied in the exact order they were learned, because BPE is a greedy, order-dependent algorithm: applying merges out of order can produce a different, invalid segmentation not seen during training. The full preprocessing pipeline, and where BPE sits inside it, is shown below.

Normalization is a linear scan: each character is inspected and rewritten a constant number of times, so it runs in $O(n)$ time and $O(n)$ space for a string of length $n$. Unicode normalization (NFC/NFKC) is also $O(n)$ in practice, since it is implemented as a bounded lookup and local recombination per character cluster.

Rule-based sentence segmentation and tokenization apply a fixed cascade of regular expressions or a finite-state scan over the string. Each character is visited a constant number of times across the cascade (assuming a bounded number of rules), giving $O(n)$ time. A classifier-based segmenter evaluates a constant-size feature vector at each candidate boundary (there are $O(n)$ candidates, one per punctuation mark), so it remains $O(n)$ overall, with a constant-factor overhead per boundary for the classifier's feature extraction and decision.

BPE training is more expensive. Let $n$ be the total number of (whitespace-separated) word tokens in the corpus, and let $V$ be the target vocabulary size (number of merges performed). A naive implementation recomputes all adjacent-pair counts from scratch at every iteration, costing $O(n)$ per iteration and $O(nV)$ overall. Efficient implementations maintain a priority queue of pair counts and only update counts for pairs adjacent to a merge site, giving an amortized cost close to $O(n \log n + n)$ across all merges in practice, since each merge only invalidates a bounded number of local pairs. Either way, training is a one-time offline cost paid once per corpus/vocabulary choice, not paid per inference call.

BPE inference (tokenizing one new word of length $L$ characters) applies at most $|merges|$ candidate merge rules, each requiring a scan of the current symbol list; a straightforward implementation costs $O(L \cdot M)$ where $M$ is the number of merge rules, but because each merge strictly reduces the symbol count and most rules do not match, well-engineered tokenizers (using a priority queue keyed by merge rank) bring this down to $O(L \log L)$ per word.

Correctness argument for BPE. The key invariant is: at every point in training, the current segmentation of the corpus is the unique result of greedily merging the most frequent pair first, given the merges done so far. This is true by construction — step 4 of the training algorithm literally selects the argmax pair and applies it corpus-wide before recomputing statistics, so no other segmentation is reachable at that step for a deterministic implementation with fixed tie-breaking. This greedy invariant is also what guarantees the inference algorithm reproduces training-consistent segmentations: because inference applies merges in the same order they were learned (i.e., the same greedy priority), the segmentation of a word seen during training is provably identical to its training-time segmentation, since it must follow the same locally-optimal merge order.

Honest tradeoffs. BPE's frequency-greedy criterion is not linguistically motivated — it will happily merge non-morphemic character pairs if they are frequent (e.g., merging across a genuine morpheme boundary), so subword units do not always align with true morphology, a gap that motivates studying Morphology and Stemming separately. Sentence segmentation via hand-written abbreviation lists is not robust to unseen abbreviations or new domains (biomedical text, social media); this is exactly why the field moved to trainable classifiers instead of static rule lists. Word-level tokenizers guarantee interpretable tokens but an unbounded, corpus-dependent vocabulary; character-level tokenizers guarantee a small vocabulary but longer sequences and a harder learning problem for whatever model consumes them, since more computation is spent per unit of meaning; subword methods sit at a Pareto-favorable point but introduce a training-time hyperparameter (target vocabulary size $V$) that must be tuned rather than derived.

Trace the sentence: `"Dr. Smith paid $3.50 for the app—it's amazing!! Isn't that great?"`

Step 1: Normalization. Lowercase (task-dependent choice; here we keep case for named entities but normalize whitespace and the em-dash to a standard hyphen): ``` Dr. Smith paid $3.50 for the app-it's amazing!! Isn't that great? ```

Step 2: Sentence segmentation. The classifier scans each `.`, `!`, `?`:

Result: two sentences. ``` S1: Dr. Smith paid $3.50 for the app-it's amazing!! S2: Isn't that great? ```

Step 3: Word tokenization (rule-based baseline). Split on whitespace, then peel punctuation, special-casing abbreviations and contractions: ``` S1 -> [Dr., Smith, paid, $, 3.50, for, the, app, -, it, 's, amazing, !, !] S2 -> [Is, n't, that, great, ?] ``` Note the deliberate choices: `Dr.` stays fused (abbreviation exception), `$3.50` splits the currency symbol from the amount but keeps the decimal number intact (a digit-aware rule), and `it's` / `Isn't` split into a stem and a clitic (`it` + `'s`, `Is` + `n't`) using a small contraction lookup table — this is a classic hand-crafted exception list, and different tokenizers (e.g., the Penn Treebank tokenizer vs. spaCy's) disagree on the exact split point for `n't`.

Step 4: Subword tokenization (BPE), assuming `amazing` is rare in the training corpus but `Smith`, `paid`, `for`, `the` are common enough to be single tokens. Suppose the learned merges include `am`, `az`, `ama`+`zing` not yet fully fused. A plausible BPE output for the rare word: ``` amazing -> [am, az, ing] (three subword pieces, none is "amazing" itself) ``` while common short words remain intact: ``` Smith -> [Smith] paid -> [paid] ``` The full subword token stream for S1 might look like: ``` [Dr., Smith, paid, $, 3, ., 50, for, the, app, -, it, 's, am, az, ing, !, !] ``` Every piece here is drawn from a fixed, bounded vocabulary learned once from a training corpus — this is the property that lets a model handle `amazing` even if the literal word `amazing` never appeared during vocabulary construction, so long as its subpieces did. This is precisely the OOV-robustness property that makes subword tokenization the default choice in essentially every modern transformer-based system, feeding directly into the fixed-size embedding lookup tables discussed when studying language models built on top of this token stream.

Tokenization as an explicit, statistically-grounded problem grew out of two threads: information-theoretic data compression, and the corpus-linguistics tradition of building annotated, hand-tokenized reference corpora (like the Penn Treebank) that made the ambiguity of "what is a token" concrete and measurable. Byte-Pair Encoding itself began life as a compression algorithm, later repurposed for open-vocabulary neural translation, illustrating how ideas migrate across subfields of computer science.

Every major transformer-based language model — BERT, GPT-family models, T5, and their successors — begins with a learned subword tokenizer (BPE, WordPiece, or Unigram/SentencePiece variants), whose vocabulary size (commonly 30,000 to 100,000+ tokens) is fixed before training and baked permanently into the model's embedding table. Search engines rely on normalization and tokenization to match a user's query against indexed documents despite case and punctuation differences. Machine translation systems use subword tokenization specifically to handle rare names, morphologically rich languages (Finnish, Turkish), and code-switching without ever hitting an unknown-word wall. Speech-to-text and text-to-speech pipelines depend on sentence segmentation to chunk long transcripts into units suitable for prosody modeling. Even simple applications — spell checkers, autocomplete, keyword search — sit on the same normalize-segment-tokenize foundation described here, making this pipeline one of the few pieces of NLP infrastructure that essentially every downstream system, from the classical Bag-of-Words Model to the largest modern LLMs, depends on directly.

Ask the tutor: How would you design a tokenizer that handles both English and Chinese text robustly in the same vocabulary?