The Inverted Index

How search really works.

⏱ 2 min read▶ Video at 1:56:32🎓 Free

Watch this lesson in the NLP courseWatch on YouTube ↗Full NLP course

Open any textbook, and turn to the back. There's a list of words, and for each one, the pages that it's on. You don't read the whole book. You go straight to the page. That's all that a search engine really is.

The index at the back of a book
Go straight to the page
That's a search engine

Building an index

For every word, we store the set of tickets that contain it. To search for two words, we intersect their sets. Run it. Refund appears in four tickets. And refund and my together find three. The point is that we didn't scan any text at all. We just looked up two sets. If you had a billion documents, this would still take milliseconds. Google, Elasticsearch, and all of the others are built on this one idea.

index.pypython

from collections import defaultdict
from tickets import TICKETS

index = defaultdict(set)
for doc_id, (text, _) in enumerate(TICKETS):
    for word in text.split():
        index[word].add(doc_id)

def search(query):
    sets = [index[w] for w in query.split()]
    return set.intersection(*sets) if sets else set()

print("refund:", len(index["refund"]), "tickets")
for doc in search("refund my"):
    print("-", TICKETS[doc][0])

Output

refund: 4 tickets
- how long does a refund take to reach my card
- cancel my order and give me a refund
- refund has not appeared on my statement

Also uses tickets.py

TICKETS = [
    ("my order arrived late and the box was crushed", "delivery"),
    ("the parcel never came, where is my delivery", "delivery"),
    ("courier left the package in the rain", "delivery"),
    ("tracking has not moved for a week", "delivery"),
    ("shipping took three weeks, far too slow", "delivery"),
    ("delivery driver was rude and threw the parcel", "delivery"),
    ("package is lost, nobody knows where it went", "delivery"),
    ("the courier says delivered but nothing arrived", "delivery"),
    ("i want my money back for this book", "refund"),
    ("please refund the second copy you charged me for", "refund"),
    ("you took payment twice, return my money", "refund"),
    ("how long does a refund take to reach my card", "refund"),
    ("cancel my order and give me a refund", "refund"),
    ("i returned the book but got no money back", "refund"),
    ("charged the wrong price, want the difference back", "refund"),
    ("refund has not appeared on my statement", "refund"),
    ("the book has missing pages in chapter four", "quality"),
    ("cover is torn and the spine is broken", "quality"),
    ("pages are printed upside down in the middle", "quality"),
    ("ink is smudged on every page", "quality"),
    ("the binding fell apart after one read", "quality"),
    ("this copy has a coffee stain on the cover", "quality"),
    ("wrong edition, and the print quality is awful", "quality"),
    ("several pages are stuck together badly", "quality"),
]
QUERIES = [
    ("where is my parcel, it has not arrived", "delivery"),
    ("i need my money back please", "refund"),
    ("the pages are torn and the cover is bent", "quality"),
    ("courier lost my package", "delivery"),
    ("refund the payment to my card", "refund"),
    ("print is smudged and hard to read", "quality"),
]

Summary

Look up words, and intersect the sets. But which result should come first? Next, ranking.

Key takeaways

Word maps to document list
Intersect the sets
Fast at any size

Next up: BM25 — the ranking that refuses to die

❮ Near Duplicates BM25 ❯