How This Search Works

Type the query below into the search box at the top of this page and press Enter.

Porter stemer

The results page reads "Showing results for Porter stemmer", and the first result is The Porter Stemmer. In between, a small search engine did what the course articles on information retrieval describe. It noticed that the second word is not one any page uses and found the nearest word that is. It ran the corrected query against an inverted index of every page on the site, scored the matches with BM25F, and picked a sentence from each result to show under its title. How does each of those steps work here, and how well does the result hold up?

This page describes that engine as it stands and runs worked examples against its real index. The theory lives elsewhere on the site. The architecture of a search engine traces the same code on a four-sentence collection, designing a modular search engine discusses how its modules are divided, and BM25F derives the ranking function. This page follows the whole system in order: the index, the query language with its rough edges, ranking, spelling correction, snippets, the browser's copy of the index, the tests, and the API that the site owner's chatbot uses. A companion page, How the Content Analysis Tools Work, follows the same text processing into the tools that review the site's pages.

Every number about the index comes from tools/experiments/search/how-this-search-works.py, which rebuilds the index with the site's own code and prints what this page quotes. The figures are a snapshot of November 2026, when the site had 471 pages, this one included. Counts and scores drift as pages are added or edited; rerunning the script gives the current values.

The pieces

The engine is a handful of files in the site's source, which is private. None of it depends on a search library or a database.

The figure shows how the pieces connect. The left column runs once, when the site starts, and the right column runs for every query. The bottom row is the shortcut that lets the browser rank without the server's code.

From page to index

The index is built in memory every time the site starts, from the article records that app/wiki.py has loaded. There is no index file on disk and nothing to rebuild by hand when a page changes: the next start sees the new text. The build took about six seconds on the machine that ran the script.

Five fields

Each page is cut into five fields, the zones of weighted zone scoring, each indexed separately so that a word can count for more in one field than another.

Turning Markdown into the body text (plain_text in app/search.py) is mostly removal. Fenced code blocks are dropped. Display math is dropped, and inline math becomes an ellipsis, so that a snippet shows a visible gap where a formula was. A wiki link becomes its visible text, or the title of the page it points to if it has no text of its own. A figure, video or demo line becomes its caption, so captions are searchable. Inline code keeps its text, so words inside code spans, such as search-index.json, are searchable.

A reader who searches for μ or lambda usually wants the pages whose formulas use $\mu$ or $\lambda$, but the formulas themselves are not indexed. So the indexer scans each formula for Greek letters, written either as Unicode symbols or as TeX commands such as \lambda and \varepsilon, and indexes their names in the math field. Its weight of 0.1 is deliberately low: the word delta in the prose of the article on index compression should outrank a $\delta$ in some proof, and a test checks that it does.

Tokens

A field's text then goes through the same function, tokens, whether it comes from a page or from a query. It folds the text, removing accents after Unicode decomposition and then lowercasing, so Schütze and schutze are the same word. It drops a possessive 's, so Schütze's is just Schütze. It replaces each Greek letter with its name as a separate word and keeps maximal runs of the letters a to z and the digits 0 to 9. Everything else separates tokens. The tokenization article compares this rule with two others on hard cases.

The sentence below, made up to exercise the rules, shows each step.

The crawlers were crawling Schütze's pages, and (μ,λ)-ES appeared in the summaries.

Stop words are the 33 words of a short, fixed list (a, an, and, are, as, at, be, but, by, for, if, in, into, is, it, no, not, of, on, or, such, that, the, their, then, there, these, they, this, to, was, will, with). They are not indexed, but they still take up a position, so the term crawler is at position 1 even though the first token was dropped. Counting positions this way keeps phrase queries honest, as that article explains, and it means field lengths include stop words. The stop words article discusses how long such a list should be.

Two rows show rules that are easy to miss. The possessive of Schütze's is gone before the text is split, so the word takes one position, not two. And es, from (μ,λ)-ES, is its own index term, because words of one or two letters are not stemmed, as the next section explains.

Stems

