Course contentsShow
← System Design
Lesson 1744 of 1,91942. Real-World System: Search and TypeaheadFree lesson

Building an Inverted Index: Tokenization

Breaking text into searchable tokens through normalization, stemming, and stop-word removal.

Building an Inverted Index: Tokenization

You'll learn how to transform raw text into clean, searchable tokens that power fast and accurate search queries.

When you build an inverted index, you can't simply store text as-is. The phrase "Running quickly!" and "run quick" should both match a search for "run". Tokenization is the process of breaking raw text into standardized, searchable units called tokens.

The Three-Stage Tokenization Pipeline

1. Normalization Convert text to a consistent format. This typically means:

  • Lowercasing: "Apple" → "apple"
  • Removing punctuation: "hello!" → "hello"
  • Handling special characters and Unicode

2. Stemming/Lemmatization Reduce words to their root form so variants match together:

  • "running", "runs", "ran" → "run"
  • "better" → "good" (lemmatization)
  • "connectivity" → "connect" (stemming)

Stemming uses algorithmic rules (Porter Stemmer), while lemmatization uses dictionaries for linguistic accuracy.

3. Stop-Word Removal Filter out common words that add little search value:

  • Remove: "the", "a", "is", "and", "of"
  • Keep: "apple", "search", "algorithm"

This reduces index size dramatically (often 30-40% smaller) and speeds up queries.

Example Transformation

Input:  "The Quick Brown Fox Jumps!"
Tokens: ["quick", "brown", "fox", "jump"]

Notice: lowercased, punctuation removed, "The" filtered out, "Jumps" stemmed to "jump".

The Trade-Off

Aggressive tokenization improves matching but loses precision. Searching "New York" might incorrectly match "new ideas in york" if you remove all context. Modern systems balance this with n-grams and phrase indexing.

Key Takeaway: Tokenization transforms messy real-world text into clean, searchable tokens through normalization, stemming, and stop-word removal—the foundation of every inverted index.