Simple Search Engine

Underneath every "search this corpus" feature is the same three-step pipeline: break text into terms, remember which documents each term appears in, and score documents against a query using those term overlaps. The design question is which of those three steps you're willing to swap out later - the answer should be all of them.

Requirements

Functional

index(document) tokenizes a document's text and records it so it becomes searchable.
search(query) tokenizes the query and returns matching documents ranked by relevance.
Relevance ranking should account for how often a query term appears in a document, not just whether it appears at all.

Non-functional

Looking up documents for a query term must not scan every indexed document - it should go straight to the documents that contain that term.
Tokenization rules (lowercasing, stemming, stopword removal) and the scoring formula both change often as search quality improves; neither should require touching the indexing or query flow itself.

Design

InvertedIndex maps each term to a postings list of (documentId, termFrequency) pairs - the one structure that makes "which documents mention this term, and how often" an O(1) lookup instead of a document scan. Tokenizer and Scorer sit on either side of it as interfaces: one turns raw text into terms, the other turns term overlaps into a ranking, and SearchEngine just wires the three together.

1Indexing and querying both go through the same engine facade.
2The document's raw text is turned into terms using the one shared tokenizer.
3Each term is recorded against this document, with its frequency, in the inverted index.
4Later, a query arrives as plain text, same shape as a document.
5The query is tokenized identically - this is what makes the two tokenizer calls safe to be the same instance.
6Each query term goes straight to its postings list - no document is scanned that doesn't contain the term.
7Term frequencies collected from the index are handed to the scorer to rank matching documents.

Indexing and querying run through the exact same Tokenizer - if they used different tokenization rules, a document containing "running" would never match a query for "running" tokenized differently, silently.

Class diagram

implementsuses

Tokenizer and Scorer are pluggable on either side of InvertedIndex, which never changes when either does.

Code

import java.util.*;
 
class Document {
    final String id;
    final String text;
 
    Document(String id, String text) {
        this.id = id;
        this.text = text;
    }
}
 
interface Tokenizer {
    List<String> tokenize(String text);
}
 
class SimpleTokenizer implements Tokenizer {
    public List<String> tokenize(String text) {
        return Arrays.asList(text.toLowerCase().split("\\W+"));
    }
}
 
class Posting {
    final String documentId;
    int termFrequency;
 
    Posting(String documentId) {
        this.documentId = documentId;
        this.termFrequency = 0;
    }
}
 
class InvertedIndex {
    private final Map<String, Map<String, Posting>> postings = new HashMap<>();
 
    void addPosting(String term, String documentId) {
        Map<String, Posting> byDoc = postings.computeIfAbsent(term, t -> new HashMap<>());
        Posting posting = byDoc.computeIfAbsent(documentId, Posting::new);
        posting.termFrequency++;
    }
 
    Collection<Posting> postingsFor(String term) {
        return postings.getOrDefault(term, Map.of()).values();
    }
}
 
interface Scorer {
    double score(List<String> queryTerms, String documentId, InvertedIndex index);
}
 
class TermFrequencyScorer implements Scorer {
    public double score(List<String> queryTerms, String documentId, InvertedIndex index) {
        double total = 0;
        for (String term : queryTerms) {
            for (Posting posting : index.postingsFor(term)) {
                if (posting.documentId.equals(documentId)) total += posting.termFrequency;
            }
        }
        return total;
    }
}
 
class SearchEngine {
    private final InvertedIndex index = new InvertedIndex();
    private final Map<String, Document> documents = new HashMap<>();
    private final Tokenizer tokenizer;
    private final Scorer scorer;
 
    SearchEngine(Tokenizer tokenizer, Scorer scorer) {
        this.tokenizer = tokenizer;
        this.scorer = scorer;
    }
 
    void index(Document document) {
        documents.put(document.id, document);
        for (String term : tokenizer.tokenize(document.text)) {
            index.addPosting(term, document.id);
        }
    }
 
    List<Document> search(String query) {
        List<String> queryTerms = tokenizer.tokenize(query);
        Set<String> candidateIds = new HashSet<>();
        for (String term : queryTerms) {
            for (Posting posting : index.postingsFor(term)) {
                candidateIds.add(posting.documentId);
            }
        }
 
        List<Document> results = new ArrayList<>();
        for (String id : candidateIds) results.add(documents.get(id));
        results.sort((a, b) -> Double.compare(
            scorer.score(queryTerms, b.id, index),
            scorer.score(queryTerms, a.id, index)));
        return results;
    }
}

Design decisions

The index stores postings as (documentId, termFrequency), not just a set of document ids per term. A pure set answers "does this document contain the term" but throws away the count a scorer needs. Storing the frequency once, at index time, means Scorer never has to re-read the document's raw text to count anything.
Tokenizer is shared by both indexing and querying, not reimplemented for each. The entire index is only useful if a query term and an indexed term were produced by the same rules. Passing one Tokenizer instance into both index and search is what guarantees that invariant instead of hoping two call sites stay in sync.
Scorer is a separate interface from InvertedIndex, even though it's the index it reads from. Swapping term-frequency scoring for TF-IDF (which also needs to know how many total documents contain a term) is then a new class that reads the same index differently, not a rewrite of how the index stores data.
What's missing for a real system: term-frequency scoring rewards long documents that repeat common words - TF-IDF or BM25 correct for that by weighting down terms that appear in most documents - and this design only supports append-only indexing; updating or deleting a document means also removing its old postings, which a real inverted index tracks via document versioning rather than an in-place overwrite.

Requirements​

Design​

Class diagram​

Code​

Design decisions​

Requirements

Design

Class diagram

Code

Design decisions