Skip to content
Tutorials Center
My learning

Topics

Lesson 187 of 201 ยท Projects

Project: A Simple Search Engine

Build a small Java search engine with a tokenizer, an inverted index, term frequency and TF-IDF ranking, prefix and exclusion queries, highlighted snippets and live add and remove.

Every search box you use, from a text editor to a web search engine, is built on one data structure: the inverted index. It answers "which documents contain this word?" without reading a single document at query time. Instead of scanning every text for the word stream, you look stream up in a map and get the list of documents immediately, the way a book's index sends you to pages instead of making you reread the book.

In this project you'll build that engine in three steps. First the tokenizer and index, with exact word search. Then ranking: when 500 documents contain your word, which one should come first? You'll work out term frequency and inverse document frequency (TF-IDF) with real numbers. Finally the complete engine, with prefix queries (stream*), exclusions (-thread), highlighted snippets and documents that you can add and remove while it runs.

You'll practice maps and computeIfAbsent, sorted maps, sets, records, regular expressions, string handling and sorting with comparators. The same ideas, at a much larger scale, power libraries such as Lucene, which sits underneath Elasticsearch and Solr.

How an inverted index works

A forward index maps documents to words: document 3 contains threads, locks, data. To find a word you'd have to open every document. An inverted index flips the relationship:

TEXT
list     -> documents 0, 2, 6, 7
stream   -> documents 2, 6, 7
thread   -> document 3

Each word maps to its posting list, the documents it appears in. A search for list stream becomes a lookup of two posting lists and an intersection of two small sets. The time depends on how many documents contain the words, not on how many documents exist.

Building it takes three steps:

  1. Tokenize. Split text into words: lowercase it and cut at every character that isn't a letter or digit.
  2. Filter. Drop stop words (the, and, of...) that appear everywhere and tell you nothing.
  3. Normalize. Reduce word forms so list and lists are one term. Real engines use stemmers such as Porter's algorithm; we'll use a deliberately crude rule that strips a plural s.

The same pipeline must run on documents and on queries, otherwise a search for Lists would never find lists.

Stage 1: tokenizing and indexing

Java Stage 1: tokenizer and inverted index

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

What to notice:

  • computeIfAbsent creates the posting set the first time a term is seen, then adds the document id. That one line is the whole indexing loop.
  • TreeMap keeps terms sorted. You'll use that for prefix search later, and it makes the printouts easy to read.
  • TreeSet keeps each posting list sorted by id, and retainAll intersects two sets in place. Searching for several words as a logical AND is nothing more than that.
  • The crude pipeline already shows its weakness. lists and list are different terms, so lists finds documents 0, 2 and 6 but misses 7, which says list. The AND search for lists streams finds 2 and 6. A stemmer fixes this, which is why the next stage adds one.
  • Searching Streams works because the query goes through the same tokenize, which lowercases it.

Stage 2: ranking with TF-IDF

An index finds which documents match. Users want the best ones first. Two ideas rank documents without understanding language:

Term frequency (TF). A document that mentions stream five times in 100 words is probably more about streams than one that mentions it once in 100 words. Count how often the term appears, divided by the document's length so long documents don't win just by being long.

Inverse document frequency (IDF). A word that appears in every document, such as java in a Java tutorial, helps nothing in telling documents apart. A word found in only one document is a strong signal. The rarer the term, the higher its weight. A common formula is:

TEXT
idf(term) = ln(1 + N / df)       N = number of documents, df = documents containing the term
score(doc, query) = sum over query terms of  tf(term, doc) * idf(term)

The next program computes the numbers for four tiny documents and a two-word query, and prints every step, so you can follow the arithmetic.

Java Stage 2: term frequency, document frequency and scores

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Read the table:

  • java is in 3 of 4 documents, so its IDF is low (about 0.85). lists is in 2 of 4, so it's higher (about 1.10). A hit on the rarer word is worth more.
  • Document 1 says lists four times in five words, so its TF for lists is 0.8, and it gets the top score even though the query also contains java.
  • Document 3 has no query word, so its score is 0. It never appears in results at all.
  • Document 2 contains both words but only once each among six words, so it scores lower than document 1 despite matching more query terms. That's a legitimate TF-IDF result, and a real engine would tune such trade-offs.

This is a simple member of a family. Production engines use BM25, which adds saturation (the tenth occurrence of a word counts less than the second) and a smarter length normalization, but they're built from exactly the same ingredients.

