A search engine for our textbooks

The last chapter ended with a question: how does the answer to a query arrive in a fraction of a second when the web holds billions of pages? Here is the scale of the problem. Google says its index covers hundreds of billions of pages and is “well over 100,000,000 gigabytes in size.” No machine could read that much in the blink of an eye. So the answer is prepared in advance, before the question is asked. The surest way to see how that is possible is to build a search engine ourselves.

We will search what we have at hand: the textbooks of this site. That means the course you are reading and “Mathematics, the Queen of the Sciences,” the site’s math course. Together they hold more than 120 chapters, over 800,000 words and more than 1,300 links between chapters: a small internet with pages and hyperlinks of its own. The engine grows in versions, and each version repairs what tripped up the one before. At the end you will have a working search, and question seven will have its answer.

Our little internet

A script has gathered the chapters into the course sandbox: it read the chapter files, threw out the code and the formulas, cut every chapter into its sections and wrote down which chapter links to which. This is a snapshot. The engine knows the textbooks as they were on the day of the build, and chapters written later don’t exist for it until the script runs again. The snapshot includes this chapter too, so the engine will find itself. Big search engines live with the same limitation: their index always lags a little behind the web.

Every page is a dictionary: an address id such as cs:hashing or math:eigen, a title, the page’s URL on the site and sections of clean text. The link graph is a dictionary “page → the pages it links to,” like the metro graph of Chapter 19.

The crawler

Before it can search, a search engine has to learn which pages exist at all. Nobody has a list of every page on the web. Instead there is the crawler, or spider, a program that downloads a page, pulls out its links, puts them in a queue, downloads the next page, and so on without end. This is the breadth-first search of Chapter 19, except that the graph isn’t known in advance and opens up as the crawler goes. We set our crawler loose on the textbooks from two starting pages: the beginning of this course and the beginning of the math course.

The crawler that started from this course found everything. The one that started from the math course found not a single chapter of this course, because the math course never links to it. A page that no link leads to doesn’t exist for a crawler. That is why the owner of a new site submits it to search engines by hand or gives them a sitemap, a file listing all its addresses. And to keep crawlers from bringing down other people’s servers with a thousand requests a second, Martijn Koster proposed robots.txt in 1994: a file in the root of a site that says where crawlers may go and where they may not. The writer Charles Stross says it was prompted by a badly behaved crawler Stross himself had written, which accidentally knocked over Koster’s server.

Version 0.1: read everything

The pages are downloaded. The most direct search engine reads through all of them in turn and checks whether the text contains the query string.

On our four megabytes the scan is quick, a couple of milliseconds, because Python runs the in check in C. But the time grows with the amount of text, and over the whole of Google’s index a single query would take about a year and a half. Worse, the scan doesn’t understand words. Asked for “war”, it found the title of Tolstoy’s novel, but also software, hardware, toward and forward, which have “war” inside them. And it says nothing about which of the dozens of pages it found is the one you need. The next versions fix these problems one at a time, starting with speed.

Version 0.2: the index at the back of the book

To find a word in a thick textbook, you turn to the index at the back: “hash table, 211, 340, 517”. The index was compiled in advance, once, and now any lookup is a single line in it. Google describes its own index in the same terms: it is “like the index in the back of a book,” with an entry for every word seen on every page it indexes.

An index like this is called an inverted index: normally a document is a list of words; here it is the other way round, and a word is a list of documents. The list of page numbers for one word is called a posting list. The index is built in one pass over all the texts and kept in a dictionary, the hash table of Chapter 16.

A query of several words is the intersection of their lists: we want the pages that contain every word. The lists are sorted, so they can be intersected with two fingers, as in the merge of Chapter 21: the finger on the smaller number steps forward, and a match goes into the answer. This takes as many steps as there are numbers in the two lists. It pays to start with the shortest list, since from then on the result can only shrink. The answers came in microseconds, tens to hundreds of times faster than the scan, and that time depends on the length of the lists; the total number of pages and words hardly affects it.

The index has dealt with speed and, by accident, with the second problem as well: “war” is now looked up as a word of its own. But the last two queries in the cell reveal a new one. “Shortest path” turned up in 26 chapters, “shortest paths” in only 11, this very chapter among them: it is in the index too. To the index, “path” and “paths” are different words.

Version 0.3: words and their forms

Before a text goes into the index, it is cut into tokens, words brought to a single form: lowercase letters, punctuation thrown away. This is the text-cleaning workshop of Chapter 7; in the module cs.search the function tokens does the job. But a word still comes in several forms. English is kind here: a noun has two, tree and trees, and a regular verb four, sort, sorts, sorted, sorting. Few forms, and still enough to lose pages: a single “s” cost the last query fifteen chapters.

