Text Preprocessing: Tokenization, Stemming, Lemmatization

A food-delivery app processes tens of millions of reviews a year. Somewhere in Bengaluru a backend engineer builds a feature: type a word into the review-search box for a restaurant, and every review containing that word (or something close to it) should surface. A user searches "spicy". The database holds reviews containing "spicy," "spicier," "spiciest," "spiced," "spicing" — five distinct strings, one shared idea. A naive index built on exact string match returns only the first. Four honest, relevant reviews vanish from the results, and the engineer gets a bug report that says, unhelpfully, "search is broken."

It isn't broken. It's missing a preprocessing step. Before any of these words reach an index, a ranking model, or a language model's embedding table, they pass through a pipeline with three distinct jobs: cut the raw character stream into meaningful units (tokenization), then collapse related surface forms of a word down to a common representation, either by blind rule (stemming) or by dictionary lookup (lemmatization). This chapter builds all three from first principles, with every claimed output independently traced or executed — not asserted.

The preprocessing pipeline: three distinct jobs

Keep these three jobs separate in your head, because conflating them is where most confusion about this topic starts.

• Tokenization decides where one unit of meaning ends and the next begins. Input: a raw string. Output: a sequence of tokens. It never removes information about word identity — it only draws boundaries.
• Stemming takes a token and chops off its suffix using a fixed set of rewrite rules, with no knowledge of grammar, dictionaries, or the token's role in the sentence. It is fast and crude by design.
• Lemmatization takes a token, plus (usually) its part of speech, and looks up its dictionary headword — its lemma — using a lexicon and a table of morphological patterns. It is slower and linguistically correct by design.

Search engines and classical information-retrieval (IR) systems typically want stemming: crude, fast, aggressive collapsing that maximizes recall. Machine translation, question answering, and any pipeline whose output a human reads typically wants lemmatization: an output that is still a real, grammatical word. Neither is a substitute for the other — a claim the "misconception" section below defends with a specific counterexample, not just an assertion.

Tokenization: splitting text is harder than .split()

The first instinct is to split on whitespace. Try it on a sentence an IRCTC customer-support bot might actually receive:

>>> text = "Don't book IRCTC's Tatkal for Rs.1,200/- @9pm, bhai bahut fast chahiye!! 🚄"
>>> text.split()
["Don't", 'book', "IRCTC's", 'Tatkal', 'for', 'Rs.1,200/-', '@9pm,', 'bhai', 'bahut', 'fast', 'chahiye!!', '🚄']

This looks reasonable until you look closely. "Rs.1,200/-" is one token that actually bundles a currency marker, a decimal-grouped number in the Indian numbering system (lakh-style comma placement), and a suffix meaning "approximately" — three separate pieces of meaning glued together. "chahiye!!" bundles a Hindi verb with English-script punctuation. "Don't" is a contraction hiding two words, "do" and "not," which matters if a downstream parser needs to see the negation as a separate token. A regex that instead keeps only word characters looks like it fixes the punctuation problem:

>>> import re
>>> re.findall(r"\w+", text)
['Don', 't', 'book', 'IRCTC', 's', 'Tatkal', 'for', 'Rs', '1', '200', '9pm', 'bhai', 'bahut', 'fast', 'chahiye']

It doesn't fix anything — it trades one failure mode for a worse one. "Don't" is now shattered into the meaningless fragments 'Don' and 't'. The price amount is now three disconnected tokens, 'Rs', '1', '200', with the relationship between them thrown away. The emoji is silently dropped, which may or may not be acceptable depending on whether the downstream sentiment model uses emoji as a signal (it usually should — an angry review with a 🚄 delay emoji carries information). Neither rule is wrong in general; both are wrong for specific, predictable classes of input, which is exactly why production systems build long, hand-tuned lists of exceptions (currency symbols, honorifics, known contractions, URL and hashtag patterns) on top of a base regex.

Worked example: byte-pair encoding builds a subword vocabulary

Rule-based tokenizers hit a second wall: no fixed rule set anticipates every word a model will ever see, especially rare brand names, transliterated Hindi, or a typo. Modern NLP systems — the transformer-based language models you've already met in this course — solve this with a data-driven approach called Byte-Pair Encoding (BPE). Instead of hand-writing rules, BPE learns a vocabulary of subword pieces directly from a training corpus by repeatedly merging the most frequent adjacent pair of symbols.

Start every word as a sequence of characters plus an end-of-word marker </w>, so that the boundary between words is never lost. Take this five-word toy corpus with frequencies, small enough to trace by hand and verified here by running the algorithm exactly as specified:

corpus = {"low": 5, "lowest": 2, "newer": 6, "wider": 3, "new": 2}

