Topic 8.2
Keyword Search First
In one line
An inverted index lists, for every word, the documents that contain it. TF-IDF scores a match higher when the word is frequent in the document and rare across all documents. This simple search is a strong baseline that real systems still use.
Think of it like this
The index at the back of a textbook. You do not read 500 pages to find "photosynthesis". You open the index, see "photosynthesis: pages 12, 87, 143" and jump there. An inverted index is that index for a computer: it flips "document contains words" into "word is in these documents".
Words you'll meet
New words in this topic, in plain English. Come back here whenever one feels fuzzy.
- Token (here)
- A word cut out of the text: lower-case letters and digits. (Model tokens in Phase 1 are different pieces.)
- Inverted index
- A table from each word to the list of documents that contain it.
- Postings list
- The list of document numbers for one word in an inverted index.
- Term frequency (tf)
- How many times a word appears in one document.
- Document frequency (df)
- How many documents contain the word at least once.
- IDF
- Inverse document frequency, log(N / df): high for rare words, 0 for words in every document.
- Tie-breaker
- A rule that orders items with equal scores, so results are the same every run.
- BM25
- The standard improvement of TF-IDF with length normalisation. Used by most keyword search engines.
Step by step
01Step 1: the problem with scanning
Searching eight documents by looking at all of them is fine. Searching eight million is not. The fix is to do the work once, ahead of time, and keep a lookup table.
02Step 2: tokenise
Lower-case the text and keep runs of letters and digits. Both the documents and the query go through the same function. Using different tokenisers for the two is a classic bug: nothing matches, and nothing crashes.
import re
def tokenize(text):
return re.findall("[a-z0-9]+", text.lower())
print(tokenize("Bikes can be returned within 30 days!"))
# ['bikes', 'can', 'be', 'returned', 'within', '30', 'days']03Step 3: build the inverted index
Loop over the documents, add each distinct word's document number to its list. The first example prints a few lists and three searches, including bike versus bikes and a paraphrase that finds nothing.
04Step 4: rank with tf and idf
Count how many documents have each word (df), turn that into idf, and score each document as the sum of tf × idf over the query words. The second example prints idf for every query word and the ranked documents. Check one score by hand with the numbers in the lesson.
05Step 5: see the flaws
Words absent from every document (how, many) contribute nothing, which is right. Common small words such as for still add points, which is why real systems drop stop words or use BM25. And no amount of tf-idf will connect "money back" to "refund".
Try it yourself
- 1
Predict a score
Change the query to
warranty. Using idf = ln(8/1) = 2.0794 and the fact that the warranty document says it twice, predict the top score before you run it. - 2
Make the paraphrase work
In the first example, search for
refundand then forget my money back. Which words in your query would you have to add by hand to find the returns document? This is the gap vector search closes. - 3
Add a stop-word list
Make
scoreskip the wordsfor,the,aandis. Does the ranking of the four documents change?
Code & diagrams
Document numbers start at 1 so they match the numbered sources used later in the phase.
Expected output
8 documents, 82 different words
days: returns, shipping, repairs
warranty: warranty
bike: repairs, helmets
bikes: returns, payment
the: returns, repairs, hours, battery
search 'free helmet' -> helmets
search 'bike' -> repairs, helmets
search 'get my money back' -> nothingN = 8 documents. Scores are rounded to four decimals before sorting, so the order is the same in all three languages.
Expected output
query: how many days for shipping
how: in 0 of 8 documents, idf 0.0000
many: in 0 of 8 documents, idf 0.0000
days: in 3 of 8 documents, idf 0.9808
for: in 2 of 8 documents, idf 1.3863
shipping: in 1 of 8 documents, idf 2.0794
6.1205 shipping
2.3671 returns
1.3863 payment
0.9808 repairsBreak it on purpose
Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.
Break #1
Tokenise the query differently
In the first example, change the search so the query is not lower-cased: replace tokenize(query) inside search_all with query.split(), and also change the first query from "free helmet" to "Free helmet".
Myth vs fact
Myth
Keyword search is obsolete now that we have embeddings.
Fact
It is exact, fast, cheap and explainable, and it is often better for names, codes and rare terms. Strong systems combine both.
Myth
A higher score means a more correct answer.
Fact
Scores only order candidates for one query. They are not probabilities and cannot be compared across different queries.
Myth
More matching words always means a better document.
Fact
Common words match everywhere. That is exactly what idf discounts, and why length normalisation (BM25) exists.
Pro corner
Extra depth for experienced readers. New to this? Skip it for now and come back later.
- ▸
An inverted index trades memory and build time for fast lookups, and it can be updated incrementally. Search engines such as Lucene-based systems (Elasticsearch, OpenSearch) and databases with full-text search implement this idea with BM25 ranking.
- ▸
Tokenisation choices (case, stemming, stop words, handling of numbers and code identifiers) change recall and precision more than the scoring formula does. Change them deliberately and re-test.
- ▸
Round scores before comparing and break ties by a stable key. Floating-point scores that are equal in theory can differ in the last digit and reorder results between runs or machines.
Remember this
- 1
Why start here. To give the model the right pages you must first find them. Keyword search is the oldest, cheapest and most explainable way: no model, no GPU, exact and fast, and you can say exactly why a document matched. It is also still a strong baseline that newer methods must beat, and many production systems combine it with vector search (the coming RAG course covers hybrid search).
- 2
Step one: tokenise. Cut text into tokens (here: lower-case words made of letters and digits). "Bikes can be returned!" becomes
bikes,can,be,returned. Search happens on tokens, so what you do here decides what can match. Our tokeniser does not stem (reduce "returned" to "return") or fix typos, which is exactly why the example showsbikeandbikesfinding different documents. - 3
Step two: build the index. For each document, for each distinct word, add the document's number to that word's list (its postings list). Looking up a word is then a single dictionary read. Searching for several words means combining their lists: AND keeps documents in every list (intersection), OR keeps documents in any list (union).
- 4
Step three: rank with TF-IDF. A document that merely contains a word is not enough: with many matches you need an order. Term frequency (tf) is how many times the word occurs in this document: a document that says "shipping" twice is more about shipping. Inverse document frequency (idf) is
log(N / df), where N is the number of documents and df (document frequency) is how many contain the word: a word in every document tells you nothing (idf 0), a word in one document is a strong clue. Score = the sum of tf × idf over the query words. In the example: N = 8,shippingis in one document so idf = ln(8) = 2.0794, and the shipping document says it twice, so that word alone adds 2 × 2.0794 = 4.1589. - 5
Check one number by hand.
daysis in 3 of 8 documents: idf = ln(8/3) = 0.9808.foris in 2 of 8: idf = ln(4) = 1.3863. The returns document containsdaysonce andforonce, so its score is 0.9808 + 1.3863 = 2.3671. The shipping document, which saysdaystwice andshippingtwice, scores 2 × 0.9808 + 2 × 2.0794 = 6.1205 and comes first. Notice that the small wordforis worth more thandayshere, because it is rarer in this tiny set. That is what a tiny corpus and no stop-word list (a list of very common words to ignore) give you. - 6
Known limits. Exact words only:
bikedoes not findbikes, and "get my money back" finds nothing although the returns document is exactly the answer (Topic 8.3 fixes this with meaning). Long documents get inflated scores, which is why the standard improvement, BM25, adds length normalisation and saturates tf; it is what most real keyword search engines use. A score is also not a probability: only the order matters, and you should break ties explicitly (the example sorts equal scores by document number so results never reorder between runs).
Explain it without notes
What is an inverted index and why is it faster than scanning every document?
Explain tf and idf, and why their product is a useful score.
Name two limits of plain keyword search and one fix for each.
Why do you need an explicit tie-breaker when sorting by score?
Practice
Write idf(n_docs, df) returning ln(n_docs / df), and print it to 4 decimals for df = 1, 2, 4 and 8 with 8 documents.
Write tf_idf(word, words, n_docs, df) for one word in one document (tf times idf). Use 8 documents; the word appears twice in the document and in only 1 document overall. Print to 4 decimals.
Trade-offs
- ↔
Keyword search is exact and explainable but blind to paraphrases; vector search finds meaning but is harder to explain and can match loosely.
- ↔
Stemming and stop words raise recall but can merge words that should stay apart.
- ↔
A bigger index answers faster but must be rebuilt or updated when documents change.
Done when you can
Done when you can build an inverted index from documents and look up a word.
Done when you can compute tf, df and idf for a word by hand.
Done when you can rank documents with tf-idf and break ties deterministically.
Done when you can explain two limits of keyword search and where BM25 fits.