Skip to content

Advanced project · Large

Mini search engine

You build the searching half of a search engine: tokenise a set of documents, build an inverted index from term to the documents containing it, then answer multi-word queries ranked by relevance rather than by document order. Queries must be answered from the index alone, never by re-reading the documents, and you have to be able to explain any score it produces. A stats report at the end tells you what you actually built.

Languages
Python
Size
Large: a longer build over several weeks
Where to build it
The whole thing runs in the Python playground if the corpus is a list of strings in the program, because the playground cannot read files from your computer. Build it on your own computer instead when you want to index a real folder of text files. Open the Python playground →

What you will practise

  • designing an index: a dictionary of term to posting list
  • tokenising text, and every decision that hides inside that word
  • term frequency and inverse document frequency scoring
  • sorting by a computed score with a stable tiebreaker
  • reasoning about what grows with the corpus and what does not
  • writing a scoring function you can explain to someone else

Requirements

The project is done when every one of these is true.

  • A tokeniser lowercases text, splits on anything that is not a letter or a digit, drops tokens on a stop-word list you write yourself, and is the only place tokenising happens.
  • The index maps each term to a posting list of document id and term frequency pairs, built in a single pass over the documents.
  • Answering a query touches only the index and a small per-document table of metadata; it never re-reads document text except to cut a snippet for display.
  • A multi-word query returns only documents containing every query term, and returns them ranked, not in document order.
  • The ranking formula is written down in a comment and implemented exactly as written: the score is the sum over query terms of the term frequency in the document multiplied by the natural logarithm of the document count divided by the number of documents containing that term.
  • Results show the document title, the score and a snippet of text around the first match, and a result with no printable snippet still prints a row.
  • Ties in score are broken by a documented rule, such as document id, so the same query always prints the same order.
  • A query term that appears in no document returns no results and a clear message, and an empty or stop-words-only query returns a message rather than every document.
  • A stats command reports the number of documents, the number of unique terms, the total number of postings and the ten most frequent terms with their document counts.

Milestones

A sensible order to build it in, so something works at every step.

  1. Tokenise one document and print the tokens

    Write the tokeniser first and stare at its output on a real paragraph. Every later bug that looks like a ranking bug usually starts here.

  2. Build the inverted index

    Walk every document once, count each term within it, and append a posting. Print a few posting lists and check them against the text by hand.

  3. Answer a one-word query

    Look the term up and print the documents in its posting list. No ranking yet, so you can see the index working on its own.

  4. Add AND across several terms

    Intersect the posting lists, starting with the rarest term so the intersection shrinks fastest, and confirm a document missing one term is excluded.

  5. Add the ranking formula

    Write the formula in a comment, implement it, and print the per-term contributions next to each score while you are developing so you can check the arithmetic.

  6. Add snippets and the stats report

    Cut a window of text around the first match for display, then add the stats command so you can see the size and shape of your index.

  7. Test the shape of the growth

    Multiply your corpus by concatenating copies, and confirm build time grows with it while query time barely moves. That gap is the point of the whole project.

Hints

Open one only when you are stuck. Each gives a little more away.

Show hint 1

Tokenising is where search engines are won and lost. Write down your decisions about case, digits, apostrophes and hyphens, because every one of them changes what users can find.

Show hint 2

A term that appears in every document has a document frequency equal to the document count, so the logarithm of one is zero and the term contributes nothing to any score. That is the formula working, not a bug.

Show hint 3

Intersect from the shortest posting list outwards. Starting with the most common term means doing the most work before throwing most of it away.

Show hint 4

Keep the per-document total token count when you build the index. You will want it for length normalisation later, and recomputing it means re-reading the documents, which the requirements forbid.

Show hint 5

Print the score's per-term parts while you develop. A score alone tells you nothing; term frequency times inverse document frequency per term tells you immediately which half is wrong.

Show hint 6

The playground cannot reach files on your computer, so keep the corpus as a list of title-and-text strings in the program. On your own computer you can point the same build function at a folder of text files and change nothing else.

How to test it

Run these checks yourself, or turn them into automated tests once you know how.

  • Index a single document whose text is Cat cat CAT. and confirm the posting list for cat holds one posting with a term frequency of 3, which checks lowercasing and splitting together. Then index the text the cat sat on the mat with the and on on your stop list, and confirm that document contributes exactly three terms: cat, sat and mat.
  • With four documents and a term that appears in exactly one of them, the inverse document frequency is the natural logarithm of 4, about 1.386; check one score by hand against that. Then add a term that appears in all four documents to the query and confirm the ranking order does not change at all, because its contribution is the logarithm of one, which is zero.
  • Query a single term that appears in exactly one document: the result list must have exactly one row, that document.
  • Query two terms where one document has both and another has only one: only the document with both may appear.
  • Query a term that appears nowhere: expect zero results and the nothing-found message, with no error.
  • Build the index twice from the same documents and compare the posting lists: they must be identical, which catches anything depending on dictionary iteration order.
  • Concatenate a document with itself, re-index, and check that its term frequencies exactly double and that its score changes in the direction your formula says it should.
  • Run stats on a corpus you wrote yourself, add up the unique terms of two documents by hand, and confirm the reported unique-term count matches.

Stretch goals

  • Add phrase search by storing token positions in the posting list and requiring adjacency.
  • Add a length normalisation term so a long document does not outrank a short, focused one on term frequency alone.
  • Add prefix search over a sorted term list, so typing part of a word finds the rest.
  • Serialise the index to a file and load it back, then check that queries against the loaded index are identical.
  • Add an OR mode alongside AND, and write down which one a user would expect by default and why.

Learn what you need

All projects · Roadmaps · Practice problems