Each remaining token is reduced to its stem by app/porter.py, an implementation of the original algorithm in Porter (1980). It follows the paper rather than later revisions, the way NLTK's PorterStemmer does in its ORIGINAL_ALGORITHM mode, and tools/search/check_porter.py compares the two on every word of the wiki. The index applies it only to words of three or more letters. That is the one departure the author's own reference implementation makes from the paper, and it matters here. By the paper's rules s stems to the empty string, which would turn every stray s into a term found on nearly every page, and es stems to e, which would make a search for ES a search for the e of e.g. The Porter stemmer article walks through the rules, and stemming and lemmatization discusses what stemming gains and costs.

On this site's vocabulary, the stemmer makes choices worth knowing about when searching:

A search for stemmer therefore does not match a page that only says stemming, and a search for politeness also matches pages about politics. These are the classic overstemming and understemming errors, and they are the price of a rule-based stemmer that needs no dictionary. The index also remembers, for each term, which surface words produced it and how often (SearchIndex.surface), which the spelling corrector and prefix queries use.

Positional postings

The index itself is a dictionary from each term to the pages that contain it. Within each page it records the term's positions in each field: term, then page, then field, then a list of positions. That is a positional inverted index with one extra level for the fields. For the article on the Porter stemmer, the two terms of the running query look like this:

The title "The Porter Stemmer" puts porter at position 1, because the holds position 0. Alongside the postings, the index keeps each field's length in every page and the average length of each field, which BM25F's length normalization needs.

Across the whole site the index holds about 16,400 distinct terms drawn from about 23,700 distinct surface words. It has about 301,300 postings (pairs of a term and a page) and about 1.04 million recorded positions, from about 1.48 million tokens counting stop words. As term statistics would predict, the vocabulary has a long tail: 42% of the terms occur in exactly one page.

The query language

The parser, app/query.py, turns a query string into a tree. It never lowercases, stems or removes stop words. It leaves the words exactly as typed, and the index analyzes them with the functions it used on the pages when it evaluates the tree. The parser therefore cannot analyze a query differently from the pages, because it does not analyze at all. A query takes one of two modes, decided by the query itself.

Free text, the default, works like a web search engine. Each word is optional, any page that contains at least one of them is a candidate, and BM25F orders the candidates. Modifiers turn a word into a requirement:

Boolean mode starts when the query contains AND, OR or NOT in capitals, or a parenthesis that groups. Parsing Boolean queries traces the grammar, its precedence (NOT, then AND, then OR, with adjacent terms joined by an implicit AND) and the parser's habit of repairing rather than rejecting a malformed query. Here only the outcome matters. (stemming OR lemmatization) AND NOT porter becomes a tree of set operations, and a dangling operator or a missing parenthesis is fixed and reported in a note above the results. Inside a Boolean query the free-text modifiers still work: a leading minus means NOT, and quotes, fields and prefixes behave as above.

Matching and scoring are separate steps. Matching evaluates the tree as set operations over the postings: AND is intersection, OR is union, NOT is complement against all pages. A phrase is matched by first intersecting the pages that hold all its terms and then checking positions, field by field. Scoring then ranks the matching pages by BM25F on every term that is not under a NOT. In free text the required, optional and quoted words all count toward the score. So +stemmer porter ranks exactly like porter stemmer; it only matches fewer pages (21 instead of 28).

Two details of matching are easy to miss. An unquoted word with a hyphen or a dot, such as k-means or robots.txt, is one written word but two tokens. In free text its parts are ranked as separate optional words, so k-means matches 401 pages, 375 of them because they contain mean. Quoted, "k-means" is a phrase and matches 28. And a prefix such as crawl* is expanded through the surface vocabulary, most frequent words first. It becomes at most 64 index terms for matching and the 16 most frequent of those for scoring.

Edge cases

The cases below were run against the current index and describe current behavior.

A sign after a closing parenthesis. Parentheses only group when they stand apart from a word, so that written forms such as (1+1)-ES and f(x) stay single words (a test checks this). A minus or plus written directly after the ) of a group that holds AND, OR or NOT applies to the next word instead. So (selection OR mutation)-ES means selection or mutation, and not ES, exactly as (selection OR mutation) -ES does. Both give 176 results, out of the 191 pages that match selection OR mutation. A group with no operator in it, such as the (1+1) of (1+1)-ES, is still part of its word.

