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.