The first fix is to cut off the endings. Reducing a word to its stem this way is called stemming, and a program that does it is a stemmer. The simplest stemmer is a list of endings: cut off the longest one that fits, if at least three letters remain. English needs one more rule: a word that ends in “ss”, “us” or “is” keeps its final “s,” because in class, status and analysis it is no plural.

A dozen lines of code, and sorting, sorted and sorts have come together in “sort”, class and classes in “class”. Tree and trees became “tre”: a stem doesn’t have to be a word, only the same for every form. But mistakes of two kinds show up at once. Running became “runn” and will never meet run, because a doubled consonant is not an ending. Ran and run won’t meet either: an irregular form changes the stem itself, as in mouse and mice or go and went, and no list of endings will help. These are forms that should stick together and don’t. The opposite happens too. University and universe became one “univers”, news turned into the plural of new, and the trie of Chapter 27 fell together with tries and tried, forms of the verb try. Whether compute, computer and computation ought to be one word is a matter of taste; for a search engine, perhaps they should. Without a dictionary and without the meaning of the sentence, none of this can be sorted out.

Other languages make the job harder. A Russian noun has up to a dozen forms, a verb dozens, and vowels drop out of the stem or change inside it. When the Moscow company CompTek showed its search engine Yandex in September 1997 (the name, coined by Ilya Segalovich, stands for “yet another indexer”), its trump card was Russian morphology: given a word in one form, it found all the others. Behind this stood a large dictionary of word forms, and for words missing from the dictionary Segalovich devised a way to guess: an unfamiliar word is inflected like the familiar words it resembles.

Then there are words that don’t help the search at all: “the”, “and”, “to”, “of”, the top lines of Zipf’s law from Chapter 8. They occur in almost every chapter. Their posting lists are the longest, and they are of no use. Such words are called stop words. Search engines used to throw them out; today they more often keep them but barely count them when ranking. How to “barely count” a word is the first thing the next version needs.

Version 0.4: who comes first

The index finds pages quickly, but it hands them out in order of page number. The query “hash table” brought 23 chapters, and the chapter on hash tables is only sixth on the list. We need a rule by which, for this query, one page outranks another.

The first idea is to count how many times the word occurs on the page: the hash-table chapter repeats “hash” more than a hundred times, and the chapter on dictionaries once. This is the term frequency, tf. So that long pages don’t win by length alone, it is divided by the number of words on the page. As early as 1958 Hans Peter Luhn, the author of the hashing memo in Chapter 16, proposed picking out the significant words of a document by their frequency and building abstracts automatically that way. But frequency alone is not enough: “and” is more frequent than “hash” on any page. The second half is missing.

Karen Spärck Jones of Cambridge found it in 1972: a word is worth more for search the fewer documents it occurs in. A word that is in all $N$ documents singles out none of them; a word that is in only one points straight at it. The measure is the inverse document frequency $\text{idf} = \log \frac{N}{\text{df}}$, where df is the number of documents that contain the word. The product of the two frequencies is called TF-IDF, and a page’s weight for a query is the sum of the TF-IDF of the query’s words. For an experiment, we slip a fake page into the collection: the word “hash” repeated two hundred times and nothing else.

In the idf table, “and” and even “number” appear almost everywhere, and their weight is about a hundredth; “hash” is in fewer than one chapter in five, while “collision” and “Burrows” are in a handful, and they weigh the most. Ranking has switched off the stop words by itself, without any list. But the first line of results is a disgrace: the fake is in first place. Its frequency of “hash” is a hundred percent, and TF-IDF sees nothing suspicious. This is what spammers did on the web: they stuffed pages with keywords, often in white on white, so that a person wouldn’t see them and a search engine would.

Version 0.5: saturation

The second line of results is the fix. The formula BM25 was worked out by Stephen Robertson, Karen Spärck Jones and their colleagues for the Okapi search system at City University London; it took its present shape in the 1990s. It makes two corrections to TF-IDF. The first is saturation: a word’s contribution grows with its frequency, but more and more slowly, and runs into a ceiling of $k_1 + 1$. The tenth mention adds less than the first, and the two-hundredth adds almost nothing. The second is length: the frequency is compared with the average page length, and the parameter $b$ decides how strictly.

$$\text{BM25} = \sum_{\text{query words}} \text{idf} \cdot \frac{\text{tf} \cdot (k_1 + 1)}{\text{tf} + k_1 \left(1 - b + b \cdot \frac{\text{length}}{\text{average length}}\right)}, \qquad k_1 \approx 1.2, \ b \approx 0.75.$$