A space inside a written word. (μ,λ)-ES is one word and searches for mu, lambda and es as optional words. Written with a space after the comma, (μ, λ)-ES splits into (μ, and λ)-ES, and the first parenthesis now groups. The query becomes Boolean: mu AND the phrase lambda es, with a missing parenthesis supplied. It finds two pages, this one and parsing Boolean queries.

Short words keep their form. Since words of one or two letters are not stemmed, ES is the term es, found in 17 pages, and not the e of e.g., which occurs in 241. Excluding it removes the pages about evolution strategies and little else: evolution matches 69 pages, and evolution -ES matches 54.

Greek letters match by name. μ and mu give identical results (68 pages), as do σ, Σ and sigma (74), and a test checks that symbol and name agree. They find the prose names of the letters and the math field. Because the math field's weight is low, a page that uses a letter only in formulas ranks below pages that name it in prose. Take (μ,λ)-ES. The article on plus and comma selection has almost all of its $\mu$ and $\lambda$ in formulas, and its title spells the strategies out in words; it ranks second. This page, which repeats the query, ranks first. A whole Greek word is spelled out letter by letter, so λόγος searches for lambda, omicron, gamma and sigma. A word in a script the index does not hold, such as привет, keeps its own form and simply matches nothing, without a spelling suggestion.

Stop words in a phrase are checked by position. Stop words are not index terms, but the index keeps their positions in a separate table, which only phrase matching reads. The phrase "rate of change" therefore needs rate, then of, then chang, in consecutive positions. It finds 3 pages, and a sentence such as "the error rate barely changed" does not match. A phrase made entirely of stop words still matches nothing, because it has no index term to look up. In "one of the", one stems to on, and the phrase finds the 145 pages where that term is followed by of and the.

A possessive is the word itself. Fisher's searches for Fisher, because the possessive is dropped from queries just as it is from pages, so the two queries match the same 24 pages. The phrase "Fisher's exact test" also matches "the Fisher exact test", in 4 pages. A straight and a curly apostrophe work alike.

Stop words alone. the gives no results and the note "Only very common words were searched for, and they are not indexed." In Boolean mode a stop word is neutral: the AND pagerank is pagerank, and NOT the matches nothing rather than every page.

Ranking with BM25F

BM25F combines a term's occurrences across the fields into one pseudo term frequency before applying BM25's saturation, rather than scoring each field separately and adding. The BM25F article derives why; this section gives the formula as SearchIndex._bm25f computes it and then works one score through.

For a term $t$ and a page $d$, each field $f$ contributes its weighted, length-normalized count,

$$\tilde{tf}_{t,d} = \sum_{f} \frac{w_f \, tf_{t,d,f}}{1 - b_f + b_f \, L_{d,f} / \bar{L}_f},$$

where $tf_{t,d,f}$ is the number of times $t$ occurs in field $f$ of $d$, $L_{d,f}$ is that field's length in tokens, $\bar{L}_f$ is its average length over all pages, $w_f$ is the field weight from the table above, and $b_f = 0.5$ for every field. The term's contribution is

$$\mathrm{IDF}(t)\,\frac{\tilde{tf}_{t,d}}{k_1 + \tilde{tf}_{t,d}}, \qquad \mathrm{IDF}(t) = \ln\!\left(1 + \frac{N - \mathit{df}_t + 0.5}{\mathit{df}_t + 0.5}\right),$$

with $k_1 = 1.2$, $N$ the number of pages and $\mathit{df}_t$ the number of pages containing $t$. The IDF is the form Lucene uses, which never goes negative, and the formula omits the constant factor $k_1 + 1$ of the textbook BM25, so each term's contribution is at most its IDF. A page's BM25F score is the sum of its terms' contributions.

Two rules sit on top of BM25F. Both favor the page whose title names what was searched for. The first was added when the plain score let a page that mentions a word fifty times outrank the page titled with it.

