Keyword search from scratch

How a search engine finds the right page

A search engine has to pick the best few pages out of thousands, fast. It starts by listing which words appear in which documents (the index). Then it either keeps and drops documents with yes/no rules (Boolean search), or gives each one a score from its words (TF-IDF and BM25). Every number is shown, so you can check each score yourself.

Try this first
  1. Open “Read the 10 documents” below. They describe a made-up island, Fernport. Each document’s title counts as part of its text.
  2. In The index, press “ferry” and see which documents contain it, and how many times.
  3. In Boolean search, press “ferry AND NOT bike” and read the steps. Then press “harbour AND ferry”.
  4. In TF-IDF, press “harbour dogs” and check one score by hand: tf × idf for each word, added together.
  5. In BM25, press “harbour dogs”, then drag b to 0 and watch the scores change.
  6. In Compare, press “harbour dogs” to see all three searches at once.
Read the 10 documents

Fernport is a made-up island. A document’s title counts as part of its text when the index is built.

Fernport Bakery
Fernport Bakery stands on Harbour Street. It is run by Mira Okafor. Mira is famous for her dark rye bread, baked only on Tuesdays. She learned to bake from Tomas Reyes when she was sixteen. The shop opens at 7 in the morning and closes when the bread is gone.
Fernport Lighthouse
The Fernport Lighthouse was built in 1891 on the north cliff. Its lamp can be seen 30 kilometres out at sea. Guided tours run on Saturdays and Sundays at 10:00 and 14:00. The guide is Tomas Reyes, who has climbed the lighthouse’s 120 stairs every week for 20 years. The lighthouse is closed in January for repairs.
Ferry timetable
The ferry crosses from Millbay on the mainland to Fernport in 40 minutes. A ferry fare costs 6 coins, and children ride free. Bikes travel for 1 coin more. December to February is the quiet season. Then there is only one crossing a day, at 10:00 from Millbay. The rest of the year, the ferry leaves Millbay at 8:00, 12:00 and 17:00.
Lantern Festival
The Lantern Festival lights up Fernport every October. People hang paper lanterns along Harbour Street for a week. On the last night of the festival, everyone walks to the north cliff to watch the lighthouse lamp switch on.
Visitor rules
Visitors may camp only at the campsite behind the school. Fires are allowed on the beach, but never in the woods. Dogs must stay on a lead near the harbour.
Harbour guide
The Fernport harbour is the busiest place in town. The harbour has a long stone wall, and the harbour wall keeps the water calm inside. Fishers bring their catch to the harbour at dawn, and the harbour market sells it fresh by seven. Every morning the harbour fills with gulls, nets and carts. The ferry from the mainland ties up at the harbour, at the far end of the east pier. A small harbour office hands out maps and answers questions. The harbour café serves hot soup to anyone who is cold. Walk along the harbour edge at sunset to see the water turn orange. At night the harbour is lit by a row of yellow lamps, and the harbour is quiet. The harbour crane lifts crates of apples, wool and salt from the quay onto carts. Young children feed the gulls near the harbour steps, while old fishers mend their nets and trade stories about the weather. Two painted sheds beside the harbour store ropes, buoys and lamps. A harbour bell rings at noon, and again when the tide turns. Anyone who loves the sea should spend a slow afternoon at the harbour.
Fernport School
Fernport School teaches about forty children, from age five to twelve. Classes start at 9 in the morning and end at 3. Every child learns to swim in the sea pool, and older children learn to sail. The school library is open to the whole town on Wednesdays. The school choir sings at the end of every term.
Saturday market
The Saturday market fills the square beside the town hall. Farmers sell apples, honey and goat cheese. Weavers sell wool scarves and hats. A woman named Ida Lund sells smoked fish from a blue stall. The market opens at 8 in the morning and packs up at noon.
Weather and seasons
Fernport is mild and damp. Summer days reach about 22 degrees, and the sea is warm enough to swim in July and August. Autumn brings strong winds from the west. Fog often covers the cliffs in the early morning. It snows only once or twice a year, and the snow melts by noon.
History of Fernport
Fernport began as a fishing village about 400 years ago. The first stone houses were built in 1650, from rock taken from the cliffs. A great storm in 1702 washed away the old pier, and the town built a new one. In 1950 a bridge was planned, but the islanders voted against it. Today about 900 people live in Fernport.

Chapter 1: The index: a list of where each word lives

Reading every document for every question is slow. So a search engine reads each document once and writes down, for every word, which documents contain it and how many times. That list is the inverted index. Each entry in it is a posting. A document’s title counts too: its words go into the index along with its text.

Try “ferry”: you get two documents, and the number of times the word appears in each. Then try “harbour” and see how many more documents it reaches.

1 search word looked up.

ferry: in 2 of 10 documents
Ferry timetable (4×), Harbour guide (1×)

Chapter 2: Boolean search: yes or no, with AND, OR and NOT

The simplest search keeps or drops each document. Type words joined by AND (the document needs both), OR (either one is enough) or NOT (the document must not have the word). It is read from left to right, and every step is shown. There is no ranking: a document either matches or it does not.

Try “ferry AND NOT bike”: the ferry timetable mentions bikes, so it is dropped, and the harbour guide is left.

1 document match.

Steps

  1. Documents with ferry: ferry, harbour
  2. Documents without bike: bakery, festival, harbour, history, lighthouse, market, rules, school, weather
  3. AND keeps documents in both lists: harbour

Documents that match

  1. Harbour guide

Chapter 3: TF-IDF: score each document

To put the best document first, every search word gives each document a part of the score: how many times the word appears there (tf) times how rare the word is across all documents (idf). Rare words count for more. The parts are added up to the total.