The fake is out: its “hash” has hit the ceiling, and it has no “table” or “collision” at all. Second place, by the way, went to this very chapter, which by now has said a good deal about hashes and collisions. Saturation also protects against honest wordiness: a page where the word occurs a hundred times is not a hundred times more useful than one where it occurs five. Thirty years on, BM25 is still the default in search libraries such as Lucene and Elasticsearch, and the full-text search of SQLite, the database of Chapter 45, has a function bm25().

Version 0.6: voting with links

BM25 judges a page by its own text. But the text is written by the page’s author, who can write anything at all. Does a page have some property that its author can’t give it?

Brin and Page’s idea, PageRank, fits into one sentence: a page is important if important pages link to it. The definition is circular, but it has a concrete meaning. Picture a reader who wanders through the textbooks forever: on every page they click a random link, and now and then they get bored and open a random page out of all of them. The more often the reader lands on a page, the more important it is. In Brin and Page’s formula the probability of following a link rather than getting bored is called $d$, the damping factor. “We usually set d to 0.85,” they wrote.

If the reader walks long enough, the share of time spent on each page stops changing, and those shares are the PageRank. Computing them by walking is slow and imprecise. There is a shorter way: hand out importance. At first every page has the same importance. At each step a page gives the share $d$ of its importance in equal parts to the pages it links to, and the remaining $1 - d$ is handed out to everyone, like the jumps of the bored reader. Repeat until the numbers stop changing. This is the power method: each step multiplies the vector of importances by the matrix of links, and the answer is the matrix’s eigenvector. Why the process always converges, and always to the same answer, is proved in the chapter on eigenvectors of the math course; all we have to do is compute.

The top six are all mathematics: sequences, primes, irrational numbers, combinatorics. Dozens of other chapters link to them, chapters of this course among them. The chapters of the course, meanwhile, collected noticeably less importance than their share of the pages: in the snapshot this chapter was written from, about 36% of the importance for 52% of the pages. The reason can be seen in the graph. The CS course links to the math course, and the math course never links back. Importance flows along the links in one direction and doesn’t return. Inside the course the top places go to “Dictionaries and the telegraph,” “Hash tables: attack and defense” and “A problem inside a problem”: later chapters keep linking back to the basic ones.

How many steps it will take can be estimated in advance. At every step the distance to the exact answer shrinks at least by a factor of $1/d$: that is what the chapter on eigenvectors proves. At $d = 0.85$ the estimate promises accuracy to a billionth in about 130 steps. Our graph needed fewer, because the estimate is for the worst case. The closer $d$ is to one, the slower the convergence, so $d$ decides both what the ranking means and what it costs to compute.

The link farm

PageRank was invented so that authors couldn’t assign importance to their own pages. But nothing stops an author from making links as well. Take Chapter 4, “Again and again,” which sits in the lower half of the ranking. We create forty empty pages, every one of them linking to it: a link farm.

Forty empty pages lifted the chapter from the lower half of the table to first place. The mechanism is visible in the formula: every page receives its share $\frac{1 - d}{N}$ of the bored reader’s jumps even if nobody links to it, and dutifully passes it on along its only link. A fake page costs next to nothing, and yet it has a vote. For decades this is how sites were promoted: farms, networks of blogs, links bought in bulk, comments with links under other people’s articles.

Brin and Page proposed a defense in the same 1998 paper. The bored reader’s jumps can be aimed at a single page or a small group, and that, they wrote, “can make it nearly impossible to deliberately mislead the system in order to get a higher ranking.” The last two lines of the cell show why. If the reader jumps only to the opening chapters of the two courses, the fake pages get nothing: no link from the trusted part of the graph leads to them, and without incoming importance they have nothing to give away. The farm has lost its vote: with trusted jumps the chapter stands 92nd whether the farm is there or not. Other defenses grew out of this idea, from “trust” that spreads outward from verified sites to the attribute rel="nofollow": since 2005 it has marked links in comments and ads so that search engines don’t count them. Today PageRank is only one of hundreds of signals search engines use to rank pages, and the race between spammers and search engines goes on.

Version 0.7: putting it together

What remains is to combine text and links. There are many ways to do it; one of the simplest is to multiply the BM25 score by PageRank raised to some power: $\text{score} = \text{BM25} \cdot (N \cdot \text{PR})^{w}$. The factor $N \cdot \text{PR}$ is one for an average page, more for a popular one and less for an obscure one, and the exponent $w$ decides how much the links weigh against the text: at $w = 0$ they don’t count at all. The module cs.search gathers everything we have written into the class Engine: tokens, stems, the index with counts, BM25 and PageRank. On top of that, for every page it finds, it picks the section with the most query words and cuts out a piece around the first of them, so that you can see why the page was found.

