Text similarity and search

Intermediate

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]}")
Open in compiler

Line by line

  1. The index maps each word to the documents that contain it; setdefault creates an empty list the first time a word is seen.
  2. "cheap" is in documents 0 and 1, "python" in 2 and 3. Only documents sharing a query word need to be scored.
  3. cosine builds 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.
  4. Document 1 shares all three query words: cosine 3 / (√3 × √5) ≈ 0.775. Document 0 shares two of them: 2 / (√3 × 2) ≈ 0.577.
  5. 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

1. What is the Jaccard similarity of the word sets a, b, c and b, c, d?
2. Why is cosine similarity preferred to a raw dot product for documents?
3. What does an inverted index store for each word?
4. Why does a match on a rare query word count more with TF-IDF ranking?

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.