# each word split into characters + end marker, weighted by its frequency
l o w </w>        (×5)
l o w e s t </w>  (×2)
n e w e r </w>    (×6)
w i d e r </w>    (×3)
n e w </w>        (×2)

At every step, count every adjacent symbol pair across the whole weighted corpus and merge whichever pair occurs most often. Trace of the first three merges, with the counts that decide each merge:

merge 1: pair ('e','r') appears 6 (in newer) + 3 (in wider) = 9 times — the most frequent pair
         → merge into "er". "newer" becomes n e w er </w>, "wider" becomes w i d er </w>

merge 2: pair ('er','</w>') now appears 6 + 3 = 9 times
         → merge into "er</w>"

merge 3: pair ('n','e') appears 6 (newer) + 2 (new) = 8 times
         → merge into "ne"

Five more merges follow the same rule — always the single most frequent adjacent pair — and after 8 merges the vocabulary has learned low</w>, newer</w>, and er</w> as whole learned units, while lowest remains split as low e s t </w> because "est" never became frequent enough in this tiny corpus to earn its own merge. This is the exact, unedited output of running the standard BPE training loop on the corpus above:

merge 1: ('e', 'r')     -> {'l o w </w>': 5, 'l o w e s t </w>': 2, 'n e w er </w>': 6, 'w i d er </w>': 3, 'n e w </w>': 2}
merge 2: ('er', '</w>') -> {'l o w </w>': 5, 'l o w e s t </w>': 2, 'n e w er</w>': 6, 'w i d er</w>': 3, 'n e w </w>': 2}
merge 3: ('n', 'e')     -> {..., 'ne w er</w>': 6, 'w i d er</w>': 3, 'ne w </w>': 2}
merge 4: ('ne', 'w')    -> {..., 'new er</w>': 6, 'new </w>': 2}
merge 5: ('l', 'o')     -> {'lo w </w>': 5, 'lo w e s t </w>': 2, ...}
merge 6: ('lo', 'w')    -> {'low </w>': 5, 'low e s t </w>': 2, ...}
merge 7: ('new', 'er</w>') -> {..., 'newer</w>': 6, ...}
merge 8: ('low', '</w>')   -> {'low</w>': 5, 'low e s t </w>': 2, 'newer</w>': 6, 'w i d er</w>': 3, 'new </w>': 2}

This is precisely how a transformer's tokenizer handles a word it has never seen: an unfamiliar Hindi transliteration like "chahiye" gets no whole-word entry, so it is represented as a sequence of learned subword pieces such as cha + hi + ye — still consistent, still reversible, never dropped as an unknown token. This is also why subword tokenization has mostly replaced whitespace and regex splitting for anything that feeds a neural model, while the older rule-based tokenizers remain common in classical IR pipelines and simpler rule-based text tools where interpretability matters more than open-vocabulary coverage.

Stemming: chopping suffixes by rule, not by meaning

Once text is tokenized, the search-index problem from the opening scenario resurfaces: "spicy", "spicier", and "spiciest" are three distinct tokens after tokenization. Stemming collapses them by rule. The dominant classical algorithm, and still the one taught first, is the Porter Stemmer (Martin Porter, 1980) — a fixed sequence of five rule steps applied in order, each step conditioned on a quantity called the measure (m) of the stem: roughly, the number of consonant-vowel-consonant "syllable-like" groups in what's left of the word, which the algorithm uses to decide whether a stem is "long enough" to safely lose a suffix without disappearing entirely.

Trace the algorithm on "running". Step 1b looks for the suffixes -ed or -ing, and only strips them if what remains contains a vowel (this guards against stripping "-ing" off a word like "sing," where nothing would be left). Stripping "-ing" from "running" leaves "runn," which contains the vowel "u," so the strip proceeds, leaving "runn." The algorithm then checks whether the result ends in a doubled consonant that is not l, s, or z — "runn" ends in doubled "n" — and if so, deletes the final letter. That produces "run." Every step here is a mechanical, context-blind rule; the algorithm has no idea "running" is a verb, and doesn't need to.

Now trace three related words through the same fixed rule set — this is the exact output of running the algorithm (not a paraphrase):

university -> univers
universe   -> univers
universal  -> univers

All three collapse onto the same non-word stem. This is not a bug in one particular implementation — it is a structural property of any suffix-stripping algorithm: "university" loses "-iti" (a later rule step, triggered once the trailing "y" has already been rewritten to "i" by an earlier step) once the remaining stem is judged long enough; "universe" independently loses its trailing "-e" for the same reason; "universal" loses "-al." Three genuinely different words — an institution, a cosmos, and an adjective meaning "applying to everything" — become indistinguishable. For a search index that wants to catch "university reviews" when someone searches "universities," this is a feature: recall goes up, because one indexed stem now matches every inflected form. But it is also the classic textbook illustration of over-stemming: the algorithm has fused words that a human would never treat as synonyms.