1. Title bonus. If a page's title terms contain every query term, the page gets $2 \times |Q| / |T|$ added outside the saturation, where $|Q|$ is the number of distinct query terms and $|T|$ the number of distinct terms in the title. A title the query covers completely gets the full 2.
2. Exact titles first. Pages whose title terms are exactly the query terms are sorted ahead of all others, whatever their scores. Ties after that are broken alphabetically by title.

A score worked by hand

Take the query porter stemmer. It has two terms, porter and stemmer, and 28 pages contain at least one of them. With $N = 471$, porter occurs in 23 pages and stemmer in 21, so

$$\mathrm{IDF}(\textit{porter}) = \ln\!\left(1 + \frac{471 - 23 + 0.5}{23 + 0.5}\right) = 3.0000, \qquad \mathrm{IDF}(\textit{stemmer}) = 3.0889.$$

In The Porter Stemmer, the title has 3 tokens (the counts) against an average of 4.915, so its normalizer is $1 - 0.5 + 0.5 \times 3/4.915 = 0.8052$, and one occurrence there adds $12/0.8052 = 14.90$ to the pseudo frequency. Field by field, with normalizers to three decimals and contributions to two:

The pseudo frequency of porter is $14.90 + 1.28 + 25.22 \approx 41.40$, its saturation factor $41.40 / (1.2 + 41.40) = 0.9718$, and its contribution $3.0000 \times 0.9718 = 2.9155$. For stemmer the pseudo frequency is 27.82, the factor 0.9586, and the contribution 2.9612. The BM25F score is $2.9155 + 2.9612 \approx 5.877$. The title, after dropping the, is exactly {porter, stemmer}, so the bonus is $2 \times 2/2 = 2$, for a final score of 7.877.

The runner-up is the more interesting number. Stemming and Lemmatization mentions stemmer 55 times in its body and once in a heading, and porter 30 times, and its BM25F score is 5.909, slightly higher than the Porter article's 5.877. Both pages are near the ceiling, the sum of the two IDFs, 6.09, where saturation makes extra occurrences nearly worthless, and BM25F alone cannot tell the page about the Porter stemmer from a page that discusses it at length. The title bonus decides it, and the exact-title rule would decide it even without the bonus. The third page is this one, at 5.87: it uses both words dozens of times, and saturation lets that count for little more than a few uses would.

This is the general pattern on a site where many pages discuss each concept. The BM25F article tells the story of the query bm25, which began to rank another page above Okapi BM25 as the site grew. It also tells how the bonus was chosen: on the known-item queries described below, any bonus weight from 0.5 to 8 gave the same results.

The title, summary and heading weights and $k_1$ were chosen by a grid search on the first half of those known-item queries (tools/search/evaluate.py --tune) and checked on the second half. Robertson and Zaragoza (2009) give the background for both the field weights and the per-field normalization.

Spelling correction

The search corrects a query in two strengths, following the techniques of spelling correction. SearchIndex.suggest looks at each word of the query in turn. It skips words shorter than three letters, numbers, stop words, and written words that are more than one token (so μsec is searched as mu sec, not corrected). Only alphabetic words are candidates for a correction.

• If a word's index term occurs in no page, the correction is confident. The corrected query is run in place of the original, and the page says "Showing results for ..." with a link to search for the original instead (exact=1 turns correction off).
• If the term occurs in one or two pages and an alternative is far more common, the alternative is offered as "Did you mean ...?" above the original query's results. Far more common means at least ten times as frequent and in at least five pages. If the original query has no results at all, the suggestion is run instead, as if it were confident.
• If the term is common but the word itself never appears, the stemmer has already absorbed the typo. A misspelling of politeness that drops its first e still stems to polit, like the correct word, so its results are already right; the usual spelling is offered as a suggestion.

