Build a search engine
Build a search engine: crawler, index and ranker
The fastest way to understand search is to build a small one. This guide works through a crawler that respects robots.txt, an inverted index you can inspect, a scoring function you can reason about, and a query parser — each small enough to read in one sitting.
Every concept on this site becomes concrete once you have written it. A search engine that indexes a few thousand pages is a weekend project, and it teaches things that no amount of reading does — particularly about how much of search is bookkeeping rather than cleverness.
The four components
A crawler. A queue of URLs, an HTTP client, a robots.txt parser, a set of
already-seen URLs, and a politeness delay per host. The interesting parts are
not the fetching; they are deduplication, deciding what counts as the same URL,
and not hammering a server.
A parser. HTML in, plain text and a list of links out. You will immediately discover how much of a page is navigation, and why boilerplate detection exists.
An index. A dictionary mapping each term to a posting list of document IDs and positions. Written naively in memory it will work up to a surprising size, and the point at which it stops working teaches you why real indexes are segmented and compressed.
A ranker. Start with TF-IDF: score a document higher when the query terms appear often in it and rarely across the collection. Then try BM25, which adds document-length normalisation and term-frequency saturation, and observe how much better the results get for one afternoon’s work.
What you learn that reading does not teach
- How much of the web is duplicates of the web.
- That the frontier — deciding what to crawl next — is a harder problem than fetching.
- Why an inverted index is the only sensible structure, once you have tried to answer a query by scanning documents.
- Why relevance scoring is easy to get to “reasonable” and extremely hard to get to “good”.
Scope this honestly
A small engine will do well on a focused corpus — one site, one documentation set, one archive — and will do badly on the open web, because the open web is adversarial and enormous. That is not a failure of your code. It is the actual reason there are so few independent indexes.
The articles in this guide build each component in turn, with runnable code and a corpus small enough to inspect by hand.
Articles in this guide
The articles for this guide are being written. The guide above covers the whole topic in outline, and the article index lists everything published so far.