Keyword search

The core data structure is the inverted index: a term dictionary (in Lucene, compressed as a finite-state transducer) mapping each term to a postings list of document IDs, usually with term frequencies and positions, stored delta-encoded and compressed. A query looks up the postings for each query term and scores only documents that appear in at least one list. Positions enable phrase and proximity queries; per-field indexes enable restricting or weighting fields such as title versus body. Top-k evaluation avoids scoring every match through dynamic pruning algorithms such as WAND and Block-Max WAND, which skip documents whose maximum possible score cannot enter the current top k.

BM25, from the Okapi system at City University London and formalised in the probabilistic relevance framework (Robertson and Zaragoza, 2009), scores a document D for query Q as Σ IDF(q) · f(q, D) · (k₁ + 1) / (f(q, D) + k₁ · (1 − b + b · |D| / avgdl)). The term-frequency component saturates: the first occurrences of a term add most, and further repetitions add less and less, with k₁ controlling how fast (typical values 1.2-2.0). The parameter b (typically 0.75) normalises for document length relative to the average avgdl, so long documents are not rewarded simply for containing more words. Lucene's IDF is ln(1 + (N − n + 0.5) / (n + 0.5)) for N documents of which n contain the term, so rare terms dominate. Lucene made BM25 its default similarity in version 6.0 (2016), replacing classic TF-IDF, with k₁ = 1.2 and b = 0.75; BM25F extends the formula to weighted fields. PostgreSQL's built-in ts_rank, by contrast, is not BM25 and uses no corpus-wide IDF.

Quality depends as much on the analysis chain as on the formula: tokenisation, lowercasing, Unicode folding, stop words, stemming or lemmatisation, and synonyms. Danish needs particular care. The Snowball Danish stemmer handles inflection, but productive compounding means that "sygedagpengeloven" does not match "sygedagpenge" or "loven" without dictionary-based decompounding, and the characters æ, ø and å must not be folded to ASCII in a way that merges distinct words. The same analyser must be applied at index and query time, otherwise terms silently fail to match.

The classic weakness is vocabulary mismatch: relevant documents that use different words score zero. Mitigations include synonym lists, query expansion with pseudo-relevance feedback (for example RM3), fuzzy matching by edit distance for typos, and, today, combining the lexical ranking with dense retrieval in hybrid search. Its strengths are explainability (every score decomposes into per-term contributions), no training requirement, cheap incremental updates and deletions, and robustness on unseen domains, which is why BM25 remains the standard baseline in retrieval benchmarks.