How does a search engine work?

What you'll learn

Understand why search engines don't read every page one by one
Build an index of words and pages
Use sets to find pages that contain several words

Billions of pages in half a second

A search engine knows billions of web pages. Still, you get the results in a fraction of a second. So it does not read the pages when you search. It does that beforehand – and builds an index from them.

Without an index: read everything

This is how it would work without an index. With three pages that’s no problem:

pages = {
    "dogs": "dogs are loyal animals",
    "cats": "cats are animals that like to sleep",
    "fish": "fish live in water",
}

wanted = "animals"
read = 0
for name, text in pages.items():
    read = read + len(text.split())
    if wanted in text.split():
        print("Found on:", name)
print("Words read for this:", read)

With billions of pages, though, the computer would have to read trillions of words for every search. Far too slow!

The index: like the index of a book

At the back of a non-fiction book there’s an index: “robot … pages 12, 48, 97”. You don’t have to read the whole book. A search engine does the same. For every word it remembers which pages it appears on. A dictionary with sets fits perfectly:

pages = {
    "dogs": "dogs are loyal animals",
    "cats": "cats are animals that like to sleep",
}

index = {}
for name, text in pages.items():
    for word in text.split():
        if word not in index:
            index[word] = set()
        index[word].add(name)

for word in sorted(index):
    print(f"{word:8} → {sorted(index[word])}")

Now a search for “animals” is just one look into the dictionary: index["animals"].

Several words: the intersection

If you search for “loyal animals”, you want pages that have both words. That’s the intersection of the two sets. In Python you write & for it:

animals = {"dogs", "cats", "horses"}
loyal = {"dogs", "horses", "friends"}

print("Both words:", animals & loyal)
print("At least one:", animals | loyal)

Good to know: Real search engines also remember how often and where a word appears. And they rate how many other pages link to a page. That’s how the best hits get to the top. But the basic principle is exactly your index.

Your task

Your turn

Build a mini search engine. build_index(pages) gets a dictionary “page name → text” and returns the index: a dictionary “word → set of page names”. Words are written in lower case, and the punctuation marks .,!? are removed first. search(index, query) returns an alphabetically sorted list of the pages that contain all words of the query (upper/lower case doesn't matter). If the index doesn't know a word, the result is empty.

pages = {
    "dogs": "Dogs are loyal animals. Dogs like to play.",
    "cats": "Cats are animals that like to sleep.",
    "fish": "Fish live in water!",
}


def build_index(pages):
    index = {}
    return index


def search(index, query):
    return []


index = build_index(pages)
print(search(index, "animals like"))

Something to think about
For every word: if word not in index: index[word] = set() – then index[word].add(name).
Which command helps?
You get the intersection of two sets with &: hits = hits & index[word].
If a word isn't in the index, return an empty list right away.

Gap code – fill in the ___

                        pages = {
    "dogs": "Dogs are loyal animals. Dogs like to play.",
    "cats": "Cats are animals that like to sleep.",
    "fish": "Fish live in water!",
}


def words(text):
    for character in ___:
        text = ___
    return ___


def build_index(pages):
    index = {}
    for name, text in ___:
        for word in ___:
            if ___:
                index[word] = ___
            ___
    return index


def search(index, query):
    hits = ___
    for word in ___:
        if ___:
            return []
        if ___:
            hits = ___
        else:
            hits = ___
    return ___


index = build_index(pages)
print(search(index, "animals like"))

Solve it without hints to earn a ⭐ on your progress page.

Show solution

Try it yourself first – mistakes teach you the most. Here is one possible solution:

pages = {
    "dogs": "Dogs are loyal animals. Dogs like to play.",
    "cats": "Cats are animals that like to sleep.",
    "fish": "Fish live in water!",
}


def words(text):
    for character in ".,!?":
        text = text.replace(character, "")
    return text.lower().split()


def build_index(pages):
    index = {}
    for name, text in pages.items():
        for word in words(text):
            if word not in index:
                index[word] = set()
            index[word].add(name)
    return index


def search(index, query):
    hits = None
    for word in words(query):
        if word not in index:
            return []
        if hits is None:
            hits = set(index[word])
        else:
            hits = hits & index[word]
    return sorted(hits or [])


index = build_index(pages)
print(search(index, "animals like"))