An index over more than 120 chapters is built in a fraction of a second, a search takes milliseconds, and the engine is already usable; with stems, “shortest paths” now finds the same 26 chapters as “shortest path”. The search box below sends your query to the course server, where the same Engine runs, and shows the results with links straight to the right section.

Play with the weight of links. With a large $w$, popular chapters of the math course climb to the top even when the query is about something else: PageRank knows nothing about the query. Even the default weight makes itself felt: for “shortest paths”, Chapter 24, which is all about them, missed the top three in the cell above, behind chapters that more pages link to; move the slider to zero, and it comes first. But at $w = 0$ only the text decides, and a short page where the right words flash by a few times can overtake a chapter devoted entirely to the subject. Commercial search engines tune such weights by watching how people behave: which result they click, whether they come back to the results page. Today this is done with machine learning, which we reach in Chapter 63.

Version 0.8: suggestions

The finishing touch is suggestions while you type. In Chapter 27 we built a trie over the words of War and Peace and promised it would come back in a search engine. Here it is: a trie over the ten thousand most frequent words of the textbooks, where every node at which a word ends remembers how many times the word occurred.

The suggestions are right but monotonous: for “sort”, four forms of a single word. The cure is the same stemmer: of all the words with one stem, show only the most frequent. That is what the search box above does. And on “ram”, next to the RAM of this course, Ramsey and Ramanujan turned up from the math course: the engine searches all the textbooks at once. Big search engines build suggestions from the queries people have already typed, and they don’t walk the whole subtree: every node of the trie keeps a few best continuations ready, to answer while your finger is still over the key.

How it works on billions of pages

Our engine answers in milliseconds, but it has just over 120 pages. A big search engine has hundreds of billions, and almost all of its work is done before you press Enter.

In advance: crawling, the index, PageRank. The crawler walks the web without stopping, the index is rebuilt piece by piece, and PageRank is recomputed over the whole link graph. The index itself is built by sorting: from every page the pairs “word, page number” are written out and sorted by word. In the 1998 paper, sorting took “about 24 hours” on four machines. Pairs that don’t fit in memory are sorted in chunks, and the finished chunks are merged: we saw how two lists merge in Chapter 21, and how many merge at once with a heap in the task “Merging sorted lists” of Chapter 18.

At query time: a few lines of the index. The words of the query are looked up in a dictionary, the hash table of Chapter 16 or the tree of Chapter 46, and their posting lists are intersected with two fingers. The time depends on the length of the lists, not on the size of the web. The lists are stored compressed: page numbers come in increasing order, so instead of the numbers themselves you store the differences between neighbors, small numbers that take a byte each or even less. This is the last chapter at work, and the disks are not the only winners: a compressed index fits in main memory, and memory, as we saw in Chapter 34, is thousands of times closer than a disk.

Thousands of machines at once. The index of the whole web fits on no single machine, so it is split by pages: each machine holds the index of its own share of the pages. A query goes out to all the parts at once, each part finds its best ten, and the answers are merged by the heap of Chapter 18, which picks the best of the best. Every part is also copied onto several machines: if one breaks, a neighbor answers, as in Chapter 44.

Ranking in two passes. A cheap formula like ours, BM25 with PageRank, quickly picks a few thousand candidates, and only those are reordered by an expensive model with hundreds of signals. Frequent queries aren’t computed afresh at all: the answer to “weather” sits in a cache.

A search engine does its searching in advance, before the question is asked. A crawler walks the web along its links and downloads the pages. Their texts are turned into an inverted index: for every word, a sorted list of the pages where it occurs. The index is built by sorting “word, page” pairs and stored compressed, and the words in it are found through a hash table. A query becomes a few lookups in the index and an intersection of short lists, so the time to answer depends on the length of those lists and not on the number of pages on the web. What is found gets ordered by text and by links. By text, with formulas like TF-IDF and BM25, where rare words weigh more and repetitions saturate. By links, with PageRank: the share of time a random reader spends on a page, computed in advance by the power method. The index is split across thousands of machines that search in parallel, a heap merges their best answers, and a trie supplies the suggestions. A fraction of a second is enough because all that has to be read is a few lines of an index made in advance.

Tasks

Three tasks, three parts of a search engine: the index, ranking by text and ranking by links. Each one has a big test with a stopwatch.

Write build_index(docs): given a list of texts, return the inverted index, a dictionary “word → list of the numbers of the documents that contain it,” in increasing order and without repeats. Words are what the starter’s function words returns: runs of lowercase letters and digits. Also write search(index, query): the numbers of the documents that contain all the words of the query, in increasing order. If some word occurs in no document, or the query has no words, the answer is an empty list. The last test builds an index of 20,000 documents and asks 3,000 queries; three seconds for everything.