Try “harbour dogs”: the harbour guide says “harbour” many times and wins. The rules say “dogs” only once, but “dogs” is rare, so they still score well. Notice a long document gets no penalty here.

4 documents scored. Top result: Harbour guide.

Scroll sideways to see every column.

DocumentWordtfdfidfPartTotal
1. Harbour guideharbour1840.91616.49316.493
2. Visitor rulesharbour140.9160.9163.219
dog112.3032.303
3. Fernport Bakeryharbour140.9160.9160.916
4. Lantern Festivalharbour140.9160.9160.916

Chapter 4: BM25: stop repeats and length from winning

BM25 is the score most search engines use. It fixes two problems of TF-IDF. Saturation: the tenth “harbour” helps much less than the first, and k1 sets how fast that levels off. Length normalization: a word in a short document says more than in a long one, and b sets how strongly length is held against a document. Move the sliders and watch the table change. To check a row by hand: part = idf × tf × (k1 + 1) ÷ (tf + length factor), where length factor = k1 × (1 − b + b × this document’s words ÷ average words). BM25’s idf is ln(1 + (N − df + 0.5) ÷ (df + 0.5)), which is not the same as TF-IDF’s ln(N ÷ df). The table shows each document’s word count, and the average is just above it.

Try “harbour dogs” again. Repeats of “harbour” are cut short, so the visitor rules (which have the rare word “dogs”) beat the harbour guide. Now drag b to 0 (ignore length): the short visitor rules lose their length bonus and their total falls from 3.73 to 2.89.

4 documents scored. Top result: Visitor rules.

Average document length: 42.50 words (search words in the title and text, filler words not counted). N = 10 documents.

Scroll sideways to see every column.

DocumentWordtfdfidfWords in documentLength factorPartTotal
1. Visitor rulesharbour140.894190.7021.1553.730
dog111.992190.7022.575
2. Harbour guideharbour1840.8941212.8621.6971.697
3. Lantern Festivalharbour140.894270.8721.0511.051
4. Fernport Bakeryharbour140.894300.9351.0161.016

Chapter 5: Compare: the same question, three searches

Here one question goes through all three searches side by side, so you can see where they agree and where they differ. BM25 uses k1 = 1.2 and b = 0.75.

Try “harbour dogs”: Boolean search keeps only the visitor rules, the one document with both words, and cannot put anything in order. TF-IDF and BM25 rank every document that has either word, and they order them differently.

Boolean: 1 match. TF-IDF: 4 documents scored. Top result: Harbour guide. BM25: 4 documents scored. Top result: Visitor rules.

Boolean

  1. Visitor rules

TF-IDF

  1. Harbour guide 16.493
  2. Visitor rules 3.219
  3. Fernport Bakery 0.916
  4. Lantern Festival 0.916

BM25

  1. Visitor rules 3.730
  2. Harbour guide 1.697
  3. Lantern Festival 1.051
  4. Fernport Bakery 1.016
Word list
Search engine
A program that finds the documents that best fit a question. This lab builds a small one from scratch.
Document
One page of text, like the ferry timetable. Its title counts as part of its text.
Search words
The words of your question that are kept for searching. Very common words (stop words, also called filler words) are dropped, and a plural “s” is cut so “tours” matches “tour”.
Stop words (filler words)
Words so common that they say nothing about the topic, like “the”, “is” and “when”. They are too common to search for, so they are left out.
Skipped
Something in your question that the search left out: a stop word, or an AND, OR or NOT with no word to apply to (for example one at the very start or end).
Index
A list made ahead of time so a search does not have to read every document again.
Inverted index
An index that goes from word to documents (“ferry” → the timetable and the harbour guide), the opposite of a document that goes to its words.
Posting
One entry in the inverted index: a document that has the word, and how many times it has it.
Boolean search
Search with yes/no rules. A document matches or it does not, so there is no ranking.
AND
Keep only documents that match both sides.
OR
Keep documents that match either side.
NOT
Drop documents that contain the word after it.
Term frequency (tf)
How many times a word appears in one document.
Document frequency (df)
How many documents contain the word at least once.
IDF
Inverse document frequency: how rare a word is. TF-IDF uses ln(N ÷ df), where N is the number of documents. ln is the natural logarithm; a calculator has an ln key. A word in every document gets 0, because it cannot tell documents apart.
N
The number of documents in the index.
TF-IDF
A score for a word in a document: tf × idf. A document’s total is the sum over the search words.
BM25
A score used by many real search engines. Like TF-IDF, but repeats count less and long documents are held back a little. Part for one word = idf × tf × (k1 + 1) ÷ (tf + length factor), with idf = ln(1 + (N − df + 0.5) ÷ (df + 0.5)). This idf differs from TF-IDF’s ln(N ÷ df).
k1
BM25 setting for saturation. Low k1: repeats stop helping quickly. High k1: repeats keep adding.
b
BM25 setting for length normalization, from 0 (ignore length) to 1 (fully correct for length).
Words in document
How many search words a document has, counting its title (stop words are not counted). Also called the document’s length.
Length normalization
Comparing a document’s length to the average, so a word in a short document counts for more than the same word in a long one.
Length factor
The number the table shows for length normalization: k1 × (1 − b + b × this document’s word count ÷ the average word count). Bigger means a longer document.
Saturation
The effect that each extra repeat of a word adds less than the one before.
Part
One search word’s share of a document’s score: tf × idf for TF-IDF, or the BM25 formula for BM25.
Total
A document’s score: its parts added up.
Rank
A document’s place in the results: 1 is the best score.
Score
A document’s total: the parts for each search word added up. Higher means a better match.