Introduction
When you search the web, your email or a shop, a program has to answer two questions very quickly: which documents might match, and in what order to show them. Behind both is similarity: a number that says how alike two pieces of text are. This lesson builds the classic answer from the previous lessons: an inverted index to find candidates, and cosine similarity of TF-IDF vectors to rank them. The same similarity ideas also detect duplicate questions, recommend related articles and group documents by topic.
How it works
Jaccard similarity treats each text as a set of words:
J(A, B) = |A ∩ B| ÷ |A ∪ B|
It is 1 for the same set and 0 when nothing is shared. It ignores how often words occur.
Cosine similarity treats each text as a vector (counts or TF-IDF weights over a vocabulary):
cos(a, b) = (a · b) ÷ (‖a‖ × ‖b‖)
where a · b is the sum of products of matching entries and ‖a‖ is the square root of the sum of squares. It measures the angle between the vectors, so a document repeated twice has the same direction, and cosine 1, as the original. With non-negative counts it ranges from 0 to 1.
An inverted index maps each word to the sorted list of documents that contain it, its postings. To answer a query, look up each query word: documents containing any query word are candidates, and documents in every list (the intersection) match all words. A real index over millions of documents answers this in milliseconds, because it only touches the postings of the query words.
To rank, compute the similarity between the query vector and each candidate's vector and sort. With TF-IDF weights, a match on a rare word (high idf) counts much more than a match on a common one, and a word in every document contributes nothing at all.
Example
import math
docs = [
"cheap flights to paris",
"paris hotels and cheap rooms",
"learn python programming",
"python for data science",
]
index = {}
for i, doc in enumerate(docs):
for word in doc.split():
postings = index.setdefault(word, [])
if i not in postings:
postings.append(i)
print("cheap ->", index["cheap"], " python ->", index["python"])
def cosine(a, b):
vocab = sorted(set(a) | set(b))
va = [a.count(w) for w in vocab]
vb = [b.count(w) for w in vocab]
dot = sum(x * y for x, y in zip(va, vb))
return round(dot / (math.sqrt(sum(x * x for x in va)) * math.sqrt(sum(y * y for y in vb))), 12)
def jaccard(a, b):
return len(set(a) & set(b)) / len(set(a) | set(b))
query = "cheap paris hotels".split()
hits = []
for word in query:
for i in index.get(word, []):
if i not in hits:
hits.append(i)
print("documents sharing a word:", hits)
for i in sorted(hits, key=lambda i: -cosine(query, docs[i].split())):
d = docs[i].split()
print(f" cosine {cosine(query, d):.3f} jaccard {jaccard(query, d):.2f} {docs[i]}")Line by line
- The index maps each word to the documents that contain it;
setdefaultcreates an empty list the first time a word is seen. - "cheap" is in documents 0 and 1, "python" in 2 and 3. Only documents sharing a query word need to be scored.
cosinebuilds count vectors over the words of both texts and divides the dot product by the product of the lengths. The result is rounded to 12 places so it is the same on every computer.- Document 1 shares all three query words: cosine 3 / (√3 × √5) ≈ 0.775. Document 0 shares two of them: 2 / (√3 × 2) ≈ 0.577.
- Jaccard agrees on the order here: 3 shared words out of 5 in the union, against 2 out of 5.
Expected result
cheap -> [0, 1] python -> [2, 3]
documents sharing a word: [0, 1]
cosine 0.775 jaccard 0.60 paris hotels and cheap rooms
cosine 0.577 jaccard 0.40 cheap flights to paris
In the real world
Search engines such as Elasticsearch and Lucene store inverted indexes with compressed postings and rank with BM25, a refinement of TF-IDF that limits the effect of repeated words and adjusts for document length. Near-duplicate detection uses Jaccard similarity on word n-grams, often approximated with MinHash for speed. Modern semantic search replaces the count vectors with embeddings from neural networks, but still ranks by cosine similarity and still often combines it with a keyword index (hybrid search).
Common mistakes
- Dividing by zero when a query has no known words: a zero vector has no direction, so define its similarity as 0.
- Comparing raw dot products, which favour long documents; cosine divides by the lengths.
- Scanning every document for each query instead of using the index.
- Forgetting to apply the same tokenization and normalization to the query and the documents.
Best practices
- Normalize queries and documents in exactly the same way.
- Use the inverted index to pick candidates, then score only those.
- Break ties in rankings explicitly, for example by document number.
- Evaluate a search system with real queries and judged results, not by looking at one example.
Summary
Jaccard similarity compares sets of words; cosine similarity compares count or TF-IDF vectors by angle and ignores length. An inverted index maps words to the documents that contain them, so a query touches only a few postings lists. Ranking candidates by TF-IDF cosine similarity is the classic search engine, refined in practice by BM25.
Quick check
Key takeaways
- Jaccard compares which words are shared; cosine also uses how often they occur and ignores document length.
- An inverted index finds the documents that contain the query words without reading every document.
- Ranking with TF-IDF cosine favours documents that share the rare, informative words of the query.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.