README
¶
bm25
Okapi BM25 keyword-relevance ranking and reciprocal-rank fusion (RRF) for Go — small, dependency-free, and built for the keyword half of hybrid (keyword + semantic) search.
- Zero third-party dependencies —
math/strings/unicodeonly. go 1.21+ — broad compatibility, no surprises.- Two layers: a one-call
Corpusfor the common case, and the low-levelScorerprimitives when you need to tokenize yourself or score against a per-query candidate set. - RRF built in — fuse a BM25 ranking with a vector-similarity (or any other) ranking, the standard recipe for hybrid search, with no weights to tune.
go get github.com/richardwooding/bm25
Keyword ranking
c := bm25.New()
c.Add("moby", "Call me Ishmael. The whale, the ship, the sea.")
c.Add("austen", "It is a truth universally acknowledged, marriage and fortune.")
for _, r := range c.Search("whale ship", 5) {
fmt.Printf("%.3f %s\n", r.Score, r.ID)
}
// 1.39 moby
Search(query, k) returns the top k documents by BM25 score, descending (ties broken by
ID); k <= 0 returns all. IDF and average document length are computed over the whole
corpus — the standard Okapi BM25 setup. Tune the parameters with
bm25.NewWithParams(k1, b).
Hybrid search (reciprocal-rank fusion)
Keyword search is precise on exact terms; vector search catches paraphrase. RRF blends two ranked lists into one without picking weights:
keyword := c.Search("http caching proxies", 0) // []bm25.Result
semantic := myVectorIndex.Search("http caching", 0) // your embedding ranker
// Fuse the two orderings (best-first ID lists) into one ranking.
fused := bm25.FuseRanked(bm25.DefaultRRFK,
ids(keyword), // []string of IDs, best-first
ids(semantic),
)
fmt.Println(fused[0].ID) // strong in both lists ranks first
ReciprocalRankFusion returns the raw map[id]score if you'd rather sort yourself.
Bring your own tokenizer
Corpus uses a deliberately simple built-in tokenizer (lowercased Unicode
letter/digit runs). For stemming, stop-words, or n-grams, tokenize however you like and
drive the low-level API:
queryTerms := myTokenize(query)
docs := make([]bm25.DocStats, len(corpus))
for i, d := range corpus {
docs[i] = bm25.StatsForTokens(myTokenize(d.text), queryTerms)
}
scorer := bm25.NewScorer(queryTerms, docs, bm25.DefaultK1, bm25.DefaultB)
score := scorer.Score(docs[0])
This low-level path also lets you compute IDF over a per-query candidate set (e.g. only the documents that passed an upstream filter) rather than the whole corpus.
License
MIT — see LICENSE.
Extracted from file-search-on, where it powers hybrid keyword + semantic file search.
Documentation
¶
Overview ¶
Package bm25 implements Okapi BM25 keyword relevance scoring plus reciprocal-rank fusion, the keyword half of hybrid keyword+semantic search (issue #335).
BM25 ranks a document d against a query Q as:
score(d, Q) = Σ_{t∈Q} IDF(t) · ( f(t,d)·(k1+1) ) / ( f(t,d) + k1·(1 − b + b·|d|/avgdl) )
where f(t,d) is the term frequency of t in d, |d| is the document length in tokens, avgdl is the mean document length over the corpus, and IDF(t) = ln( 1 + (N − n(t) + 0.5)/(n(t) + 0.5) ) with N documents and n(t) documents containing t. The IDF form is the BM25+ variant that stays non-negative, so a term appearing in every document scores ~0 rather than going negative.
The corpus here is the candidate set being ranked (issue #335's "candidate set" decision): IDF and avgdl are computed over exactly the files that survived the CEL pre-filter, so relevance is relative to the result set the caller is sorting.
Example (Bm25) ¶
Example_bm25 shows ranking a small corpus by keyword relevance.
c := New()
c.Add("moby", "Call me Ishmael. The whale, the ship, the sea.")
c.Add("austen", "It is a truth universally acknowledged, marriage and fortune.")
for _, r := range c.Search("whale ship", 0) {
if r.Score > 0 {
fmt.Println(r.ID)
}
}
Output: moby
Example (HybridRRF) ¶
Example_hybridRRF shows fusing a keyword ranking with a (pretend) vector-similarity ranking via reciprocal-rank fusion.
keyword := []string{"doc1", "doc2", "doc3"} // best-first by BM25
semantic := []string{"doc1", "doc3", "doc4"} // best-first by cosine
fused := FuseRanked(DefaultRRFK, keyword, semantic)
fmt.Println(fused[0].ID) // doc1 is #1 in both → ranks first
Output: doc1
Index ¶
Examples ¶
Constants ¶
const ( DefaultK1 = 1.5 DefaultB = 0.75 )
Default Okapi BM25 free parameters. k1 controls term-frequency saturation (how quickly extra occurrences stop helping); b controls length normalisation (0 = none, 1 = full). These are the standard textbook defaults and work well across mixed corpora.
const DefaultRRFK = 60
DefaultRRFK is the conventional reciprocal-rank-fusion damping constant.
Variables ¶
This section is empty.
Functions ¶
func ReciprocalRankFusion ¶
ReciprocalRankFusion fuses two rankings of the same item set into a single score per item, the standard RRF formula:
RRF(item) = Σ_ranking 1 / (k + rank(item))
rank is 1-based position in each input ranking. k (typically 60) damps the contribution of low ranks so neither list dominates. Each input is a slice of item IDs in ranked order (best first); the return maps item ID → fused score. Items missing from a ranking simply don't contribute that list's term.
func Tokenize ¶
Tokenize splits text into lowercase word-shaped tokens — maximal runs of Unicode letters and digits, everything else a separator. The same tokenizer is applied to both queries and documents so they share a vocabulary. Mirrors internal/fingerprint's tokenizer so keyword and near-duplicate views agree on word boundaries.
Types ¶
type Corpus ¶
type Corpus struct {
// contains filtered or unexported fields
}
Corpus is a small in-memory BM25 index for the common "add documents once, run many queries" workflow. IDF and average document length are computed over the WHOLE corpus (the standard Okapi BM25 setup).
For advanced use — streaming, or scoring against a per-query candidate set whose IDF should reflect only those candidates — drive the lower-level Scorer / DocStats / StatsForTokens directly instead.
A Corpus is not safe for concurrent Add and Search; guard it yourself if you mutate and query from multiple goroutines.
func New ¶
func New() *Corpus
New returns an empty Corpus using the default BM25 parameters (DefaultK1, DefaultB).
func NewWithParams ¶
NewWithParams returns an empty Corpus with explicit BM25 parameters. k1 controls term-frequency saturation, b the length normalisation (0..1). Out-of-range values fall back to the defaults at score time.
type DocStats ¶
DocStats is the per-document data BM25 needs: the term frequency of each QUERY term in the document, plus the document's total token length. It's query-scoped (TermFreqs only holds query terms) so it stays tiny regardless of body size — the walker captures it during body extraction.
func StatsFor ¶
StatsFor builds the DocStats for a body given the query terms. It tokenizes the body once: counting the total length and tallying only the frequencies of terms that appear in queryTerms.
func StatsForTokens ¶
StatsForTokens is StatsFor for an already-tokenized document — use it when you tokenize once and score against many queries (e.g. Corpus) so you don't re-tokenize the body on every call.
type Result ¶
Result is one ranked document: its caller-supplied ID and score. Higher Score is more relevant. Scores are only comparable within a single Search / FuseRanked call.
func FuseRanked ¶
FuseRanked combines several ranked ID lists into one, scored by reciprocal-rank fusion, and returns them sorted by fused score descending (ties broken by ID). It's the sorted-slice companion to ReciprocalRankFusion — the shape most callers want for hybrid search (e.g. fuse a BM25 ranking with a vector-similarity ranking). k is the RRF damping constant (DefaultRRFK is the usual choice). Each ranking is best-first; an ID missing from a list simply doesn't get that list's contribution.
type Scorer ¶
type Scorer struct {
// contains filtered or unexported fields
}
Scorer holds the corpus statistics (IDF per query term, average doc length) needed to score any document in the corpus. Build it once per candidate set with NewScorer, then call Score per document.
Source Files