Go through the documents in order. If the document’s number is already the last one in the word’s list, the word has turned up in this document again, and there is no need to write the number down twice. That way the lists come out sorted by themselves.

For a search, take the lists of all the query words (repeats in the query don’t matter: set), sort them by length and intersect them starting with the shortest: the result can only shrink. A word that isn’t in the index is an empty list, not a KeyError: index.get(t, []).

You can intersect with two fingers, as in the chapter, or with sets. What you can’t do is check every document for every query: 3,000 queries over 20,000 documents make sixty million checks.

Building the index is one pass over all the words, $O(\text{words})$. A query costs as many steps as there are numbers in the lists of its words, and when you start from the short list, often far fewer: if the rarest word is in three documents, at most three remain after the first intersection. The early exit on an empty result is a trifle that costs nothing and saves a lot on live queries.

Write tf_idf_rank(docs, query): the document numbers ordered by decreasing TF-IDF score for the query. Words come from the same function words. For a query word $t$ and a document $D$: $\text{tf} = \frac{\text{occurrences of } t \text{ in } D}{\text{number of words in } D}$, $\text{idf} = \ln \frac{N}{\text{df}}$, where $N$ is the number of documents and df is how many of them contain $t$. A document’s score is the sum of $\text{tf} \cdot \text{idf}$ over the different words of the query. Only documents with a positive score go into the answer; on equal scores the smaller number comes first. A document with no words, an empty one, gets nothing.

First make one pass over all the documents: split each into words and count df, for every word the number of documents it occurs in. Within a document a word counts once: take a set of its words.

Then, for each document, a counter of its words and a sum over the query words it contains. A word that is in every document gives $\ln 1 = 0$, and a document that contains only such words stays out of the answer. Skip an empty document before you divide by its length.

The order “by decreasing score, ties by number” comes from sorting the pairs (-score, number).

Repeated words in the query add nothing; that is what the statement asks for, and set takes care of it. TF-IDF doesn’t require a document to contain every word of the query: a document with one rare word can beat a document that has all the words, if they are frequent ones. Search engines usually first select the documents that have all the words, as in the previous task, and only then rank them.

Write pagerank(links, d=0.85). The graph is a dictionary “page → list of the pages it links to”; every page in the lists is also among the keys, and no page links to itself. Return a dictionary “page → PageRank” whose values add up to 1, accurate to $10^{-6}$. With probability $d$ the reader follows a random link from the page, and with probability $1 - d$ opens a random page out of all of them. The catch is pages without links: our textbooks have none, but the web has plenty. From a page without links the reader always goes to a random page out of all of them. The last test is 5,000 pages and almost 30,000 links in three seconds.

Take pagerank from the chapter and trace what it does with a page without links: that page’s importance goes nowhere and vanishes, and the sum drops below one.

Collect the importance of all the pages without links into one pot, multiply it by $d$ and hand it out equally to all $N$ pages, the same way the bored reader’s jumps are handed out.

To stop, measure how much the vector changed in a step, the sum of the absolute differences, and stop when the change is less than $10^{-10}$. That is comfortably below the required accuracy: the error shrinks by a factor of $1/d$ at every step.

One step is a pass over all the links, $O(N + \text{links})$, and the number of steps needed is $O(\log(1/\varepsilon) / \log(1/d))$: at $d = 0.85$ and $\varepsilon = 10^{-10}$, no more than about a hundred and fifty. In matrix form a page without links is a column of zeros, and without the fix the matrix is no longer a transition matrix; the fix “go anywhere” turns that column into a column of equal entries $1/N$. The chapter on eigenvectors in the math course does the same.

What next

The search engine is finished, and it took a few hundred lines. Big search engines are more complicated, but they are assembled from the same parts, and we have built almost every one of them before: breadth-first search, the hash table, merging, the heap, the trie, compression, the eigenvector.

There is one thing our engine can’t do. The script that gathered the textbooks threw the code out of them, and for a search engine that is the right call: to it, the cells and programs of the course are noise, with for and print in every other one. Yet a program is a text too, and it has a meaning that neither the stemmer nor BM25 can see. To a bag of words, the line a, b = b, a % b is five one-letter words; to Python it is a step of Euclid’s algorithm. To understand that, you have to read a text by the rules of the language it is written in, not as a bag of words. There are thousands of programming languages. Why there are so many, and how they differ, is the subject of the next chapter. It starts a road that ends with you writing a program that understands another program.