Candidates come from two places. First, the word may be two words run together, as when k and means are typed without the hyphen. If the two halves appear together as a phrase in the index, the split is the suggestion. Otherwise the corrector looks for the nearest word in the vocabulary. A bigram index over the alphabetic surface words (665 distinct bigrams over about 19,000 words) proposes the candidates. Each must share at least 30% of its letter bigrams with the typed word, by the Jaccard coefficient of the bigram sets with the word's start and end marked. Those within edit distance 1, or 2 for words of six letters or more, survive. The distance is the Damerau-Levenshtein distance in its restricted form (optimal string alignment), which counts a swap of adjacent letters as one edit (Damerau, 1964). Among the survivors the corrector prefers the smallest distance, then words that occur in the same pages as the query's other words, then the most frequent.

Seven queries, with the index term of the misspelled word, the number of pages that contain that term, and what the search does:

typed                   term      pages  outcome
Porter stemer           stemer        0  runs "Porter stemmer" (distance 1)
pagernak                pagernak      0  runs "pagerank" (one swap)
evolutionary algoritm   algoritm      0  runs "evolutionary algorithm"
retreival               retreiv       1  suggests "retrieval", shows 1 page
kmeans                  kmean         2  suggests "k means"
politness               polit        45  suggests "politeness"
bm52                    bm52          0  nothing: "bm25" is not alphabetic

The misspellings on this page are written in code blocks for a reason: the indexer skips code blocks, and written as ordinary text they would enter the index. A misspelling that occurs in some page is no longer unknown, so the corrector would only suggest a fix instead of making it. That is what happens with the fourth row. That misspelling of retrieval occurs in exactly one page, the article on spelling correction, which opens with it as its example; the search shows that page and offers the correct spelling.

Snippets and passages

Under each result on the /search page is a snippet, chosen by SearchIndex.snippet. Every sentence of the page's body is scored by the number of distinct query terms it contains, with a small preference for the first sentence. The best one is shown, extended by the next sentence if it is shorter than 120 characters and trimmed to about 240 characters around its first match. Every word whose stem is a query term is highlighted. For porter stemmer, the Porter article's snippet is its opening sentence, with two highlights:

Run on the thesis student's four Arctic sentences in the architecture article, the Porter stemmer turned warms and warming into warm, declining into declin, and climate into climat.

The JSON API returns passages instead, which are larger. When app/wiki.py renders a page, it splits the HTML at its second- and third-level headings into plain-text sections, each with its heading and anchor. The text before the first heading counts as the introduction. For a search, SearchIndex.passages picks the two sections that hold the most distinct query terms, returns them in page order, and trims each to 1,200 characters around its first match. For porter stemmer the Porter article has 15 sections, and the two chosen are the introduction and "Worked traces". Each passage carries a link to its anchor, so an answer built from it can cite the exact section.

Instant results in the browser

As soon as a reader focuses a search box, search-ui.js downloads the site's index once. From then on every keystroke is answered in the browser, with up to eight titles under the box and no request to the server. The browser contains no stemmer and no BM25F code. It does not need them, because of a property that the architecture article points out. A page's BM25F score is a sum over query terms, and each term's contribution depends only on the term and the page. So SearchIndex.export computes, at startup, the contribution of every pair of a term and a page that contains it, and the browser only adds numbers up. This is the precomputed-impact idea described in implementing BM25.

The exported index, served at /search-index.json, has these parts:

• postings: for each term, a flat list of page numbers and weights, [page, weight, page, weight, ...], with weights rounded to four decimals, about 301,300 weights in all. The list for stemmer covers 21 pages, and in it the Porter article's weight is 2.9612, the contribution worked out above.
• words: each surface word with the number of its index term and its frequency. This replaces the stemmer: a typed word is looked up in the table rather than stemmed, so stemmers maps straight to the term stemmer.
• titleTerms, titleBonus, docs: what the title bonus and the exact-title rule need, and each page's slug, title, type, summary and address.
• stop and greek: the stop list and the Greek letter names, so the browser tokenizes as the server does.

The file is 3.99 MB of JSON, sent gzip-compressed as 1.52 MB (38% of the original). Its address carries a version, the first twelve hex digits of a SHA-256 hash of its contents. The browser may therefore cache it for a year: when any page changes, the hash changes and the address with it.