Stage 3: the complete search engine

The final program puts it all together:

  • A SearchIndex class with add, remove and search. Postings are Map<String, Map<Integer, Integer>>: term, then document id, then the number of occurrences. Document lengths are stored separately for TF.
  • A tiny stemmer: ies becomes y, and a trailing s is dropped (but not in ss, is or us). It's crude, and it's applied to documents and queries alike.
  • Query syntax: plain words are included, word* matches every term starting with the prefix (a TreeMap.subMap range scan), and -word removes documents containing that word.
  • Snippets show the first match in context, with matching words in square brackets, found with a Matcher over the original text.
  • Live updates: add Title | text indexes a new document, and remove id deletes its postings. Both leave the index consistent.
Java Stage 3: the complete search engine

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Read the output:

  • search list now finds the singular and plural documents, because the stemmer maps lists and list to one term. The short Lists document ranks first: the term fills a larger share of a short text, and its title adds a second occurrence.
  • search lists streams ranks documents that contain both words ahead of those that contain one, because their scores add up.
  • search stream* expands to every term starting with stream in the sorted term map. With the crude stemmer it also catches streams as stream.
  • search list -stream removes every document containing stream, which drops the documents about streams and collections.
  • search the and consists only of stop words, and reports an error instead of returning everything.
  • After add Executors | ... the new document 8 is findable at once and ties with document 3 on score, so the tie is broken by id. remove 4 deletes the document about sets, and stats at the end reflects both changes: the new terms were added and the removed document's terms are gone (unique and treeset, for example, disappear).

Design notes

  • The pipeline is shared. analyze is used for documents and for each query word, so they always agree on what a term is.
  • remove cleans up empty terms so stats stays honest and prefix scans never return terms with no documents.
  • TreeMap.subMap(prefix, prefix + Character.MAX_VALUE) is an efficient range scan: it jumps to the first term with the prefix and stops after the last one, without looking at the rest of the vocabulary.
  • Snippets use appendReplacement with quoteReplacement. Without it, a $ or backslash in a document could be misread as a group reference and throw an exception.
  • The index returns Hit records, not printed text. A web page, a command line and a test can all use the same results.
  • It's an in-memory engine. Real engines keep postings on disk in compressed blocks, update them in segments and merge in the background.

Ideas to extend it

  • Phrase search: store the positions of each term in each document (Map<Integer, List<Integer>>) and require consecutive positions for "hash map".
  • A real stemmer: implement the first step of Porter's algorithm (sses to ss, ies to i, ed and ing removal).
  • BM25 scoring instead of plain TF-IDF.
  • Fuzzy matching: suggest streams when someone types steams, using the edit distance from the dynamic programming lesson.
  • Persistence: write the documents to a file and rebuild the index on startup, or save the index itself with object streams.
  • Index files from a folder by walking it with Files.walk, indexing every .txt file, and showing the path as the title.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What makes an inverted index fast for searching?

    A lookup in the term map returns the posting list directly. Query time depends on the number of matching documents, not on the number of documents in the collection.
  2. 2. Why must documents and queries go through the same tokenizer and stemmer?

    Search compares terms for equality. If the index and the query are normalized differently, equal words end up as different terms and matches are missed.
  3. 3. In TF-IDF, why does a rare term contribute more to a document's score than a common one?

    idf = ln(1 + N/df) grows as df shrinks. A word that appears in every document tells you nothing, while a word in one document is a strong signal.
  4. 4. What does TreeMap.subMap(prefix, prefix + Character.MAX_VALUE) provide for prefix queries?

    Because the keys are sorted, the range from the prefix to the prefix plus the highest character is exactly the terms that start with that prefix.

Summary

  • An inverted index maps each term to its posting list; a multi-word search intersects posting lists instead of scanning documents.
  • Build terms by tokenizing, removing stop words and normalizing (stemming), and apply the same steps to documents and queries.
  • TF-IDF ranks results: term frequency rewards documents that use a term often, inverse document frequency rewards rare terms.
  • A sorted TreeMap of terms turns prefix queries into cheap range scans.
  • Return results as records that carry the score and a highlighted snippet, and keep printing out of the engine.
  • Keep updates consistent: adding indexes new postings, removing deletes them and prunes empty terms.

Next: Project: Sudoku Solver, where you'll validate boards and solve them with backtracking.