The opposite failure, under-stemming, happens when related forms of a genuine single word fail to collapse to the same stem because they don't share enough surface structure for any rule to catch — for instance, irregular forms like "went" and "go" share no suffix at all, so no suffix-stripping rule can ever unify them; Porter stemming leaves both untouched. Stemming can only ever exploit shared spelling, never shared meaning.

Lemmatization: looking words up instead of cutting them

Lemmatization solves the same collapsing problem with a completely different mechanism: dictionary lookup instead of rule-based deletion. A lemmatizer needs two extra pieces of information a stemmer doesn't use — a lexicon of valid dictionary headwords for each part of speech, and (ideally) the part of speech (POS) of the word being processed, because the correct lemma genuinely depends on it.

The algorithm, in the shape used by real systems like WordNet's morphological processor: first check whether the (word, POS) pair is a known irregular form via an exception table — this catches cases no general rule could ever derive, like "went" (verb) mapping to "go," or "better" (adjective) mapping to "good." If there's no exception match, check whether the surface word is already a valid dictionary headword for that POS — if so, return it unchanged. Otherwise, apply the language's regular morphological patterns (strip "-s," rewrite "-ies" to "-y," and so on) to produce a candidate, and only accept that candidate if it is actually found in the dictionary for that POS. This last check is exactly what a stemmer skips, and it's exactly what keeps the output a real word.

A minimal but faithful implementation, with a small hand-built lexicon and exception table, run and verified below:

LEXICON = {("study","NOUN"), ("study","VERB"), ("good","ADJ"), ("go","VERB"),
           ("mouse","NOUN"), ("leaf","NOUN"), ("leave","VERB")}
EXCEPTIONS = {("went","VERB"): "go", ("better","ADJ"): "good", ("best","ADJ"): "good",
              ("mice","NOUN"): "mouse", ("leaves","NOUN"): "leaf"}

def lemmatize(word, pos):
    if (word, pos) in EXCEPTIONS:
        return EXCEPTIONS[(word, pos)]
    if (word, pos) in LEXICON:
        return word
    candidates = []
    if word.endswith("ies"):
        candidates.append(word[:-3] + "y")
    if word.endswith("s"):
        candidates.append(word[:-1])
    for c in candidates:
        if (c, pos) in LEXICON:
            return c
    return word

for w, p in [("studies","NOUN"), ("leaves","NOUN"), ("leaves","VERB"),
             ("went","VERB"), ("better","ADJ")]:
    print(w, p, "->", lemmatize(w, p))

# studies NOUN -> study
# leaves  NOUN -> leaf
# leaves  VERB -> leave
# went    VERB -> go
# better  ADJ  -> good

Worked example: same suffix, two different lemmas

The "leaves" row above is the clearest possible demonstration of why POS matters for lemmatization and cannot matter for stemming. Run "leaves" through the Porter stemmer verified earlier and it produces the non-word "leav" regardless of context — the plural noun (tea leaves) and the third-person verb (the train leaves at 9pm) are indistinguishable to a rule that only ever looks at spelling. A lemmatizer, given the POS tag from a prior POS-tagging stage, produces two different, correct, real words: "leaves" as a noun lemmatizes to "leaf" (an irregular plural, caught only because it sits in the exception table — no regular rule derives "leaves" from "leaf"), while "leaves" as a verb lemmatizes to "leave" (a regular "-s" strip that lands on a valid dictionary verb). Same six letters, same suffix, two entirely different, entirely correct outputs — something no suffix-stripping rule could ever produce, because a stemmer never sees a POS tag in the first place.

The misconception: "lemmatization is just a more accurate stemmer, so always use it"

The natural assumption, once you've seen lemmatization produce real words while stemming produces garbage like "studi" and "univers," is that lemmatization simply dominates — it does the same job, correctly, so there's no reason ever to reach for the cruder tool. This is wrong on two independent grounds.

First, cost. Lemmatization needs a POS tagger to run first (to know whether "leaves" is a noun or a verb) and a dictionary lookup against a large lexicon for every token. Stemming needs neither — it's a fixed, small set of string-rewrite rules with no external dependency, which makes it orders of magnitude cheaper to run over a corpus of tens of millions of reviews. For a search index being rebuilt nightly over the app's entire review corpus, that cost difference is not academic.

