Capstone: build a mini search engine
Combine tokenizing, stop words, an inverted index and TF-IDF into a working search engine.
- Build an inverted index that finds documents by word in an instant
- Rank matching documents by TF-IDF
- Explain how real search engines go further
Time to put the pieces together. A search engine answers “which of my documents best match these words?” You already have every tool you need: tokenizing and normalizing text, dropping stop words, and TF-IDF to weigh terms. The one new idea is how to find matching documents quickly.
The inverted index
Reading every document for every search is far too slow. Instead, build an inverted index once: a dictionary from each word to the documents that contain it - like the index at the back of a book. A query then only touches the documents listed under its words.
1import re
2from collections import defaultdict
3
4documents = ["Cats chase mice", "Dogs chase cats", "Mice eat cheese"]
5index = defaultdict(set)
6for number, document in enumerate(documents, start=1):
7 for word in re.findall(r"[a-z]+", document.lower()):
8 index[word].add(number)
9print(sorted(index["chase"]), sorted(index["mice"]))[1, 2] [1, 3]
Try it
Rank by hand
Imagine searching for cat food. Click cat and then food to see each term’s TF-IDF in each page, and add the two numbers per page. Which page does TF-IDF rank first? Is that the page you would want at the top?
Pick a term
Page 1
Choosing cat food: wet food or dry food for your cat.
- tf
- 0.091
- idf = ln(3/1)
- 1.099
- tf × idf
- 0.100
Top term here: food
Page 2
Cat cat cat! The cat sat. A cat nap for the cat.
- tf
- 0.000
- idf = ln(3/1)
- 1.099
- tf × idf
- 0.000
Top term here: cat
Page 3
Dog food reviews: the best food for a happy dog.
- tf
- 0.000
- idf = ln(3/1)
- 1.099
- tf × idf
- 0.000
Top term here: dog
“choosing” appears in 1 of 3 documents.
Surprise: plain TF-IDF puts Page 2 first (0.203 vs 0.184), even though it never mentions food - it just repeats “cat” six times. Real search engines guard against this: BM25, the standard refinement of TF-IDF, gives diminishing credit for each repeat of a word, and good ranking rewards pages that cover all the query words. Your own ranking exercise below will put Page 2 first too - that is the correct TF-IDF result, and a reminder to sanity-check a ranking function on real queries.
Key takeaways
An inverted index maps each word to the documents containing it, built once and reused for every query.
Score matching documents by summing the TF-IDF of the query terms, then sort.
Process queries exactly like documents - the same tokenizer, case and stop words - or they won’t match.
Lesson quiz
5 questions · pass with 4 correct · up to 50 XP
Passing this quiz completes the lesson and keeps your streak going. Questions you miss come back in review sessions later.
Practice: apply NLP with Python
Try each text-processing idea in Python, run it against sample inputs, and use the results to see where the method works or falls short.
Build an inverted index
The first line is N, followed by N documents, one per line (document numbers start at 1). Use lowercase alphabetic words. Print every word in alphabetical order as word: numbers, with the document numbers in increasing order and separated by spaces.
- Three documents
- Repeated word
Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.
Rank documents for a query
The first line is N, followed by N documents, then a query line. Use lowercase alphabetic words everywhere.
Score each document as the sum, over the distinct query words, of tf × idf with tf = count in document / words in document and idf = ln(N / documents containing the word) (a word in no document adds 0). Print the documents with a score above 0, best first (ties: lower number first), as doc NUMBER: SCORE with the score rounded to 3 decimals. If nothing matches, print no results.
- cat food
- No matches
Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.
Questions about this lesson
Stuck? Ask. Figured something out? Share it. Explaining is one of the best ways to learn.
Loading posts…