BM25 keyword search

score(D, Q) = Σ over query words t: IDF(t) × tf ÷ (tf + k1 × (1 − b + b × dl ÷ avdl))

For each query word, multiply its rarity weight by a saturating function of how often it appears, where k1 is scaled by the document's length relative to the average (dl is the document's length, avdl the average). Add up the words. Many versions also multiply by (k1 + 1), which scales every score equally and leaves the ranking unchanged.

Worked example: “router” (IDF 4.20) appears 4 times in an 80-word page, average length 100, with k1 = 1.2 and b = 0.75: 4 ÷ (4 + 1.2 × 0.85) = 0.80, so the word earns 4.20 × 0.80 ≈ 3.34 points.

IDF(t) = ln(1 + (N − n + 0.5) ÷ (n + 0.5))

N is the number of documents and n the number that contain the word. This is Lucene's form; the Robertson–Spärck Jones weight it comes from has no “1 +” and turns negative for words found in more than half the documents.

Worked example: Among 10,000 documents, a word found in 150 of them gets ln(1 + 9,850.5 ÷ 150.5) ≈ 4.20; a word found in 1,200 gets about 2.12.

tf ÷ (tf + k1) → 1 as tf grows

The saturation curve for a document of average length: the share of a word's IDF that its mentions earn.

Worked example: With k1 = 1.2, one mention earns 45% of the maximum, three earn 71%, ten earn 89% and twenty earn 94%: repetition quickly stops paying.