Second, and more fundamentally, the two algorithms optimize for opposite things. A search index built for recall — don't miss a relevant document — actively benefits from stemming's over-aggressive collapsing. When "university" and "universe" both index to "univers," a search for "university reviews" will also surface a document that only says "universe," which is a false positive, but a search for "universities" will now correctly match a document that only ever said "university" — a true positive that a lemmatizer, which correctly keeps "university" and "universities" as the same lemma but would never touch "universe," would not have introduced as noise in the first place, at the cost of exactly this kind of harmless mismatch. IR systems have historically accepted this trade because for search, a few noisy matches ranked low are a much smaller problem than a relevant result missing entirely. Machine translation, grammar checking, and text generation cannot make this trade at all — if a translation system's output lemma "univers" appeared in a translated sentence, it would simply be wrong, not "over-inclusive." That system needs a real, grammatical word every time, which only dictionary-based lemmatization guarantees. The correct framing is not "lemmatization is better," but "the two algorithms make different, deliberate trade-offs between precision, recall, and computational cost — pick the one whose trade-off matches the downstream task."

How the pieces connect

The diagram below traces one token, "studies," through the full pipeline this chapter has built, side by side with the stemmer path and the lemmatizer path, using the exact traced outputs verified above.

Active recall

Attempt every question before reading its answer.

1. Run both "Flight AI-202 departs @ 6:45am, ~2hrs delay expected!".split() and re.findall(r"\w+", ...) on the same string mentally. Name one specific piece of information each approach destroys.
2. Why does the Porter stemmer reduce "university", "universe", and "universal" all to "univers"? Is this a bug in one particular implementation?
3. A lemmatizer sees the word "leaves" twice, once tagged NOUN and once tagged VERB. What two different outputs should it produce, and why can a stemmer never do this?
4. In the BPE trace, why does the pair ('e','r') get merged before ('n','e'), even though "new" and "newer" together contribute more raw character occurrences of "n" and "e" than "newer" and "wider" contribute of "e" and "r"?
5. You're building the nightly index-rebuild job for a restaurant-review search feature that runs over 40 million reviews. Would you choose stemming or lemmatization for the indexing step, and what's the one-sentence justification?
6. A teammate says: "We should always lemmatize instead of stem — it produces real words, so it's strictly more correct." What is the flaw in this reasoning?

Answers

1. .split() keeps "AI-202" and "6:45am," intact as single tokens but leaves trailing punctuation stuck to real content (the comma stuck to the time, the exclamation mark stuck to "expected"). The regex \w+ approach strips that punctuation cleanly but destroys structure instead: it splits "AI-202" into the meaningless fragments 'AI' and '202', losing the fact that they form one flight number, and splits "6:45am" into '6' and '45am', losing the time structure entirely. Neither approach is strictly better; each destroys a different kind of information.
2. It is a structural property of any suffix-stripping algorithm, not an implementation bug. All three words share the substring "univers" once their respective suffixes ("-ity" via the "y→i" rewrite, "-e", "-al") are judged removable by the algorithm's fixed rules. The algorithm only ever looks at spelling and a "stem is long enough" length heuristic (the measure m) — it has no way to know that a university, the universe, and something described as universal are three unrelated concepts, because it never consults meaning at all.
3. NOUN "leaves" should lemmatize to "leaf" (the irregular plural of a tree leaf, unrecoverable by any regular rule and caught only via an exception table), and VERB "leaves" should lemmatize to "leave" (the regular third-person present tense of the verb "to leave," recovered by stripping "-s" and confirming "leave" is a valid dictionary verb). A stemmer can never produce this split because it has no POS input at all — it sees six identical letters and applies the same rule regardless of grammatical role, which is exactly why the Porter stemmer collapses both to the same non-word, "leav."
4. BPE merges whichever pair has the highest total frequency, not the pair whose individual characters are most common. ('e','r') occurs as an adjacent pair 6 times in "newer" and 3 times in "wider," for 9 total pair occurrences. ('n','e') only becomes available as a pair after nothing blocks it, and even then it occurs 6 times in "newer" and 2 times in "new," for 8 total — one less than ('e','r'). The algorithm counts adjacent pairs, never individual character frequency, so it merges the pair with 9 occurrences first.
5. Stemming. An index-rebuild job over 40 million reviews is a recall-oriented, throughput-bound batch job: it needs to run fast without a POS tagger in the loop, and a search index actively benefits from stemming's aggressive collapsing of inflected forms into one lookup key, at the acceptable cost of occasional unrelated words sharing a stem.
6. The flaw is treating "produces real words" as the only criterion that matters. Lemmatization requires a POS tagger and a large dictionary lookup for every token, which costs far more compute than a fixed rule table, and its more conservative collapsing (it keeps "university" and "universe" separate, correctly) means it will miss some of the recall gains a search system wants from aggressive stemming. The two algorithms trade off precision, recall, and cost differently — neither one dominates the other across every task.

Think About It

Think about this: How would you explain text preprocessing: tokenization, stemming, lemmatization to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where text preprocessing: tokenization, stemming, lemmatization is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting text preprocessing: tokenization, stemming, lemmatization to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind text preprocessing: tokenization, stemming, lemmatization, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.