Text being typed is treated like the server query made of the finished words plus the last word as a prefix. Typing porter ste is the server query porter ste*, and ste expands to the 16 most frequent index terms that start with it:

step steer stemmer stem steepest steadili steadi steepli steep steven stern steyver stereotyp steeper stepwis steel

No title holds all sixteen, so neither title rule applies and the order rests on BM25F alone. The Porter Stemmer comes first (8.439), ahead of Stemming and Lemmatization (8.377), mostly because it uses step, for the five steps of the algorithm, more often. The list is in a code block, which the indexer skips. Written as prose, it would add to this page a term from the list that the Porter article never uses, and this page would rank first. Finishing the word brings the title rules back, since porter stemmer is an exact title.

The instant results are deliberately simpler than the full search. They do no spelling correction: a word the site never uses matches nothing (the full results page still corrects it). They are hidden while the query contains quotes, parentheses, operators, a leading plus or minus, a field name or a star, since those need the server's parser. For everything else they rank exactly as the server does, and a test makes sure of it.

Tests that hold it together

The search's checks run in the build for every pull request and every push, and the site is deployed only if they pass.

The parity test (tools/search/test_parity.py) runs the browser's code under Node.js and the server's SearchIndex.search on the same queries and compares the top eight results. The queries are every page title cut off at 3, 6 and 10 characters and in full, the known-item queries and their first halves, and a few Greek, parenthesized and possessive forms: 1,518 distinct queries at present. A typed query is compared with its server equivalent, porter ste with porter ste*. Rankings must match exactly, except that two pages may swap if their server scores differ by less than 0.005, since the exported weights are rounded. The test exists because the two implementations share no code: a change to the title bonus in Python alone would make the browser rank differently, and the test would fail.

The title test is the last block of tools/search/test_search.py: for every page on the site, searching for its exact title must return that page first. Currently all 471 pass. It protects the most common search on a reference site, typing the name of what one wants, and it constrains titles:

• The title must be distinctive in its words, not just its wording. Stop words and word order disappear, and words reduce to stems, so "The Porter Stemmer" and "Porter Stemmers" would have the same title terms, and only one of the two pages could come first. No two pages currently share a set of title terms.
• A short title that is part of a longer one relies on the title rules. Searching for "Boolean Retrieval" finds a page titled with exactly those words and another, "Boolean Search in Practice", that discusses Boolean retrieval at length. By BM25F alone, 41 pages would lose to another page for their own titles; the title bonus brings every one of them back to first place.
• Generic words make a title weaker. The bonus shrinks with the length of the title, $2|Q|/|T|$, and a title whose words appear everywhere has a low IDF to work with.

A new page that fails the test fails the build, and the fix is almost always a more specific title.

The rest of test_search.py pins down the behavior described on this page, from operator precedence and repairs to each kind of spelling correction. The build also renders /search for several queries, among them a misspelled one and an unbalanced one.

Measuring quality

Tests check behavior; they do not say whether the ranking is good. For that the site has a small evaluation, tools/search/evaluate.py, built on known-item search. Each line of tools/search/queries.tsv is a query and the one page that should come first, such as watch a web page for changes for the article on monitoring websites. There are 60 queries, split into a tuning half, used to choose the weights, and a held-out half, used only to check them.

The measures are mean reciprocal rank (MRR; Voorhees, 1999), the average of $1/r$ where $r$ is the rank of the wanted page, and success at 1 and at 3. Success at $k$ is the share of queries whose page is in the top $k$. Ranked retrieval evaluation describes all three.

Four queries miss first place, each by one rank. k-means puts K-means in Practice above The k-means Algorithm: both titles contain both terms and earn the same bonus, so BM25F decides, narrowly. rocchio algorithm puts the article on vector space classification, which discusses the Rocchio classifier, above relevance feedback. k nearest neighbors classifier puts the library article titled K-Nearest Neighbors above the course article on vector space classification that the query was written for. And query likelihood smoothing topic model finds the article on probability for information retrieval first. Several of these are reasonable answers; known-item evaluation assumes one right page.

The evaluation has other limits. It measures only whether one page comes first, not the quality of the rest of the list, so there is no recall and no graded relevance as in retrieval evaluation more generally. The queries were written by the site's author, who knows the titles, rather than collected from readers; no query log exists, since the site does not store searches. And the queries cover the information retrieval course far better than the rest of the site, which has grown well past it.

The JSON API for assistants

The site owner's chatbot answers questions from this site's content by calling two endpoints. They use the same index and ranking as the search page.

• GET /api/search?q=...&section=...&limit=... searches, with spelling correction, and returns the ranked pages. Each has its title, address, section, type, summary, score and best two passages, and each passage links to its section. limit is 1 to 20 (default 5), section is wiki or library, and the query is cut to 200 characters. The response also has corrected_from, the parser's notes and the total number of matches. A request without q gets a 400 error.
• GET /api/page/<slug>?offset=...&max_chars=... returns a whole page section by section, as many sections as fit in max_chars characters (1,000 to 60,000, default 30,000). next_offset says where to read on. The Porter article has 15 sections; asked for 5,000 characters, the endpoint returns the first four and next_offset 4. A slug that has become a course page returns 404 with the course page's address in moved_to.

Both are described at /openapi.json, an OpenAPI 3.1 document with the operations searchSite and readPage, which is what an assistant platform reads to learn how to call them. Its descriptions also tell the assistant how to search well here: a few specific keywords rather than a whole question, and a second search with different words if the first misses. That advice follows from everything above about free text and BM25F. The schema in app/routes.py is kept in step with the endpoints by hand. The site's privacy page, at /privacy, covers the API: searches made through it, like those made on the site, are processed to return results and not stored by the site.

Limits

The engine is built for a site of a few hundred pages, and its design choices follow from that size.

• The whole index lives in memory and is rebuilt at every start. That takes seconds here and would not scale to millions of pages; index construction and search at scale describe what larger systems do instead.
• The browser downloads about 1.5 MB before its first instant result. That is acceptable for a reference site read on a laptop and less so on a slow phone connection, where the form still works without it by submitting to /search.
• Analysis is for English. Accents are folded and Greek letters are named, but other scripts are not tokenized into anything the index holds, and the stemmer knows only English suffixes.
• There are no synonyms, no anchor text field, and no use of the link graph in ranking. A page is found by its own words.
• Matching is exact up to stemming and spelling correction, so a query whose words the site does not use returns nothing, even when a page answers the question in other words. Latent semantic indexing and later dense retrieval methods address this, at the cost of the transparency that makes every score on this page reproducible by hand.

What we have learned

A site of a few hundred pages can build its search from the course's own parts: fielded positional postings, the Porter stemmer, BM25F with a title bonus, a bigram index for spelling, and precomputed weights for the browser. Every score can be recomputed by hand, and tests hold the browser and the server to the same ranking. The same tokenizer and stemmer also serve a second purpose, reviewing the site's content as a whole, which How the Content Analysis Tools Work describes.

References

• Damerau, F. J. (1964). A technique for computer detection and correction of spelling errors. Communications of the ACM, 7(3), 171–176.
• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapters 2 (tokenization, stemming, positional indexes), 3 (spelling correction) and 6 (zones and scoring). Cambridge University Press.
• OpenAPI Initiative (2021). OpenAPI Specification, version 3.1.0. https://spec.openapis.org/oas/v3.1.0
• Porter, M. F. (1980). An algorithm for suffix stripping. Program, 14(3), 130–137.
• Robertson, S., Zaragoza, H., and Taylor, M. (2004). Simple BM25 extension to multiple weighted fields. In Proceedings of CIKM 2004, 42–49.
• Robertson, S., and Zaragoza, H. (2009). The probabilistic relevance framework: BM25 and beyond. Foundations and Trends in Information Retrieval, 3(4), 333–389.
• Voorhees, E. M. (1999). The TREC-8 question answering track report. In Proceedings of the Eighth Text REtrieval Conference (TREC-8), 77–82.

Code for this page: tools/experiments/search/how-this-search-works.py prints every number quoted about the index, and tools/figures/how-this-search-works.py draws the figures.